LeetCode 191简单位运算
位 1 的个数 图解题解
这道题到底在问什么
计算整数二进制表示里 1 的个数。
- 示例
- n=1011₂ → 3
最优解：一步一步想明白
- 3逐位除 2 可以做，但不如直接利用位运算。
- 4n & (n-1) 会把最低位的 1 清零，循环几次就有几个 1。
- 5数 n 里有几个 1。诀窍：n & (n−1) 每做一次，就清掉最低位的一个 1；做了几次，就有几个 1。绿色是当前的 1。
- 61011 & 1010 = 1010：最低位(最右)的 1 被清成 0，其余不变。计数 1。
- 71010 & 1001 = 1000：当前最低位的 1 又被清掉。计数 2。
- 81000 & 0111 = 0000：最后一个 1 清掉，n 变 0。计数 3。
- 9关键帧：为什么 n & (n−1) 清的恰是最低位的 1？n−1 会把最低位的 1 变 0、它右边的 0 全变 1，左边不变；和 n 相与，那个最低位 1 被抹掉、其余原样。n 变 0 时停，做的次数 = 1 的个数 = 3。
- 12一句话记住：n & (n-1) 会把最低位的 1 清零，循环几次就有几个 1。
- 21这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=bit 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
⚠️ 容易写错的地方
✗ 错：Java 用 n ＞＞ 1 逐位扫
✓ 对：用 n & (n−1) 或无符号右移 ＞＞＞
有符号右移对负数高位补 1，会死循环或多算。
✗ 错：以为必须扫满 32 位
✓ 对：n&(n−1) 只循环「1 的个数」次
每次清掉一个 1、没有 1 就停，比逐位扫快。
✗ 错：写成 n & (n+1)
✓ 对：是 n & (n−1)
只有 n−1 才能把最低位 1 变 0、其右变 1，从而抹掉那个 1。
完整代码（Python / C++ / Java）
Python
class Solution:
def hammingWeight(self, n):
ans = 0
while n:
n &= n - 1
ans += 1
return ansC++
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
while (n) {
n &= n - 1;
ans++;
}
return ans;
}
};Java
public class Solution {
public int hammingWeight(int n) {
int ans = 0;
while (n != 0) {
n &= n - 1;
ans++;
}
return ans;
}
}套路模板 · Brian Kernighan
# 数 1 个数骨架 · 每次清最低位 1
ans = 0
while n:
n &= n - 1 # 清掉最低位的一个 1
ans += 1
return ans # 循环次数 = 1 的个数复杂度
时间复杂度
O(1)
最多 32 位，循环次数 = 1 的个数 ≤ 32
空间复杂度
O(1)
只用一个计数器
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 位 1 的个数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心技巧是什么？+
n & (n−1) 每次清掉最低位的一个 1；循环到 n 为 0，循环次数就是 1 的个数。
这道题为什么用「位运算」，换最直接的暴力解会差在哪？+
位运算抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。