跳到主要内容

LeetCode 191. 位1的个数

本节目标

反复清除最低位的 1，用实际的置位数计算汉明重量。

这道题承接二进制与位运算基础：利用 n & (n - 1) 每次恰好删除一个最低位的 1，而不必逐位检查全部 32 位。

查看原题

题意与约束​

给定一个固定宽度的无符号 32 位整数 n，返回它的二进制表示中 1 的个数，也称为汉明重量（Hamming weight）。

  • 输入范围为 0 <= n <= 2^32 - 1。
  • C++ 的形参是 uint32_t，因此位宽和无符号语义由类型固定。
  • Python 的 int 没有固定 32 位；本题仍约定传入同一范围内的非负整数，把它看作一个 32 位无符号字。负数不是这个接口的有效输入。

n 与 n - 1 有什么变化​

当 n 不为 0 时，设它最低位的 1 右侧有若干个 0。n - 1 会把这个最低位的 1 变成 0，并把它右侧的所有 0 变成 1；更高位保持不变。

因此，再将两者按位与：更高位被保留，最低位的 1 被清掉，右侧位置本来就是 0，结果不会增加新的 1。这正是 n & (n - 1) 的效果。

每轮清除最低位的 1​

以 12 = 1100₂ 为例：

1100 & 1011 = 1000  （清除一个 1）
1000 & 0111 = 0000  （再清除一个 1）

每轮循环只会少一个 1，所以变量 count 的增加次数恰好等于原数中 1 的个数。输入为 0 时不进入循环，答案自然为 0。

代码实现​

两份源码都在每轮执行 n &= n - 1，再让 count 加一。Python 实现不额外掩码：在有效的非负 32 位输入范围内，清除操作本身会在有限轮后到达 0；若传入负数，Python 的无限位补码语义不符合本题约束。

C++17
#include <cstdint>

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n != 0) {
            n &= n - 1;
            count++;
        }
        return count;
    }
};

复杂度分析​

设 k 为 n 中 1 的个数。循环恰好执行 k 次，因此时间复杂度为 O(k)，在 32 位输入下 k <= 32。除计数器外不使用额外存储，空间复杂度为 O(1)。

易错点​

  • 把 n & (n - 1) 误认为“去掉最低位”：它只清除最低位的 1，不会移动其他位。
  • 对 n = 0 执行 n - 1 后再推导：循环前必须先保证 n != 0。
  • 在 C++ 中使用有符号整数：最高位为 1 时符号和移位相关的推理容易混乱，应使用 uint32_t 表示题目的无符号 32 位输入。
  • 让 Python 接收负数：Python 整数没有固定 32 位，负数的按位表示会导致本循环不能按本题的有限字长语义结束。

模式迁移​

当题目要求枚举、删除或统计一个数已经置位的 1 时，优先考虑 n & (n - 1)：它把工作量从固定的位宽缩到实际的置位数。若需要定位最低位的 1，可结合 n & -n；若必须检查每一位的贡献，再使用移位和掩码。