位运算统计二进制中 1 的个数

1. 核心技巧

统计一个整数中有多少个 1：

int count = 0;

while (n)
{
    n = n & (n - 1);
    count++;
}

关键不是 while，而是：

n & (n - 1)

它的作用：

消除 n 最右边的那个 1。

---

2. 为什么能消掉？

假设：

n = 1011000

那么：

n-1 = 1010111

相与：

  1011000
& 1010111
---------
  1010000

可以看到：

1011000
     ↑
   最右边的 1

被消掉了。

---

3. 循环一次，消掉一个 1

例如：

1011000
   ↓
1010000
   ↓
1000000
   ↓
0000000

一共消掉 3 个 1。

所以：

count

最终就是二进制中 1 的个数。

---

4. 为什么比逐位检查更好？

普通方法可能这样：

while (n)
{
    if (n & 1)
        count++;

    n >>= 1;
}

每一位都要检查。

而：

n = n & (n - 1);

是直接消掉一个 1。

所以循环次数不是固定的位数，而是：

循环次数 = 二进制中 1 的数量。

如果一个 32 位整数只有 2 个 1：

00000000 00000000 00000000 00000101

只循环 2 次。

---

5. 最终记住

n & (n - 1)
       ↓
消掉最低位的 1
       ↓
循环一次 = 消掉一个 1
       ↓
循环多少次 = 有多少个 1

所以这个算法最核心的一句话就是：

n & (n - 1)：消掉最低位的 1。