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?
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
Take the answer to Bit hack to generate all integers with a given number of 1s and loop over [1,k]
. That will generate each integer with up to k
bits once.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With