循环最多k位为ON的整数的最佳方法是什么? [英] What is the best way to loop through integers with at most k bits ON?

问题描述

我需要遍历所有n位整数，这些整数最多具有k位ON(位1)，其中0≤n. n ＜＝ 32和0 ＜＝ k ＜＝ n.例如，如果n = 4且k = 2，则这些数字(以二进制数字表示)为:0000、0001、0010、0100、1000、0011、0101、0110、1001、1010、1100.这些数字的顺序是循环访问并不重要，但是每个访问仅一次.

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

我认为该算法效率不高，因为它必须遍历太多数字.例如，如果n = 32且k = 2，则它必须遍历2 ^ 32个数字以仅找到529个数字(具有<= 2位1).

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?

推荐答案

您将需要创建自己的按位计数算法来递增循环计数器.基本上，为了计算序列中的下一个数字，如果少于k个"1"位，则正常递增；如果有k个"1"位，则在最低有效位"1"不等于后假装为"0"位存在并正常增加.

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.

另一种说法是，使用标准计数器，您需要在最低有效位上加1并进位.对于您的情况，当有k个数字"1"时，您将1加到最低的"1"位.

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.

例如，如果k为2并且您有1010忽略最后一个0并增加101，则得到110，然后为1100添加0.

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

这篇关于循环最多k位为ON的整数的最佳方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！