[Math] general formula to generate all numbers with a given binary / Hamming weight

binarycombinatorics

It's easy to generate numbers that have one non-zero digit in their binary representation, and it's not much harder to generate numbers with two non-zero digits. It rapidly seems to become more difficult, though. Is there a general formula that will let me generate all numbers of all lengths with (say) 7 non-zero digits, starting with 1111111 and continuing indefinitely?

If there isn't a general formula, is there a standard algorithm?

Best Answer

There is an algorithm: how standard it is I couldn't tell you, but it's well enough known that I learnt it as an undergrad in computer science. It's due to Bill Gosper and it transforms a number into the next largest number with the same Hamming weight using (twos complement) arithmetic and bitwise operations. Input val, output next, code (with suitable types) is valid in most languages related to C, although some may need >>> instead of >> for right shift without sign extension:

c = val & -val;
r = val + c;
next = (((r^val) >> 2) / c) | r;

c is the least power of 2 in the binary representation of val: this relies on twos complement, since to negate an integer you invert its bits and add 1.

val + c causes carries to ripple through the continuous set bits from c up until a 1 is carried into a 0.

r ^ val therefore gives a value equal to twice the value of the lowest continuous block of set bits in val. Shifting right 2 is equivalent to division by 4, and then dividing also by c causes the bottom bit in r ^ val to be lost to a flooring operation. Since r has kept one carry bit, the final Hamming weight of next will therefore be the same as in val, and if this explanation is clear enough then it should be obvious that it's the lexicographically next value with that property.

Related Question