位 1 的个数 图解题解
这道题到底在问什么
- 输入
- n = 11（二进制 1011）
- 输出
- 3
- 输入
- n = 128（二进制 10000000）
- 输出
- 1
最优解：一步一步想明白
- 3记住这句「n & (n-1) 消掉最低位的 1」，下面每一帧都在套它——而且循环次数 = 1 的个数，不是 32 位逐位扫。
- 4间隔分布的 6 个 1，最能看清「每次只灭最右边那个 1、范围逐步左收」。
- 5先把 n = 2730 摊成 12 位。亮着的格子是 1、暗的是 0。接下来每按一次 n&(n-1)，就灭掉最右边那个 1。
- 6当前 n = 2730。n−1 会把「最低位这个 1」借成 0、它右边的 0 全变 1；再和 n 按位与，正好只把这一位清零，其余不动。
- 7那一位已变 0（绿色记一笔），计数 +1 = 1。n 还剩 2728，继续消下一个最低位的 1。
- 8当前 n = 2728。n−1 会把「最低位这个 1」借成 0、它右边的 0 全变 1；再和 n 按位与，正好只把这一位清零，其余不动。
- 9那一位已变 0（绿色记一笔），计数 +1 = 2。n 还剩 2720，继续消下一个最低位的 1。
- 10当前 n = 2720。n−1 会把「最低位这个 1」借成 0、它右边的 0 全变 1；再和 n 按位与，正好只把这一位清零，其余不动。
- 11那一位已变 0（绿色记一笔），计数 +1 = 3。n 还剩 2688，继续消下一个最低位的 1。
- 12当前 n = 2688。n−1 会把「最低位这个 1」借成 0、它右边的 0 全变 1；再和 n 按位与，正好只把这一位清零，其余不动。
- 13那一位已变 0（绿色记一笔），计数 +1 = 4。n 还剩 2560，继续消下一个最低位的 1。
- 14当前 n = 2560。n−1 会把「最低位这个 1」借成 0、它右边的 0 全变 1；再和 n 按位与，正好只把这一位清零，其余不动。
- 15那一位已变 0（绿色记一笔），计数 +1 = 5。n 还剩 2048，继续消下一个最低位的 1。
- 16当前 n = 2048。n−1 会把「最低位这个 1」借成 0、它右边的 0 全变 1；再和 n 按位与，正好只把这一位清零，其余不动。
- 17这一位灭掉后 n 变成 0，循环结束。一共消了 6 次，就是 6 个 1。
- 18所有 1 都被消光、n 归 0。绿格子就是当初的每个 1。注意循环只跑了 6 次（= 1 的个数），不是把 12 位逐个看一遍。
- 19相邻的 1 也不例外：n−1 只动「最低那一个 1」及其右边，左边的 1 纹丝不动。
- 20先把 n = 7 摊成 12 位。亮着的格子是 1、暗的是 0。接下来每按一次 n&(n-1)，就灭掉最右边那个 1。
- 21当前 n = 7。n−1 会把「最低位这个 1」借成 0、它右边的 0 全变 1；再和 n 按位与，正好只把这一位清零，其余不动。
- 22那一位已变 0（绿色记一笔），计数 +1 = 1。n 还剩 6，继续消下一个最低位的 1。
- 23当前 n = 6。n−1 会把「最低位这个 1」借成 0、它右边的 0 全变 1；再和 n 按位与，正好只把这一位清零，其余不动。
- 24那一位已变 0（绿色记一笔），计数 +1 = 2。n 还剩 4，继续消下一个最低位的 1。
- 25当前 n = 4。n−1 会把「最低位这个 1」借成 0、它右边的 0 全变 1；再和 n 按位与，正好只把这一位清零，其余不动。
- 26这一位灭掉后 n 变成 0，循环结束。一共消了 3 次，就是 3 个 1。
- 27所有 1 都被消光、n 归 0。绿格子就是当初的每个 1。注意循环只跑了 3 次（= 1 的个数），不是把 12 位逐个看一遍。
⚠️ 容易写错的地方
✗ 错：n = n & (n - 1) 写成 n = n & (n + 1)
✓ 对：n & (n - 1)
n+1 抹的是最低位的 0、还会进位，消不掉 1，方向反了
✗ 错：while (n > 0)（带符号 + 负数）
✓ 对：while (n != 0)
若 n 为负数（最高符号位是 1），n>0 会直接跳过、漏数符号位的 1，要用 != 0
✗ 错：右移用 n >>= 1 逐位扫但忘了无符号
✓ 对：n >>>= 1（或本法 n&(n-1)）
带符号右移会补符号位 1，对负数死循环；本法天然回避了符号问题
完整代码（Python / C++ / Java）
Python
def hammingWeight(n: int) -> int:
count = 0
while n != 0:
n &= n - 1 # 抹掉最低位的 1
count += 1 # 抹一次就数一个
return countC++
int hammingWeight(uint32_t n) {
int count = 0;
while (n != 0) {
n &= n - 1; // 抹掉最低位的 1
count++; // 抹一次就数一个
}
return count;
}Java
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n = n & (n - 1); // 抹掉最低位的 1
count++; // 抹一次就数一个
}
return count;
}复杂度
时间
O(k)
k = 1 的个数；循环只跑「1 的个数」次，而非位宽次
空间
O(1)
只用 n 和 count 两个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 位 1 的个数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么 n & (n - 1) 能恰好消掉最低位的 1？+
设 n 最低位的 1 在第 k 位，那么它右边全是 0。n-1 会向这一位借位：第 k 位由 1 变 0，第 k 位右边的 0 全部变 1，比 k 高的位保持不变。再做 n &(n-1)：第 k 位 1&0=0 被清掉，更高位与自身相与不变，更低位 0&1=0 仍是 0。于是只有最低位那个 1 被抹掉。
这个方法比「逐位 &1 右移」好在哪？+
逐位法要循环「位宽」次（如 32 次），不管有几个 1。n&(n-1) 只循环「1 的个数」次——1 很稀疏时快得多，最坏（全 1）才退化到位宽次，平均更优，且天然不踩负数右移补符号位的坑。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 位 1 的个数 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。