algorithm - 如何查找 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 项，因此它的复杂度不能再低了。

编辑

这里有一个类似问题的优雅解决方案 Looping through bits in an integer, ruby , 找到 longes 1 序列的长度。

如果您事先知道要查找的运行的长度n，则该算法将只需要n 步。然后可以在大约 5 个以上的步骤中从算法的前最后一步中的尾随零的数量中恢复偏移量。这不是非常有效，但可能比循环解决方案更好，尤其是对于较小的 n。

编辑 2

如果 n 是预先知道的，我们可以计算出一系列必要的移位。例如。如果我们正在寻找 7 位运行，那么我们必须做

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

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

编辑 3

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