algorithm - 遍历最多 k 位 ON 的整数的最佳方法是什么？

Question

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

目前我正在使用这个简单的算法:

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)。

我的问题是:有没有更有效的算法来做到这一点？

Answer 1

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

另一种说法是，对于标准计数器，您将最低有效位加 1 并进位。在您的情况下，当有 k 个“1”时，您会将 1 添加到最低的“1”位。

例如，如果 k 是 2 并且你有 1010 忽略最后的 0 并递增 101 所以你得到 110 然后为 1100 添加 0。

这是递增数字的伪代码:

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