LeetCode 338简单动态规划 · 位运算
比特位计数 图解题解
这道题到底在问什么
给你一个整数 n，对于 0 ≤ i ≤ n 中的每个 i，计算其二进制表示中 1 的个数，返回一个长度为 n + 1 的数组 ans 作为答案。要求在线性时间内完成，且不使用内置 bit count 函数。
- 输入
- n = 2
- 输出
- [0,1,1]
- 输入
- n = 5
- 输出
- [0,1,1,2,1,2]
最优解：一步一步想明白
- 3对每个 i 都循环数二进制位或调内置函数，能出答案，却把已经算过的小数字白白浪费了。
- 4i 右移一位去掉 i 的最低位，看最低位是不是 1，于是 ans[i] = ans[i 右移一位] + 最低位，每格都依赖更小的格子。
- 5ans = [0] * (n + 1)0 的二进制没有 1，所以边界 ans[0]=0。
- 6i = 1数字 1 的二进制是 1，去掉最低位后是 0，再加上最低位 1。
- 7i = 22 的二进制是 10，去掉最低位变成 1，最低位本身不是 1。
- 8i = 33 的二进制是 11，比 1 多一个最低位 1，所以答案是 2。
- 9i = 44 的二进制是 100，去掉最低位是 10，1 的数量不变。
- 10i = 55 的二进制是 101，等于 2 的答案再加最低位的 1。整张表填法都来自同一行代码：ans[i] = ans[i 右移一位] + 最低位，没有任何字符串转换。
- 11如果先填 ans[5]…假设倒着从大往小填：算 ans[5] 时要读依赖格 ans[2]（标蓝），但它还没算、是个空格，公式直接崩。这就是为什么必须从小到大。
- 12for i in range(1, n + 1)正着从 1 往后填：依赖格（i 右移一位）一定小于 i，轮到 ans[i] 时它早已算好（标绿），整张表一遍填满。
- 13return ans样例 n=5 的输出就是整张表。
- 16位运算 DP 的通用套路：把当前数字拆成右移后的更小数字，加上最低位是不是 1。看懂「右移去最低位」和「按位与取最低位」后，很多计数位题都会变直观。
- 23同一类骨架，三道往上爬：191 位1的个数是单个数的版本、338 比特位计数是 0..n 的批量版、把右移换成
i 按位与 (i-1)又是去最高位 1 的变体——三题共用「子问题答案 + 本位贡献」一套思路。想系统刷这一类，去纯 LeetCode 专题页 位运算/DP 专题 接着练；哪一步卡住，直接问小欧 AI 私教，或进「通关训练」按题闯关。
⚠️ 容易写错的地方
✗ 错：对每个 i 调用 bin(i).count("1")
✓ 对：用递推公式填表
题目进阶要求不用内置函数，并做到线性扫描。
✗ 错：依赖 ans[i - 1]
✓ 对：依赖 ans[i 右移一位]
i-1 和 i 的二进制变化不稳定，右移才是稳定去掉最低位。
✗ 错：忘记 ans 长度是 n+1
✓ 对：初始化 [0]*(n+1)
题目要求包含 0 到 n。
完整代码（Python / C++ / Java）
Python
class Solution:
def countBits(self, n):
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i >> 1] + (i & 1)
return ansC++
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans(n + 1);
for (int i = 1; i <= n; i++) {
ans[i] = ans[i >> 1] + (i & 1);
}
return ans;
}
};Java
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 1; i <= n; i++) {
ans[i] = ans[i >> 1] + (i & 1);
}
return ans;
}
}套路模板：位运算递推骨架
# 位运算 DP 三步骨架（拿去套同类题）
ans = [0] * (n + 1) # 1. 开表，定边界 ans[0]
for i in range(1, n + 1): # 2. 从小到大填
smaller = i >> 1 # 去掉最低位 -> 更小、已算过的数
bit = i & 1 # 本位贡献：最低位是不是 1
ans[i] = ans[smaller] + bit # 3. 子问题答案 + 本位贡献
return ans// 位运算 DP 三步骨架（拿去套同类题）
vector<int> ans(n + 1, 0); // 1. 开表，定边界 ans[0]
for (int i = 1; i <= n; i++) { // 2. 从小到大填
int smaller = i >> 1; // 去掉最低位 -> 已算过的数
int bit = i & 1; // 本位贡献
ans[i] = ans[smaller] + bit; // 3. 子问题 + 本位
}
return ans;// 位运算 DP 三步骨架（拿去套同类题）
int[] ans = new int[n + 1]; // 1. 开表，边界 ans[0]=0
for (int i = 1; i <= n; i++) { // 2. 从小到大填
int smaller = i >> 1; // 去掉最低位 -> 已算过的数
int bit = i & 1; // 本位贡献
ans[i] = ans[smaller] + bit; // 3. 子问题 + 本位
}
return ans;复杂度
时间复杂度
O(n)
从 1 填到 n，每个 i 只做一次右移和按位与，共 n 步。
空间复杂度
O(n)
除返回数组外没有额外结构；答案数组本身必须存 n+1 个数。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 比特位计数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
状态定义是什么？+
ans[i] 表示整数 i 的二进制中 1 的个数。
转移为什么成立？+
i 右移一位去掉最低位，再补回最低位是否为 1。
为什么从 1 开始、从小到大？+
ans[0]=0 是地基；又因 i 右移一位小于 i，正序填能保证依赖格已算好。
还有别的递推式吗？+
有。ans[i] = ans[i 与上 (i-1)] + 1，「i 按位与 (i-1)」去掉最低位的那个 1，等价且也是 O(n)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。