Geek asks and answers

What is the best way to iterate over integers with no more than k bits ON?

I need to iterate over all n-bit integers in which no more than k bits are ON (bit 1), where 0 <n <= 32 and 0 <= k <= n. For example, if n = 4 and k = 2, then these numbers (in binary digits): 0000, 0001, 0010, 0100, 1000, 0011, 0101, 0110, 1001, 1010, 1100. The order in which these numbers are looping it doesn’t matter, but each of them is visited only once.

I am currently using this simple 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 iterate over too many numbers. For example, if n = 32 and k = 2, then he must go through 2 ^ 32 numbers to find only 529 numbers (which have <= 2 bits 1).

My question is: is there a more efficient algorithm for this?

+5
5

. , , , k '1', , k '1' , "0" "1", .

, 1 . , k '1, 1 ' 1 '.

, k 2, 1010 0 101, 110, 0 1100.

Pseudocode :

Count 1 bits in current number
If number of 1 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
+3

-, 1s [1,k]. k .

+1

2 4, ( 0... 3) , , .

, 2

for lowest in 0 to (n-k)
  for highest in lowest + 1 to 3 
    (0000).setBit (lowest).setBit (highest)

16 16 , .

0

.

If you have integers with bit length nand bits r, then there are nCrsuch numbers. Just use the combination generator and iterate over the combinations if necessary.

0
source

you can use while loop as below. In this loop there will only be a loop without bits. if you do not want the bit to be fixed, you can use a gap

countbits = 0
while num > 0
    num = num & (num-1)
    countbits = countbits + 1
end while

for example:
if 64 (1000000) it will loop only once,
if 72 (1001000), then 2 times

-1
source

More articles:


All Articles