比特位计数

对每个 i 都循环数二进制位或调内置函数，能出答案，却把已经算过的小数字白白浪费了。

i 右移一位去掉 i 的最低位，看最低位是不是 1，于是 ans[i] = ans[i 右移一位] + 最低位，每格都依赖更小的格子。

定义状态：ans[i] 是 i 的二进制 1 的个数：0 的二进制没有 1，所以边界 ans[0]=0。

i=1：1 右移一位 = 0，最低位是 1：数字 1 的二进制是 1，去掉最低位后是 0，再加上最低位 1。

i=2：2 右移一位 = 1，最低位是 0：2 的二进制是 10，去掉最低位变成 1，最低位本身不是 1。

i=3：3 右移一位 = 1，最低位是 1：3 的二进制是 11，比 1 多一个最低位 1，所以答案是 2。

i=4：4 右移一位 = 2，最低位是 0：4 的二进制是 100，去掉最低位是 10，1 的数量不变。

i=5：5 右移一位 = 2，最低位是 1：5 的二进制是 101，等于 2 的答案再加最低位的 1。整张表填法都来自同一行代码：ans[i] = ans[i 右移一位] + 最低位，没有任何字符串转换。

反例：倒着填会读到空格：假设倒着从大往小填：算 ans[5] 时要读依赖格 ans[2]（标蓝），但它还没算、是个空格，公式直接崩。这就是为什么必须从小到大。

循环方向：从小到大：正着从 1 往后填：依赖格（i 右移一位）一定小于 i，轮到 ans[i] 时它早已算好（标绿），整张表一遍填满。

返回答案数组：样例 n=5 的输出就是整张表。

位运算 DP 的通用套路：把当前数字拆成右移后的更小数字，加上最低位是不是 1。看懂「右移去最低位」和「按位与取最低位」后，很多计数位题都会变直观。

边界三连：比特位计数 的边界先看最小规模、特殊输入和最容易触发分支的样例。

面试追问：比特位计数 的追问重点，是把状态定义、填表顺序和替代递推讲成自己的话。

迁移阶梯：同一类骨架，三道往上爬：191 位1的个数是单个数的版本、338 比特位计数是 0..n 的批量版、把右移换成 i 按位与 (i-1) 又是去最高位 1 的变体——三题共用「子问题答案 + 本位贡献」一套思路。想系统刷这一类，去纯 LeetCode 专题页 位运算/DP 专题 接着练；哪一步卡住，直接问小欧 AI 私教，或进「通关训练」按题闯关。