比特位计数：如何求 0 到 n 每个数的 1 的个数？（LeetCode 338）

简化版

给整数 n，返回一个长度 n+1 的数组 ans，ans[i] 是 i 的二进制中 1 的个数。逐个用 Integer.bitCount 是 O(n log n)，但用动态规划能做到 O(n)：利用已算出的较小数的结果递推。两个经典递推式：① dp[i] = dp[i >> 1] + (i & 1)（i 去掉最低位后 1 的个数，再加回最低位）；② dp[i] = dp[i & (i - 1)] + 1（消掉一个最低位的 1 后，再 +1）。

详细版

递推一：dp[i] = dp[i >> 1] + (i & 1)

int[] countBits(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);   // i 右移一位的 1 的个数，加上被移掉的最低位
    }
    return dp;                            // dp[0] = 0 默认
}

递推二：dp[i] = dp[i & (i - 1)] + 1

int[] countBits(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i & (i - 1)] + 1;    // 消掉最低位的 1 后 + 1
    }
    return dp;
}

核心：i 的 1 的个数可由「更小的、已算过的数」推出，避免重复逐位数。
递推一：i >> 1 是 i 去掉最低位（右移），其 1 的个数已知；i & 1 补回最低位是 0 还是 1。
递推二：i & (i-1) 是 i 消掉一个 1 后的数（更小、已知），其 1 的个数 +1 即 i 的。
复杂度：O(n) 时间、O(n) 空间（输出数组）。

完整版教学

一、朴素解法及其瓶颈

最直接：对 0..n 每个数单独用「数 1」的方法（如 n & (n-1) 消 1）统计。每个数 O(log n)，总共 O(n log n)。题目通常要求 O(n)——这就得靠动态规划，用小数的答案推大数，避免每个数从头数。

二、递推一：右移一位 `dp[i] = dp[i >> 1] + (i & 1)`

观察：把 i 的二进制右移一位（i >> 1），相当于去掉了 i 的最低位。那么：

i >> 1 的 1 的个数 = i 除最低位外的 1 的个数——这个值 i>>1 < i，已经算过，直接查 dp[i >> 1]。
再看被移掉的最低位：i & 1 是 0 或 1，正是要补回的那一位。

所以 dp[i] = dp[i >> 1] + (i & 1)。例：i = 6 = 110，i>>1 = 3 = 11（有 2 个 1），i & 1 = 0，dp[6] = 2 + 0 = 2。✔

直觉：i >> 1 是「i 砍掉个位」，i & 1 是「个位是几」，两者相加就是 i 的总 1 数。这是奇偶 + 折半的思路。

三、递推二：消一个 1 `dp[i] = dp[i & (i - 1)] + 1`

另一条基于 n & (n-1) 消 1 的性质：i & (i - 1) 把 i 最低位的 1 消成 0，得到一个更小的数，它的 1 的个数比 i 少 1，且已算过。所以：

dp[i] = dp[i & (i - 1)] + 1

例：i = 6 = 110，i & (i-1) = 110 & 101 = 100 = 4（有 1 个 1），dp[6] = dp[4] + 1 = 1 + 1 = 2。✔

直觉：i 比「消掉它一个 1 之后的数」恰好多 1 个 1，那个数更小、已知，+1 即可。

四、两条递推的对比

	递推一 `dp[i>>1]+(i&1)`	递推二 `dp[i&(i-1)]+1`
思路	折半 + 看最低位奇偶	消掉一个最低位的 1
依赖的子问题	`i >> 1`（约 i/2）	`i & (i-1)`（去一个 1）
都满足	`dp[0]=0` 起手、O(n)	同

两条都对、都 O(n)，任选其一记住即可。递推一更好背（右移看奇偶），递推二体现 n&(n-1) 的威力。关键都是「i 的答案依赖一个比它小、已算过的数」——这正是 DP 的精髓：无后效性 + 子问题重叠。

五、为什么这是「动态规划」

