Is there a general formula to generate all numbers with a given binary / Hamming weight?

Question

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?

Answer 1

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.

Answer 2

If you want to generate all numbers whose binary representation has exactly $k$ non-zero digits, and is at most $n$ digits long, the following procedure works: Let $S = \{0, 1, 2, \dotsc, n-1\}$. For all $T \in S$ where $|T| = k$, the number $\sum_{t \in T} 2^t$ has exactly $k$ non-zero digits, and further they are all unique. Assuming you are using a computer, it is easy for computers to iterate over all such subsets of $S$.

If you want to generate all numbers whose binary representation has exactly $k$ non-zero digits regardless of total length, the following procedure works: The first number is $\sum_{i=0}^{k-1} 2^k$. After that, let $S = \{0, 1, 2, \dotsc, k-1\}$. Iterate a variable $x$ starting from $k$ and continuing upwards indefinitely. For each value of $x$, choose a subset of $T$ such that $|T| = k-1$ and generate a number as described above. To this number add $2^x$. This gives you unique numbers with exactly $k$ non-zero digits and goes on forever.