原始题目

以下代码的输出是什么？

#include <iostream>
using namespace std;
int main() {
    int n = 10;
    int count = 0;
    while (n > 0) {
        n &= (n - 1);
        count++;
    }
    cout << count << endl;
    return 0;
}

答案：2

这段代码在干什么

它在统计 n 的二进制中有几个 1（也就是 popcount）。

这是大名鼎鼎的 Brian Kernighan 算法，核心只有一行：

n &= (n - 1);   // 把 n 最低位的那个 1 清成 0

每执行一次，n 里就少一个 1；循环几次，就有几个 1。

逐步模拟（n = 10 = 1010₂）

n 变成 0，循环结束，输出 2。

10 的二进制是 1010，确实有 2 个 1。

为什么 n & (n-1) 能清掉最低位的 1

以 n = 1010 00（末尾两位是 0）为例：

• n - 1 做减法时，要向最低位的那个 1 借位
• 结果：这个 1 变成 0，它右边所有的 0 全变成 1，更高位不变

n     = 1010 0 0
n - 1 = 1001 1 1      ← 最低位的 1 变 0，右侧 0 全变 1
&     = 1000 0 0      ← 该位及其右侧全部清零，高位不变

一句话记忆：n & (n-1) 抹掉最低位的 1。

复杂度：为什么它更快

比如 n = 1（二进制只有一个 1），普通方法要转 32 次，这个算法只跑 1 次。

经典应用一：判断 2 的幂

2 的幂（1、2、4、8、16…）的二进制只有一个 1：

bool isPow2(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

抹掉唯一那个 1 后变成 0，就是 2 的幂。

经典应用二：统计位差异、判重、状态压缩

// 统计 a、b 有多少位不同（先异或，再数 1）
int diff = a ^ b;
while (diff) { diff &= (diff - 1); cnt++; }

在状态压缩 DP、子集枚举里，这个技巧出镜率极高。

补充：n 是负数会死循环吗

不会。每次循环都清掉一个 1，最终一定会归零，只是 count 统计的是补码表示中 1 的个数（含符号位）。

int n = -1;   // 补码全 1
// 循环 32 次后 count = 32

考点总结（CSP-J 初赛选择题）

1. 看到 n &= (n - 1) + 计数 → 统计二进制中 1 的个数。
2. 循环次数 = 1 的个数，不是 \(\log n\)。
3. n & (n-1) == 0 → 判断是否为 2 的幂。
4. 秒杀技巧：直接把 n 写成二进制，数里面有几个 1 就是答案。

思考题

int n = 15;（1111₂）时输出多少？如果改成 n = 16（10000₂）呢？