Reference Request: Representing Positive Integers as Differences with Minimal Hamming Weight

Question

Background of my reference request is an observation that I made, while I was still in school: there are two ways to calculate $x*999$: either do it directly, by applying the multiplication algorithm that is taught in school or, calculate it as $x*1000-x*1$ of which the second way is much easier.
But, I had no clue about the rules behind such a simplification.

Later, having studied computer science and math, and having learned of binary digits, things got clearer and I realized that the objective would be to express the multiplicator as a difference of non-negative integers with a minimal number of 1-bits in the binary representation.
Despite the fact that such a representation could speed up multiplication via repeated addition plus one subtraction or, exponentiation via repeated squaring plus one division, I could not find any mentioning of that representation or how to obtain an optimal such representation.

I would therefore appreciate any pointers to information about the construction and properties of the representation of natural numbers as a difference with minimal Hamming weight.

My currently best algorithm to determine a such difference-representation with a small Hamming weight is to
first fill "fissions", i.e. replace 0-bits that are next to two 1-bits on the left and on the right, so $...11011...$ becomes $...11111...$
and then replace each bit of an uninterrupted sequences of at least three 1-bits by 0-bits and, each 0-bit that is immediately to the left of such a sequence, by 1-bit so that $...011...10...$ would become $...100...00...$
With that operations, 27 would first become 31 due to fixing the fission and finally 32; the difference-representation is then 32-5 with a Hamming weight of 3 instead of 4.

An interesting phenomen is, that there are bit-patterns like $0010011011$, for which the difference encoding reduces the Hamming weight also for the bit-complement and, there are others, like $0110011$, for which no improvement is possible, even for the bit-complement.
This raises the question about the statistical properties of the quotient of the Hamming weights of difference encoding and of standard encoding of numbers.

EDIT:
In order to give some impression of the amount of operations that can be saved, I applied the method to the first 200 binary digits of some wellknown constants; the percentages relate to the number of 1-bits:

$60\% \approx 67/111$ Khinchin constant
$66\% \approx 71/108$ Chapernowne constant
$66\% \approx 72/109$ ln(2)
$68\% \approx 75/111$ Conway constant
$68\% \approx 75/110$ sqrt(2)
$69\% \approx 69/100$ Euler-Mascheroni constant
$70\% \approx 65/093$ Apéry constant
$73\% \approx 74/101$ Plastic Number
$73\% \approx 77/105$ $e$
$73\% \approx 77/105$ Golden ratio
$79\% \approx 70/089$ Feigenbaum constant
$83\% \approx 68/082$ $\pi$

Below, the binary digits of the respective constants are listed; boldface runs of digits incur a saving of additions that equal to #bits-(2 + #0-bits):

Khinchin constant
10.1010 111101111 00 111 00100001000 1111 000 11011 01000011010 11101111 0010 111111011111 00 11111 000 111 0010100011001100 11111111 00 111 00001100 111 0010010 111 000000010000 1111 00110000110000010100 11101110111111 010010011

Chapernowne constant
0.000 111111 0011010 110111 0100 1101111 01010001000 1111111 01000000 111 000001101010011000 111110111 000010 110111 01000000 111111111111 01001010100000 111 0100101010 11011011 001101010 11011011 00000010100 111011 000100011001

ln(2)
0.101100010 111 001000010 1111111011111 01000 111 00 111101111 001101010 1111 00100 1111 000 111011 00 111 0011000000000 111111 0010 1111011 01010 1111 01000000 1111 001101000011001001100 111 00101001100010 11011 00010 11011 000101

Conway constant
1.0100 110110110111 00 1111 01011010100100 11111011 00010010000010101010 11111 00010101001010101010 1111 00 111 010101100010101100 111011111 00 111110110110111 000100 1110111 00000 111 0001001010 111 00 111 0100100101000 1111

sqrt(2)
1.011010100000100 1111 0011001100 1111111 00 11101111 00110010010000100010110010 11111011 000100 11011 00 110111 01010100101010 11111 0100 11111 000 111 010 1101111011 0000010 111 0101000100100 1110111 010100001001100 111011 01

