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

题目描述

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

示例：

输入：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

解题思路

方法一：暴力解法（直接计算每个数的二进制中 1 的个数）

def countBits(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) 时间计算 1 的个数。

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

观察二进制数的规律：

• 2 的幂次方的数只有一个 1（如 1, 2, 4, 8...）
• 对于任意数 i，如果知道 i 去掉最高位后的数的 1 的个数，那么 i 的 1 的个数就是去掉最高位后的数的 1 的个数加 1

具体步骤：

1. 初始化 dp[0] = 0
2. 维护一个变量 highBit 表示当前最高有效位
3. 对于每个 i：
   • 如果 i 是 2 的幂（即 i & (i-1) == 0），更新 highBit = i
   • dp[i] = dp[i - highBit] + 1

def countBits(n):
    dp = [0] * (n + 1)
    highBit = 0  # 当前最高有效位
    
    for i in range(1, n + 1):
        if i & (i - 1) == 0:  # 检查是否是2的幂
            highBit = i
        dp[i] = dp[i - highBit] + 1
    
    return dp

方法三：动态规划 + 最低有效位（更优雅的解法）

利用位运算的性质：i & (i-1) 可以去掉 i 的最低位的 1。

递推关系： dp[i] = dp[i & (i-1)] + 1

解释：

• i & (i-1) 的结果是去掉 i 的最低位的 1
• 这个数的 1 的个数我们已经计算过了
• i 的 1 的个数就是去掉最低位 1 后的数的 1 的个数加 1

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

方法四：动态规划 + 右移位

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

解释：

• i >> 1 相当于 i 除以 2（去掉最低位）
• i & 1 检查 i 的最低位是否为 1
• i 的 1 的个数等于 i/2 的 1 的个数加上最低位是否为 1

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

复杂度分析

• 时间复杂度： O(n)
• 空间复杂度： O(n)（存储结果数组）

总结

这道题展示了动态规划在位运算问题中的巧妙应用。最优解法利用了二进制数的数学性质，通过简单的位运算实现了高效计算。方法三（i & (i-1)）和方法四（右移位）是最常用的两种实现方式，理解其中的数学原理对于解决类似的位操作问题很有帮助。