我来给你讲解 LeetCode 第 338 题「比特位计数」。

题目描述

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

示例 1：

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

示例 2：

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

解题思路

方法一：暴力解法（直接计算）

最直观的方法是对于每个数 i，直接计算其二进制中 1 的个数。

def countBits_naive(n):
    def count_ones(x):
        count = 0
        while x:
            count += x & 1  # 检查最低位是否为1
            x >>= 1         # 右移一位
        return count
    
    return [count_ones(i) for i in range(n + 1)]

时间复杂度： O(n log n)，因为每个数需要 O(log n) 时间来计算
空间复杂度： O(1)，不考虑输出数组

方法二：动态规划 + 最高有效位

观察二进制数的规律：

• 2的幂次方数（1, 2, 4, 8...）的二进制只有1个1
• 对于任意数 i，设最高有效位为 high_bit，则：
  count[i] = 1 + count[i - high_bit]

def countBits_highbit(n):
    result = [0] * (n + 1)
    high_bit = 0  # 当前最高有效位
    
    for i in range(1, n + 1):
        if i & (i - 1) == 0:  # 判断是否为2的幂
            high_bit = i
        result[i] = 1 + result[i - high_bit]
    
    return result

原理：

• 当 i 是 2 的幂时，i & (i-1) == 0
• 例如：i=4(100), high_bit=4, count[4] = 1 + count[0] = 1
• i=5(101), count[5] = 1 + count[1] = 1 + 1 = 2

方法三：动态规划 + 最低有效位

利用右移操作：count[i] = count[i >> 1] + (i & 1)

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

原理：

• i >> 1 相当于去掉最低位
• i & 1 检查最低位是否为1
• 例如：i=5(101)
  • i >> 1 = 2(10), count[2] = 1
  • i & 1 = 1
  • count[5] = 1 + 1 = 2

方法四：动态规划 + 最低设置位（最优解）

利用 i & (i-1) 可以去掉最低位的1的特性：
count[i] = count[i & (i-1)] + 1

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

原理：

• i & (i-1) 会去掉 i 的最低位的1
• 例如：i=5(101)
  • i & (i-1) = 5 & 4 = 101 & 100 = 100(4)
  • count[5] = count[4] + 1 = 1 + 1 = 2

复杂度分析

• 时间复杂度： O(n)，每个数只需要常数时间
• 空间复杂度： O(1)，不考虑输出数组

总结

这道题展示了动态规划在位运算中的巧妙应用。最优解利用了二进制数的特性，通过简单的位运算就能高效计算出结果。关键是要发现二进制数之间的递推关系，避免重复计算。