6

我需要遍历所有最多有 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）。

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

4

5 回答 5

4

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

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

例如，如果 k 是 2 并且您1010忽略了最后一个0并增加了，101那么您得到110然后添加0for 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
于 2012-05-05T02:42:47.227 回答
1

以Bit hack 的答案来生成具有给定数量 1 的所有整数并循环[1,k]。这将生成每个具有最多k位的整数一次。

于 2012-05-05T03:38:22.133 回答
0

组合学。

如果您有具有n位长度和r位设置的整数，那么就有nCr这样的数字。只需使用组合生成器并根据需要迭代组合。

于 2012-05-05T03:14:39.407 回答
0

如果必须在 4 中设置 2 位，则设置的最低位最多必须是第三位（从 0...3 开始计数），最高位必须至少是第二位。

所以你可以循环2个循环

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

由于您不想为 16 位编写 16 个循环，因此您可以将这个想法转换为递归的。

于 2012-05-05T02:43:29.280 回答
-1

您可以使用如下所示的 while 循环。这个循环只会循环没有位。如果你的位数是固定的，你可以使用休息

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

例如：
如果 64(1000000) 它将只循环一次，
如果 72(1001000) 则循环 2 次

于 2012-05-05T02:57:14.893 回答