338. 比特位计数（Counting Bits）
频次 ★★★ · 难度 🟢 · 高频：美团
题目
返回 0~n 每个数的二进制表示中 1 的个数。
思路
DP：count[i] = count[i >> 1] + (i & 1)。i 右移一位的 1 的个数 + 最低位是否为 1。
代码
public int[] countBits(int n) {
int[] res = new int[n + 1];
for (int i = 1; i <= n; i++) {
res[i] = res[i >> 1] + (i & 1);
}
return res;
}复杂度
- 时间：O(n)
- 空间：O(n)
边界条件
n == 0：返回[0]。循环从i = 1开始，res[0]保持默认值 0，天然正确- 数组开
n+1：要包含n本身 i >> 1 < i恒成立（i ≥ 1），所以res[i >> 1]一定已经算过——这是 DP 无后效性的保证- 全程非负，不涉及
>>与>>>之争
变式
- 递推式换成
res[i] = res[i & (i - 1)] + 1：i & (i-1)消掉最低位的 1，所以比它多一个 1。同样 O(n) - 递推式换成
res[i] = res[i - lowbit(i)] + 1：lowbit(i) = i & -i，等价形式 - 461. 汉明距离：单个数的 1 的个数，不需要 DP
- 求 0~n 中二进制含偶数个 1 的数的个数：先算
res[]再统计奇偶
易错点
res[i >> 1] + (i & 1)的两部分含义要分清：右移丢掉的是最低位，所以补回来的也是最低位i & 1。写成res[i >> 1] + 1就错了（偶数的最低位是 0）- 循环必须从 1 开始。从 0 开始会算
res[0] = res[0] + 0，虽然结果对，但逻辑上是自引用 - 运算符优先级：
res[i >> 1] + (i & 1)里的括号不能省，&的优先级低于+ - 别写成
Integer.bitCount(i)逐个算——那是 O(n × 32)，丢掉了本题「复用子问题」的全部考点
面试追问
- 这题为什么算 DP 而不是位运算技巧：因为它的核心是复用已算出的子结果。
i的 1 的个数 =i >> 1的 1 的个数 + 最低位。i >> 1是一个更小的、已经解决的子问题——这就是重叠子问题 + 最优子结构，见动态规划与贪心。位运算只是转移方程的表达形式。 - 三个递推式（
i>>1、i&(i-1)、i-lowbit(i)）哪个好：复杂度都是 O(n)。i >> 1最直观；i & (i-1)揭示的是「消掉一个 1」这个更本质的操作，和 Brian Kernighan 算法同源。面试时能说出两种，比只会一种有区分度。 - 能不能做到 O(n) 时间且不用额外数组：不能——输出本身就是长度 n+1 的数组，O(n) 空间是下界。
- 为什么不直接调
Integer.bitCount：单次是 O(1)（POPCNT指令），n 次就是 O(n)，复杂度其实一样。但这题考的是「发现子问题重叠」这件事，用库函数就没有子问题了。