What is the best way to loop through integers with at most k bits ON?
algorithm
Solution
You are going to need to make your own bitwise counting algorithm for incrementing the loop counter. Basically, for calculating the next number in the sequence, if there are fewer than k '1' bits, increment normally, if there are k '1' bits, pretend the '0' bits after the least significant '1' don't exist and increment normally.
Another way of saying it is that with a standard counter you add 1 to the least significant bit and carry. In your case, when there are k number of '1's you will add in the 1 to the lowest '1' bit.
For instance if k is 2 and you have `1010` ignore the last `0` and increment the `101` so you get `110` and then add in the `0` for `1100`.
Here is Pseudocode for incrementing the number:
Count 1 bits in current number
If number of 1's is < k
number = number + 1
Else
shift_number = number of 0 bits after least significant 1 bit
number = number >> shift_number
number = number + 1
number = number << shift_number
Problem
I need to loop through all n-bit integers which has at most k bits ON (bits 1), where 0 < n <= 32 and 0 <= k <= n. For example, if n = 4 and k = 2 then these numbers are (in binary digits): 0000, 0001, 0010, 0100, 1000, 0011, 0101, 0110, 1001, 1010, 1100. The order in which these numbers are looped through is not important, but each is visited only once. Currently I am using this straightforward algorithm: ``` for x = 0 to (2^n - 1) count number of bits 1 in x if count <= k do something with x end if end for ``` I think this algorithm is inefficient because it has to loop through too many numbers. For example, if n = 32 and k = 2 then it has to loop through 2^32 numbers to find only 529 numbers (which have <= 2 bits 1). My question is: is there any more efficient algorithm to do this?