Skip to main content
1 of 7
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

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

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, 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.
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 and 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.

Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76