比特位计数 图解题解

比特位计数在问什么

给一个整数 n，要求返回长度为 n+1 的数组，第 i 个元素是 i 的二进制表示里 1 的个数（0 ≤ i ≤ n）。比如 n = 10 时答案是 [0,1,1,2,1,2,2,3,1,2,2]。单独数一个数的 1 谁都会，这道题的考点是：要一口气数 0 到 n 全部的数，能不能让后面的数「白拿」前面已经算好的结果。

为什么逐个数各自数一遍还不够好

直觉解是对每个 i 独立做一次位计数（逐位右移或 Kernighan 消 1），每个数要 O(log i) 步，总共 O(n log n)。慢的根源是重复劳动：数 6（二进制 110）的时候，其实把 3（二进制 11）的 1 又数了一遍——6 的高位部分就是 3。

关键观察由此浮出来：任何数 i 右移一位（i >> 1，即抹掉最低位）得到的那个数比 i 小，它的答案在从小到大填表时早就算好了。i 和 i >> 1 的二进制只差最低那一位，这一位是不是 1，用 i & 1 一步就能测出来。既然大问题的答案等于「已解决的小问题 + 常数补充」，动态规划的结构就齐了。

dp 数组的定义和转移方程为什么成立

定义 dp[i] = 数 i 的二进制中 1 的个数，下标直接就是数值本身，dp[0] = 0 是地基。转移方程 dp[i] = dp[i >> 1] + (i & 1)：i 的全部 1 分成两部分——高位部分（就是 i >> 1 的二进制）的 1，加上最低位可能贡献的那一个。偶数最低位是 0，答案与 dp[i >> 1] 相同；奇数最低位是 1，再加一。

正确性的依据是无后效性：i >> 1 严格小于 i（i ≥ 1 时），按 i 从 1 到 n 顺序填表，转移用到的那格永远已经填好，绝无循环依赖。拿 10 验证：10 是 1010，10 >> 1 = 5（101），dp[5] = 2，10 是偶数不加，dp[10] = 2，正确。

另一种转移 dp[i & (i-1)] + 1 是什么原理

同样 O(n) 的还有一种写法：dp[i] = dp[i & (i - 1)] + 1。i & (i - 1) 会精确抹掉 i 最低位的那个 1，所以它的 1 比 i 恰好少一个，且这个数也比 i 小、已经算好。两种转移都体现同一个思想——从 i 身上剥掉一小块位结构，剩下的部分复用已有答案。面试里能随手写出任意一种并解释另一种，位运算功底就立住了。

复杂度与两个容易踩的坑

时间 O(n)：n+1 个数每个只做一次右移、一次按位与、一次加法，全是 O(1)。空间上答案数组本身 O(n) 是题目要求的输出，额外空间只有循环变量，O(1)。

两个高频错误：一是把转移里的 i >> 1 顺手写成 i - 1——这道题依赖的是「去掉最低位」的位结构关系，不是「前一个数」的算术关系，i - 1 的 1 的个数和 i 没有固定加减规律；二是数组长度开成 n，忘了答案要覆盖 0 到 n 共 n+1 个数，最后一格越界或缺失。

Python

def countBits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

C++

vector<int> countBits(int n){
    vector<int> dp(n + 1, 0);
    for(int i = 1; i <= n; ++i)
        dp[i] = dp[i >> 1] + (i & 1);
    return dp;
}

Java

int[] countBits(int n){
    int[] dp = new int[n + 1];
    for(int i = 1; i <= n; i++)
        dp[i] = dp[i >> 1] + (i & 1);
    return dp;
}