如何查找32位缓冲区中是否有n个连续的设置位？

Question

也许你可以帮助我解决以下问题,这可以帮助我加速我正在考虑的内存管理器(我不确定是否存在解决方案 - 我没有找到一个).

我有一个32位寄存器,我需要找到它中是否有n个连续的设置位,如果是,那么它们的偏移量是多少.例如,如果寄存器保持以下值111100000000000000000001111111000且n等于4 - 接受以下任何答案(偏移量从0开始):

3,4,5,6,28

我所拥有的原子操作都是常规的按位运算(&,|,〜,...),并且还找到最低有效位偏移(上面的寄存器中为3).该算法(假设存在一个) - 应该不超过5个原子操作.

Answer 1

如果有一种算法可以做到这一点，那么最坏情况的复杂度至少为O(m-n)，其中m是寄存器中的位数，n是您要查找的连续设置位的数量。这很容易看出，因为如果设置了所有位，您的算法将必须准确输出m-n项目，因此它的复杂性不能再低了。

编辑

对于类似的问题，有一个优雅的解决方案：循环遍历整数 ruby​​ 中的位，找到 longes 序列的长度1。

n如果您提前知道要寻找的跑步长度，则该算法将只需要n步骤。然后可以通过大约 5 个以上的步骤从算法最后一步中的尾随零的数量恢复偏移量。这不是非常有效，但可能比循环解决方案更好，特别是对于小型n.

编辑2

如果n提前知道，我们就可以计算出一系列必要的转变。例如，如果我们正在寻找 7 位运行，那么我们必须这样做

x &= x >> 1
x &= x >> 3
x &= x >> 1
x &= x >> 1

关键是，n/2如果n是偶数，我们右移位；如果是奇数，我们右移 1 位n，然后相应地更新n（要么n = n - 1 or n = n / 2），如 @harold 所建议的。即时估计这些值会很昂贵，但如果我们预先计算它们，那么它将非常有效。

编辑3

更好的是，对于任何n，ceil(log(2,n))都需要精确的步骤，无论我们采取哪种转变，只要它在floor(n/2)和之间2^floor(log(2,n-1))。请参阅下面的评论。

Answer 2

对于每个可能的字节值（0-255），计算开头的位数、结尾的位数、字节内最长的连续位数以及该序列的偏移量。例如，对于0b11011101，开头有 2 位，结尾有 1 位，其中有 3 个连续位的序列。

将此值存储在 4 个数组中，例如start, end, longest, longest_offset。

然后，将 32 位数字视为 4 字节数组，并按如下方式迭代这些字节：

int search_bit_sequence(uint32 num, int desired) {
  unsigned char *bytes = (unsigned char *)#
  int i, acu;
  for (acu = i = 0; i < 4; i++) {
    int byte = bytes[i];
    acu += start[byte];
    if (acu >= desired)
      return (i * 8 - (acu - start[byte]));

    if (longest[byte] >= desired)
      return ( i * 8 + longest_offset[byte]);

    if (longest[byte] < 8)
      acu = end[byte];
  }
  return -1; /* not found */
}

更新：请注意，CPU 的字节顺序可能需要更改循环方向。