LeetCode 第 338 题：比特位计数（Counting Bits） 题目描述 给定一个非负整数 n ，要求计算从 0 到 n 的每个整数的二进制表示中 1 的个数，返回一个长度为 n + 1 的数组，其中第 i 个元素是 i 的二进制中 1 的个数。 示例 输入： n = 2 输出： [0,1,1] 解释： 0 → "0" → 0 个 1 1 → "1" → 1 个 1 2 → "10" → 1 个 1 解题思路 暴力法（直接计算） 遍历 0 到 n ，对每个数直接计算其二进制中 1 的个数（例如通过不断除以 2 统计余数 1 的个数）。 时间复杂度：O(n log n)，适用于小范围数据，但存在重复计算。 动态规划（利用已知结果） 核心思想：利用已计算的结果来推导新数的结果，避免重复计算。 关键观察： 最高有效位 ：对于一个数 i ，如果它等于 2 的幂（如 1, 2, 4, 8...），则其二进制中 1 的个数为 1。 递推关系 ：若 i 不是 2 的幂，可以通过 i = 最高有效位 + 剩余部分 来分解。例如： 5 = 4 + 1 → count(5) = count(1) + count(1) = 2 更通用地： count(i) = count(i - highestPower) + 1 ，其中 highestPower 是小于等于 i 的最大 2 的幂。 动态规划优化（位运算技巧） 更高效的递推： count(i) = count(i >> 1) + (i & 1) i >> 1 是 i 右移一位（即除以 2），相当于去掉最低位。 i & 1 是取最低位，若为 1 则加 1，否则加 0。 例如： 5 的二进制是 101 ， count(5) = count(2) + 1 = 1 + 1 = 2 2 的二进制是 10 ， count(2) = count(1) + 0 = 1 + 0 = 1 步骤详解 初始化数组 创建长度为 n+1 的数组 dp ， dp[0] = 0 （0 的二进制没有 1）。 遍历计算 从 i = 1 到 n ，根据递推公式计算： dp[i] = dp[i >> 1] + (i & 1) 示例演算（n=5） i=1 : dp[1] = dp[0] + 1 = 0 + 1 = 1 i=2 : dp[2] = dp[1] + 0 = 1 + 0 = 1 i=3 : dp[3] = dp[1] + 1 = 1 + 1 = 2 i=4 : dp[4] = dp[2] + 0 = 1 + 0 = 1 i=5 : dp[5] = dp[2] + 1 = 1 + 1 = 2 结果： [0,1,1,2,1,2] 复杂度分析 时间复杂度：O(n)，每个数只需一次计算。 空间复杂度：O(n)，用于存储结果数组。 总结 通过动态规划和位运算技巧，将问题转化为利用已计算结果的递推，显著提升效率。此方法既避免了重复计算，又保持了代码简洁性。