Euler-Mascheroni constant
0.100100 1111 00010001100 111111 000 11011111011011 000011000 1111 01001001101000 11011111 000 1111111 0000001000000010101001011001011010101101010000 111 00 111011 00110000 111 010 1111011 0010 111 001100000000011001000011

Apéry constant
1.001100 1110111 010000000000100 1111 0000000001100010000100 111 00000 110111 00010 111 0001010 111 000101100 1111 00110100100000 1111111 000 11011 00011000000010 11011111011011 00010 111 01001001001101000000010 1110111 01001

Plastic number
1.010100110010000010 110111 0100 111011 001010010001001010 11011 010110000010 1111 000100010010 11111 00010000010100011000010011001101000 111 00 11011111111 00000010 111 0010 1111 000 111 00 11111 010 111011 01010110000110011

$e$
10.10 110111111 00001010100010110001010001010 111011 01001010100110101010 1111110111 00010101100010000000100 111 00 1111 0100 1111 00 1111 000 111011 00010 111 00 111 000101100000 1111 00 111 00010110100 11011 0100101011010101

Golden ratio
1.100 1111 000 11011101111 00 110111 0010 1111111 010010100 11111 000001010 11111 00 111 00 111 001100000001100000010 111 00 1110110111 00100000110100000100001000001000100 111011010111111 00 111 01000100 111 00100101000 111111

Feigenbaum constant
100.1010101101010000110010 111111 000110000 111 0010010 111 01000 111 01000 111 0000000100 111011 01010001011010 111 000100110010000 111111011 010000000100010000110000000 1111 0001011000000010011000100 111 00101010101001

$\pi$
11.0010010000 111111011 0101010001000100001011010001100001000110100110001001100011001100010100010 111 0000000 110111 00000 111 001101000100101001000000100100 111 0000010001000101001100 11111 0011000 111 01000000001

Answer 1

Subtraction will produce an improvement in total weight if and only if there is an interval of $k$ bits where then number $r$ of ones satisfies $2r > k+2$.

Proof: We may assume the interval is preceded by a zero. Subtraction will transform it into the difference between the length $k+1$ string $10\cdots0$ (with 1 one) and the twos-complement (with $k-r+1$ ones). Total ones before: $r$. Total ones after: $k-r+2$.

We can call intervals satisfying the previous bound "good". If you have a good interval, your total weight doesn't change if you subdivide it at a place where there are two consecutive zeroes, and the total weight decreases if there are more than two consecutive zeroes. This means that a straightforward greedy algorithm will produce a minimal representation: start from one end or the other, and start forming a candidate interval when you hit a one. If you hit two zeroes, end your candidate interval, and check whether the number of ones satisfies the bound for goodness.

I think the reason this method is not used in multiplication algorithms is that it only yields a substantial advantage for a very small proportion of possible numbers. When $n$ is large, almost all $n$-bit numbers have very close to $n/2$ ones in the binary representation, and the bits are generally not clustered enough to make it advantageous to replace a single multiplication operation with a cluster search plus two multiplications plus a subtraction.

Answer 2

More extended comment than answer:

My understanding is that this is basically the idea behind the Fast Fourier transform multiplication algorithm. My impression is that the intuition behind finding Fourier coefficients is the same as your intuition, i.e., expressing numbers in terms of "basis" elements (like $1000$ in your initial example), and doing so as efficiently as possible, so that operations on these bases are easy.

So, for instance, we can view an $n$-bit number as a point in $\{0,1\}^n$ written in terms of the basis points $(1,0,0,\dots), (0,1,0,0,\dots),\dots$. Then we can use the Fourier transform to write it in terms of some other, more convenient basis, do some operations in that space, then convert it back to get the results of our multiplication.

But usually this is done in $\mathbb{C}$ and the bases are the $n$th roots of unity. I wish I knew more about this whole process, specifically, why the $n$th roots of unity are chosen as a basis and whether some other basis would work as well; also, I would be interested to know how a general Fourier transform would work for your particular setting (Hamming distance), but unfortunately I don't have the understanding to say. I hope someone else can perhaps respond and explain!

Anyway, there's some explanation of the FFT algorithm on the wikipedia page, and an explanation of the FFT algorithm for multiplying polynomials is in Chapter 2, section 2.6 of Algorithms by Dasgupta, Papadimitriou, and Vazirani, available for free.

---