比特位计数

问题拆解

对 0 到 n 的每个整数，求其二进制表示中 1 的个数，返回长度为 n + 1 的数组。

逐个数字调用 Brian Kernighan 或者内置的 popcount 当然能过，时间是 O(n log n)。但题目进阶要求一次遍历 O(n)，这是在提示：这 n + 1 个答案之间有关系，不该各算各的。关系在哪？看 i 和 i >> 1：右移一位丢掉的只是最低位，剩下的高位部分与 i >> 1 一模一样。所以 i 的 1 的个数，等于 i >> 1 的 1 的个数，再加上被丢掉的那个最低位是不是 1——也就是 i & 1。

求一批数的答案时，先问“大数的答案能不能由小数的答案拼出来”——i >> 1 < i 恒成立，递推天然无后效性。

用已算出的答案递推

bits[0] = 0，从 1 开始正序填表，每个 bits[i] 只查一次表、做一次加法。

public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        bits[i] = bits[i >> 1] + (i & 1); // 高位部分 + 最低位
    }
    return bits;
}

def countBits(n: int) -> List[int]:
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)  # 高位部分 + 最低位
    return bits

func countBits(n int) []int {
    bits := make([]int, n+1)
    for i := 1; i <= n; i++ {
        bits[i] = bits[i>>1] + i&1 // 高位部分 + 最低位
    }
    return bits
}

pub fn count_bits(n: i32) -> Vec<i32> {
    let n = n as usize;
    let mut bits = vec![0; n + 1];
    for i in 1..=n {
        bits[i] = bits[i >> 1] + (i & 1) as i32; // 高位部分 + 最低位
    }
    bits
}

正序填表是安全的，因为 i >> 1 严格小于 i（i ≥ 1 时），查表时那一格一定已经算好。Java 里要留意运算符优先级：bits[i >> 1] + i & 1 会先加后与，必须给 (i & 1) 加括号；Go 的 & 优先级高于 +，反而可以不加，这类跨语言的优先级差异值得在写位运算时多看一眼。

另一条等价的递推是 bits[i] = bits[i & (i - 1)] + 1：i & (i - 1) 把 i 最低的一个 1 清零，得到的数同样比 i 小且已算好，个数恰好少 1。按最低位拆和按最低的 1 拆，殊途同归。

复杂度

可以迁移的模式

• 对一段连续整数批量求某种位属性，先找 i 与 i >> 1、i & (i - 1) 这类“更小的相关数”，让答案表自己递推自己；
• x & (x - 1) 清除最低位的 1、x & 1 取最低位，是位运算里出场率最高的两个原子操作；
• DP 的状态不一定来自题面定义，数值本身的二进制结构也能充当子问题。

把“每个数独立计算”换成“答案之间互相引用”，正是这题从 O(n log n) 到 O(n) 的全部秘密。