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