如何统计一个整数二进制中 1 的个数？（汉明重量，LeetCode 191）

简化版

求一个整数二进制表示中 1 的个数（汉明重量 Hamming Weight）。最优雅的做法用 n & (n - 1) 每次消掉最低位的一个 1，循环几次就有几个 1——循环次数只等于 1 的个数，比逐位检查快。也可以逐位 (n >> i) & 1 检查 32 位。Java 处理负数要用无符号右移 >>> 或直接用 n & (n-1) 法（不受符号位影响）。

详细版

解法一：n & (n-1) 消 1（推荐，循环 = 1 的个数）

int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);      // 消掉最低位的 1
        count++;
    }
    return count;
}

解法二：逐位检查（固定 32 次）

int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        count += (n >>> i) & 1;   // 用 >>> 无符号右移，避免负数符号位
    }
    return count;
}

n & (n-1)：把 n 最低位的 1 变 0，其余不变。循环到 n 为 0，执行次数就是 1 的个数。
负数处理：解法一天然正确（一直消到 0）；解法二必须用 >>>（逻辑右移补 0），否则 >> 对负数补符号位会死循环/出错。
复杂度：解法一 O(1 的个数)，解法二 O(32)，都 O(1) 空间。

完整版教学

一、朴素解法：逐位检查

最直接的想法是检查每一位：让 n 不断右移，每次看最低位是不是 1（n & 1），累加。或者固定循环 32 次，用 (n >>> i) & 1 取第 i 位。

关键坑：负数。Java 的 int 是有符号的，负数最高位是 1。如果用算术右移 >>（补符号位），负数右移时高位一直补 1，while (n != 0) n >>= 1 会永远不为 0，死循环。所以逐位法必须用无符号右移 >>>（补 0），或者固定循环 32 次而非「移到 0 为止」。

二、更优解法：`n & (n - 1)` 消 1

核心技巧：n & (n - 1) 会把 n 最低位的那个 1 清成 0，其余位不变。

原理：n - 1 会把 n 最右边的 1 借位变成 0，并把它右边所有的 0 变成 1。举例 n = 1100，n-1 = 1011，n & (n-1) = 1000——最低位的 1（第 2 位）被消掉了。

于是循环 n &= (n-1) 每执行一次就抹掉一个 1，直到 n 变 0。循环次数恰好等于 1 的个数。好处：如果 n 只有很少的 1（比如 1 个），循环 1 次就结束，比固定 32 次快得多。而且它对负数也天然正确——负数有很多 1，一个个消到 0 为止，count 就是 1 的个数（负数的补码 1 的个数）。

三、为什么 `n & (n-1)` 能消最低位的 1

设 n 最低位的 1 在第 k 位，那么 n 的第 k 位是 1、第 0~k-1 位都是 0。减 1 时：

第 k 位借位变 0；
第 0~k-1 位从全 0 变成全 1；
第 k 位以上不变。

所以 n-1 和 n 相比，只有第 0~k 位不同（n 是 1000...0，n-1 是 0111...1）。两者相与，第 0~k 位全变 0（一个是 1000、一个是 0111，与起来 0000），第 k 位以上保持不变——净效果就是抹掉第 k 位那个最低的 1。

四、其他高效方法

查表法：预处理 0~255 每个字节的 1 的个数，把 32 位拆成 4 个字节查表相加。O(1)，工业常用。
内置函数：Java Integer.bitCount(n)、C++ __builtin_popcount(n)、有的 CPU 有 POPCNT 指令。面试可提一句，但通常要求手写。
分治位统计（SWAR）：用掩码并行地两两、四四相加，Integer.bitCount 内部就是这个，O(1)。属加分项。

五、相关变体

比特位计数（338）：求 0..n 每个数的 1 的个数，用 DP dp[i] = dp[i & (i-1)] + 1（消掉一个 1 后再 +1）或 dp[i] = dp[i>>1] + (i&1)。
汉明距离（461）：两数不同的位数 = hammingWeight(x ^ y)（先异或得到不同位，再数 1）。

这些都建立在「数 1」的基础上，一起掌握。

六、补码负数也能在有限轮内归零

Java int 是固定 32 位补码，负数并不是“前面有无限多个 1”的数学对象。以 8 位模型的 -5=11111011₂ 为例，Brian Kernighan 操作每次仍只清一个最低位 1，最终会清成 0。固定宽度解释了它对负数正确，也解释了复杂度上界。

11111011  (-5 的 8 位补码，7 个 1)
11111010  清第 0 位
11111000  清第 1 位
11110000  清第 3 位
11100000 -> 11000000 -> 10000000 -> 00000000
总共 7 轮，恰等于补码中的 1 的数量

校验维度	本题必须保持的结论
循环/递推不变量	循环开始时 count 等于原位模式已清除的 1 数，n 保留尚未统计的所有 1。
边界条件	`n=0` 循环零次；逐位右移负数时必须使用 `>>>` 或固定 32 次。
复杂度与代价	Kernighan 法执行 popcount(n) 轮，上界 32；机器字宽固定时通常记 O(1)。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

位运算题的代码通常很短，真正容易错的是把数学整数、固定宽度位模式和语言移位规则混在一起。本题应先复述这条不变量：循环开始时 count 等于原位模式已清除的 1 数，n 保留尚未统计的所有 1。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“11111011 (-5 的 8 位补码，7 个 1)”开始手推，最后应得到“总共 7 轮，恰等于补码中的 1 的数量”。
边界复核：n=0 循环零次；逐位右移负数时必须使用 >>> 或固定 32 次。
代价复核：Kernighan 法执行 popcount(n) 轮，上界 32；机器字宽固定时通常记 O(1)。
用全 0、只有一个 1、最高位为 1 三类位模式检查掩码。
涉及负数时把值写成固定宽度补码，确认使用 >> 还是 >>>。
涉及左移时检查移位距离和溢出后是否仍符合题目的位模式语义。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“循环开始时 count 等于原位模式已清除的 1 数，n 保留尚未统计的所有 1。”这条正确性主线不能省。

八、常见误区与追问

误区：负数使用 n&(n-1) 会无限循环。 Java int 只有 32 位，每轮严格少一个 1，最多 32 轮归零。
误区：while(n!=0){n>>=1;} 对所有 int 都安全。 负数算术右移持续补 1，最终停在 -1 而不是 0。
误区：算法复杂度应无条件写 O(log n)。 对固定 32 位 int 可写 O(1)；按可变位宽模型则是 O(w) 或 O(popcount)。
追问：汉明距离如何复用本题？ 先计算 x^y，异或结果为 1 的位置就是两数不同的位置，再统计其 1。
追问：为什么 Integer.bitCount 往往更快？ JIT 可能使用并行位计数技巧或映射到硬件 POPCNT 指令。
追问：若输入是大整数怎么办？ 需要按机器字分块统计并累加，每块可继续使用同样的清位或内建操作。

九、加强记忆

统计二进制 1 的个数（汉明重量）= n & (n - 1) 反复消掉最低位的 1，循环次数 = 1 的个数（n-1 把最低位 1 及右边翻转，相与即抹掉那个 1），对负数天然正确、比逐位快。逐位法 (n >>> i) & 1 必须用无符号右移 >>> 防负数死循环。变体：汉明距离 = bitCount(x^y)，比特位计数 DP dp[i]=dp[i&(i-1)]+1。核心记住那句：n & (n-1) 消一个 1。

简化版

详细版