c - 查找连续设置/未设置位的 block

Question

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

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

Answer 1

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

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

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

现在仅设置 3 个连续位序列的开始位(从 LSB 开始)。

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

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

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

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