algorithm - 循环最多k位为ON的整数的最佳方法是什么？

我需要遍历所有最多具有k个ON(位1)的所有n位整数，其中0
目前，我正在使用这种简单的算法:

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个数字(具有
我的问题是:有没有更有效的算法可以做到这一点？

最佳答案

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

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

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

这是用于增加数字的伪代码:

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

关于algorithm - 循环最多k位为ON的整数的最佳方法是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10458267/