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 



Reference Request: Representing Positive Integers as Differences with Minimal Hamming Weight
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.


