算法基础 -- Brian Kernighan 算法初识

Brian Kernighan 算法：利用 x & (x - 1) 逐步清除最低位的 1

1. 算法原理

• x & (x - 1) 这个操作的作用是每次清除 x 的最低位的 1。
• 由于 二进制的减法 会影响最低的 1，我们可以利用这一特性不断去除 1，直到 x 变为 0，从而统计 1 的个数。

2. x & (x - 1) 操作的数学推导

对于任意正整数 x，可以用二进制表示：
$$x=\text{...}1000\text{...}000$$
（假设 x 的最低位的 1 出现在某个位置）

当 x - 1 计算时，二进制的减法规则会导致：

• 最低位的 1 变为 0。
• 它右边的所有 0 变为 1（因为 -1 相当于借位操作）。

举例：

x     =  101000    // 40
x - 1 =  100111    // 39
x & (x - 1) = 100000  // 结果 32，最低的 1 被清除

可以看到：

• x - 1 把 x 最低的 1 变成 0，并把右侧所有 0 变成 1。
• x & (x - 1) 就只保留了 x 中比最低 1 更高的位，消除了最低位 1。

一般性证明：
设 x 的二进制最低 1 位于 k 位置（从右向左，从 0 开始编号），则：

• x = ...1000...000（最低位 1 在 k 处）
• x - 1 = ...0111...111（k 位置变成 0，右侧全变 1）

执行 x & (x - 1)：
$$x\&(x-1)=(...1000...000)\&(...0111...111)=(...0000...000)$$
可见，最低的 1 被消除。

3. 代码实现

#include <stdio.h>

int count_bits(uint32_t x) {
    int count = 0;
    while (x) {
        x &= (x - 1);  // 每次清除最低位的1
        count++;
    }
    return count;
}

int main() {
    uint32_t x = 0b10110101101100011011000101101010; // 示例数据
    printf("Number of 1s: %d\n", count_bits(x));
    return 0;
}

4. 代码解析

1. 初始化 count = 0，用于存储 1 的个数。
2. 循环执行 x &= (x - 1)：
   • 每次清除 x 的最低位 1。
   • count++ 统计已经清除的 1 的数量。
3. 循环终止条件是 x == 0，即 x 所有 1 都被清除。

5. 运行示例

假设 x = 0b10110101101100011011000101101010（等于 3073836458），二进制如下：

10110101101100011011000101101010

逐步消除最低位的 1：

10110101101100011011000101101010  // x
10110101101100011011000101101001  // x - 1
--------------------------------
10110101101100011011000101101000  // x & (x - 1)

10110101101100011011000101101000
10110101101100011011000101100111
--------------------------------
10110101101100011011000101100000

10110101101100011011000101100000
10110101101100011011000101011111
--------------------------------
10110101101100011011000101000000

...

不断重复，直到 x = 0。

最终 循环运行 19 次，输出：

Number of 1s: 19

6. 时间复杂度分析

假设 x 的位数是 n（32 位），设 x 里有 k 个 1，则：

• 每次操作都减少一个 1，因此总共执行 k 次操作。
• 最坏情况下 O(n)（x 的 32 位全是 1，如 0xFFFFFFFF）。
• 最好情况下 O(1)（x = 0b10000000000000000000000000000000，只执行一次）。
• 均摊复杂度 O(1)，因为实际数据往往 1 的个数远少于 32。

相比逐位检查：

• 逐位检查的复杂度始终是 O(n)，即最多执行 32 次。
• x & (x - 1) 只执行 O(k)，k 通常远小于 n，因此速度更快。

7. 适用场景

结论：

• 单个整数计算 → x & (x - 1) 是 CPU 无特殊指令时的最优选择。
• 处理大量整数 → __builtin_popcount(x) 或查表法更快。

8. 拓展：其他 x & (x - 1) 的应用

1. 判断 x 是否是 2 的幂（x 只有一个 1）

int is_power_of_2(uint32_t x) {
    return x && !(x & (x - 1));
}

示例：

8 (0b1000)  -> x & (x - 1) = 0
10 (0b1010) -> x & (x - 1) = 8 (!= 0)

2. 计算 x 的最低位 1 的位置

int lowest_bit_position(uint32_t x) {
    return x & -x;
}

示例：

x = 40 (0b101000)  -> x & -x = 8 (0b1000)

9. 结论

• x & (x - 1) 是一个强大的二进制操作，可以用来快速统计 1 的个数，适用于 CPU 没有 POPCNT 指令的情况。
• 时间复杂度 O(k)，其中 k 是 1 的个数，比逐位检查更快。
• 还能用于判断 x 是否是 2 的幂、提取最低位的 1 等多种用途。