好的，我们接下来讲解 LeetCode 第 338 题「比特位计数」。

题目描述

给你一个整数 n，对于 0 <= i <= n 中的每个 i，计算其二进制表示中 1 的个数，并返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

要求：

• 时间复杂度 O(n)
• 空间复杂度 O(n)（不算返回数组）
• 不能使用内置函数直接计算每个数的二进制中 1 的个数（如 Integer.bitCount）

解题思路

第一步：暴力解法（不符合要求）

最直接的方法是遍历 0 到 n，对每个数用循环计算二进制中 1 的个数（不断除以 2 或右移位，统计 1 的个数）。
这种方法的时间复杂度是 O(n log n)（每个数最多 log n 位），不满足 O(n) 的要求。

第二步：动态规划 + 最高有效位（Most Significant Bit, MSB）

我们想要 O(n) 的解法，必须利用已经计算过的结果，避免重复计算。
观察二进制数的规律：

• 如果一个数 i 是 2 的幂（如 1, 2, 4, 8...），那么它的二进制只有一个 1，且 bits[i] = 1。
• 对于任意数 i，我们可以找到小于等于 i 的最大的 2 的幂 2^k，那么 i 可以表示为：

  i = 2^k + j
  

  其中 0 <= j < 2^k。

那么 bits[i] = 1 + bits[j]，因为 2^k 贡献了一个 1，剩下的 j 部分我们之前已经计算过。

例子：

• n = 5
  • 0 → 0
  • 1 (2^0) → bits[1] = 1
  • 2 (2^1) → bits[2] = 1
  • 3 = 2 + 1 → bits[3] = 1 + bits[1] = 2
  • 4 (2^2) → bits[4] = 1
  • 5 = 4 + 1 → bits[5] = 1 + bits[1] = 2

实现步骤：

1. 初始化 bits[0] = 0。
2. 维护一个变量 highBit 表示当前最大的 2 的幂。
3. 遍历 i 从 1 到 n：
   • 如果 i & (i - 1) == 0，说明 i 是 2 的幂，更新 highBit = i。
   • bits[i] = 1 + bits[i - highBit]。

第三步：动态规划 + 最低有效位（Least Significant Bit, LSB）

另一种思路：
对于数 i，将其右移一位得到 i >> 1，这个数的 1 的个数已经计算过。
然后看 i 的最低位是否是 1：

bits[i] = bits[i >> 1] + (i & 1)

因为右移一位相当于去掉最低位，剩下的部分就是 i >> 1 的 1 的个数，再加上最低位是否是 1。

例子：

• i = 5（二进制 101）
  • 5 >> 1 = 2（二进制 10） → bits[2] = 1
  • 5 & 1 = 1
  • bits[5] = 1 + 1 = 2

实现步骤：

1. bits[0] = 0
2. 从 i = 1 到 n：
   • bits[i] = bits[i >> 1] + (i & 1)

这种方法更简洁，且同样 O(n) 时间。

第四步：动态规划 + 最低设置位（Lowest Set Bit）

还可以利用 i & (i - 1) 去掉最低位的 1 的性质：
i & (i - 1) 比 i 少一个 1，且这个结果小于 i，已经计算过。
所以：

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

例子：

• i = 5（二进制 101）
  • 5 & 4 = 4（二进制 100） → bits[4] = 1
  • bits[5] = 1 + 1 = 2

实现步骤：

1. bits[0] = 0
2. 从 i = 1 到 n：
   • bits[i] = bits[i & (i - 1)] + 1

最终代码（以方法三为例，最简洁）

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i & (i - 1)] + 1;
        }
        return bits;
    }
}

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)（不算返回数组）

总结

这道题利用了二进制数的递推性质，通过动态规划避免重复计算，实现了 O(n) 的解法。
三种方法都可行，方法三（最低设置位）代码最简洁。