查找连续设置/未设置位的块

Question

我正在寻找一种方法来在位集中找到连续的设置或未设置位块，例如在位集中，01010111010如果我正在寻找 3 个设置位，我想得到 6 作为结果（从 1 开始计数，如果我会从0开始数）。

另外，这是针对操作系统开发的，因此没有 stdlib 可以为我执行此操作。

Answer 1

假设您正在寻找整数 n 中的 3 个连续位。

首先，按位与将值与其本身右移 1 和 2 位：

n = n & (n >> 1) & (n >> 2);

现在，仅设置 3 个连续位序列的开始位（从 LSB 开始）。

如果您需要检查连续 3 个以上的游程，则可以在任意（但很小）游程长度的循环中执行此操作。

然后，使用快速位操作算法计算二进制数中的尾随零，找到设置的第一个位（从最低有效位开始计数为位 0） 。

通过这种方法，您只需使用少量操作即可一次搜索 32 或 64 位。然而，如果您正在查找 32 位或 64 位整数的字符串，情况会变得更加复杂，但您可以对每个字重复该过程，在第一步中移入下一个 int 的低位。

如果您要查找的连续位数很大，这也不是最佳选择。