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