状态：dp[i] = i 的 1 的个数。
转移：dp[i] 由更小的 dp[i>>1] 或 dp[i&(i-1)] 推出。
无后效性：i 只依赖更小的下标，从小到大填表天然满足。
子问题重叠：很多大数复用同一个小数的结果（如所有偶数 i 都用 dp[i/2]），省去重复计算——这就是比逐个数快的原因。

六、把递推表完整推到 n=8

递推成立的前提是依赖下标严格小于当前 i，所以从 1 到 n 填表时子问题一定已经算好。以 dp[i]=dp[i>>1]+(i&1) 为例，偶数末位为 0，答案等于折半后的答案；奇数末位为 1，比折半后的答案恰好多 1。

i        0  1  2  3  4  5  6  7  8
binary 000 001 010 011 100 101 110 111 1000
i >> 1  0  0  1  1  2  2  3  3  4
i & 1   0  1  0  1  0  1  0  1  0
dp[i]   0  1  1  2  1  2  2  3  1
例如 dp[7]=dp[3]+1=2+1=3

校验维度	本题必须保持的结论
循环/递推不变量	处理 i 时 `dp[0..i-1]` 已正确，且转移只读取其中一个更小下标。
边界条件	`n=0` 时输出只含 `dp[0]=0`；输出数组本身要求 O(n) 空间，不能声称总空间 O(1)。
复杂度与代价	每个 i 做常数次位操作，时间 O(n)，额外工作空间 O(1)，输出空间 O(n)。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

位运算题的代码通常很短，真正容易错的是把数学整数、固定宽度位模式和语言移位规则混在一起。本题应先复述这条不变量：处理 i 时 dp[0..i-1] 已正确，且转移只读取其中一个更小下标。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“i 0 1 2 3 4 5 6 7 8”开始手推，最后应得到“例如 dp[7]=dp[3]+1=2+1=3”。
边界复核：n=0 时输出只含 dp[0]=0；输出数组本身要求 O(n) 空间，不能声称总空间 O(1)。
代价复核：每个 i 做常数次位操作，时间 O(n)，额外工作空间 O(1)，输出空间 O(n)。
用全 0、只有一个 1、最高位为 1 三类位模式检查掩码。
涉及负数时把值写成固定宽度补码，确认使用 >> 还是 >>>。
涉及左移时检查移位距离和溢出后是否仍符合题目的位模式语义。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“处理 i 时 dp[0..i-1] 已正确，且转移只读取其中一个更小下标。”这条正确性主线不能省。

八、常见误区与追问

误区：调用 n 次 bitCount 也是 O(n)。 按位模型下每次统计需要 O(log n) 或固定机器字宽工作，题目想考的是跨数字复用。
误区：dp[i&(i-1)] 可能引用尚未计算的状态。 i&(i-1) 清掉一个 1 后严格小于正整数 i，所以从小到大遍历安全。
误区：递推数组可以不初始化 dp[0]。 Java 默认值恰好是 0；换到没有零初始化保证的环境应显式设置。
追问：两条递推哪条更快？ 二者每个状态都是常数操作，渐进复杂度相同，选择更易解释的一条即可。
追问：能否只返回 n 的比特数并省掉数组？ 可以，但那已变成单个数的汉明重量，不再满足返回 0..n 全部答案的题意。
追问：为什么这算动态规划？ 状态按下标复用更小状态，存在明确初值、转移和遍历依赖顺序。

九、加强记忆

比特位计数（求 0..n 每个数的 1 的个数）= DP 递推，O(n)（优于逐个数的 O(n log n)）。两条递推任选：① dp[i] = dp[i >> 1] + (i & 1)（i 折半的 1 数 + 最低位奇偶）；② dp[i] = dp[i & (i - 1)] + 1（消掉一个最低位的 1，那个更小的数 +1）。都以 dp[0]=0 起手、从小到大填。本质是「i 的答案依赖一个更小的、已算过的数」的动态规划。核心记一条：dp[i] = dp[i>>1] + (i&1)。

简化版

详细版