题目要求

给定一个正整数 n，返回它的二进制表示中 1 的个数。这个数量也叫 Hamming weight。

LeetCode 提供的方法接口是：

hammingWeight(n: int) -> int

示例 1

输入：n = 11
二进制：1011
输出：3

示例 2

输入：n = 128
二进制：10000000
输出：1

约束

  • 1 <= n <= 2^31 - 1
  • 输入处于题目给定的非负整数范围内。

虽然当前约束从 1 开始，后面的实现也会自然处理 n = 0，并返回 0。

Step 1：先明确到底在数什么

先看一个不使用十进制表示的小任务：

n = 101100₂

从左到右可以看到三个 1：

1 0 1 1 0 0
^   ^ ^

所以答案是 3。

当前 baseline 是：

先看出整数的二进制表示，再人工统计其中的 1。

这个 baseline 的 break 是：

题目给我们的是整数，不是一串已经展开的二进制字符。人工观察不能直接变成处理任意输入的函数。

现在这一版能做到：

  • 知道统计对象是二进制表示中的 1，不是十进制数字中的 1。
  • 知道 11 的答案是 3，128 的答案是 1。
  • 知道后续算法必须直接操作整数状态。

它还缺：

  • 一个可以运行的整数位检查过程。

Step 2：先从最低位逐位检查

当前 baseline 需要读取一个整数的二进制位。

最低位只有两种可能：

  • n & 1 == 1：最低位是 1。
  • n & 1 == 0：最低位是 0。

检查完最低位后，可以执行：

n >>= 1

右移会删除已经检查过的最低位，让下一位成为新的最低位。

先写一个正确版本：

def hamming_weight_by_shift(n: int) -> int:
    count = 0

    while n:
        count += n & 1
        n >>= 1

    return count

用 101100₂ 检查：

当前 nn & 1count 更新后右移后的 n
1011000010110
10110001011
101111101
1011210
10021
1130

循环 invariant 是：

count 是已经从右侧移除的二进制位中 1 的数量，n 保存尚未检查的高位部分。

运行检查：

assert hamming_weight_by_shift(11) == 3
assert hamming_weight_by_shift(128) == 1
assert hamming_weight_by_shift(0) == 0

现在这一版能做到：

  • 直接检查整数的每个二进制位。
  • 正确统计所有 1。
  • 在 n 变成 0 时结束循环。

它还缺：

  • 即使某一位是 0，循环仍然要经过它。

Step 3：不要经过零位，直接删除一个 1

看第二个示例：

n = 10000000₂

它只有一个 1，但逐位右移需要执行八轮。

当前 baseline 的 break 是：

工作量取决于二进制总位数，而不是我们真正需要统计的 1 的数量。

考虑一个正整数减一时发生的变化。对 101100₂ 来说：

n     = 101100
n - 1 = 101011

最低位的那个 1 变成了 0，它右边原来的 0 全部变成了 1。

把两者进行按位与：

  101100
& 101011
--------
  101000

结果恰好删除了 n 中最低位的一个 1，其他更高位保持不变。因此：

n & (n - 1)

每执行一次，就会减少一个 1。

继续对 101100₂ 实际执行：

101100 -> 101000
101000 -> 100000
100000 -> 000000

一共执行三次，正好等于原数中 1 的数量。

把前一版的“读取最低位再右移”替换为：

n &= n - 1
count += 1

现在这一版能做到：

  • 每轮必定删除一个 1。
  • 不为两个 1 之间的零位单独执行循环。
  • 在只含一个 1 的 128 上只执行一轮。

它还缺：

  • 把“删除次数就是答案”写成完整 invariant 和 LeetCode 实现。

Step 4：删除多少次，答案就是多少

完整实现是：

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0

        while n:
            n &= n - 1
            count += 1

        return count

循环 invariant 是：

每轮结束后，count 等于已经删除的 1 的数量，n 保存原数中尚未删除的 1。

初始时没有删除任何 1，所以 count = 0。每轮中 n &= n - 1 恰好删除一个 1，随后 count += 1，invariant 继续成立。

循环结束时 n = 0，说明已经没有未删除的 1。此时 count 就是原数中所有 1 的数量。

运行检查

solution = Solution()

assert solution.hammingWeight(0) == 0
assert solution.hammingWeight(11) == 3
assert solution.hammingWeight(128) == 1
assert solution.hammingWeight(2**31 - 1) == 31

复杂度

设 k 是 n 的二进制表示中 1 的数量：

  • 时间复杂度：O(k)。每轮删除一个 1。
  • 额外空间复杂度：O(1)。

为什么这里要强调输入范围

Python 的负整数使用概念上的无限符号扩展。对负数不断执行这个循环，不会像有限宽度无符号整数一样自然变成 0。

本题输入是正整数，因此最终代码不需要额外的位宽掩码。若工程输入允许负数，必须先明确 32 位还是 64 位表示，再在边界处进行相应归一化。

常见错误

1. 只背公式，不知道删掉了什么

n & (n - 1) 的关键不是“结果更小”，而是它恰好删除最低位的一个 1。

2. 忘记更新 count

修改 n 只是在删除位；必须同时记录删除次数。

3. 对负数直接套用 Python 循环

这超出了题目输入域，并可能导致循环无法按预期结束。

4. 把逐位右移说成错误方法

右移版本是正确 baseline，只是它的循环次数取决于总位数。优化来自跳过零位，不是修复错误答案。

小结

这道题的推导路线是：

人工数二进制中的 1
-> 用 n & 1 读取最低位并右移
-> 发现零位也会消耗循环
-> 用 n & (n - 1) 每次删除一个 1
-> 删除次数就是答案

下一题 LeetCode 338 Counting Bits 会把这个单个整数的过程扩展到 0..n，并进一步消除不同数字之间的重复计算。