LeetCode 338. 比特位计数

◎

本节目标

通过右移删除最低位，让更小整数的置位数递推到当前整数。

这道题是二进制与位运算基础中的递推母题：不必对每个数从头数位，而是让一个数删除最低位后复用已知答案。

查看原题

题意与约束

给定非负整数 n，返回长度为 n + 1 的数组；第 i 项是 i 的二进制表示中 1 的个数。

• 0 <= n <= 10^5。
• 结果必须覆盖从 0 到 n 的每一个整数。
• 题目要求线性时间，因此不能对每个 i 再逐位扫描。

删除最低位后的子问题

把 i 右移一位得到 i >> 1，相当于删除 i 的最低位。被删除的这一位正是 i & 1：它是 0 时不会增加置位数，是 1 时恰好多一个置位。

因此，当前数的置位数可以由“删除最低位后的更小整数”补上被删除位的贡献得到，而不是把公式当作需要记忆的结论。

状态定义与递推式

定义 dp[i] 为整数 i 的二进制表示中 1 的个数。0 没有置位，因此 dp[0] = 0。

对 i >= 1，i >> 1 < i，而最低位的贡献为 i & 1，所以：

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

以 0..5 为例：

i	二进制	i >> 1	i & 1	dp[i]
0	0	—	—	0
1	1	0	1	0 + 1 = 1
2	10	1	0	1 + 0 = 1
3	11	1	1	1 + 1 = 2
4	100	2	0	1 + 0 = 1
5	101	2	1	1 + 1 = 2

为什么遍历顺序天然正确

从 1 递增到 n 时，处理 i 前，所有小于 i 的 dp 值已经计算完毕。由于 i >> 1 一定小于 i，递推式读取的 dp[i >> 1] 必然是已确定状态。

这里不需要像 01 背包那样讨论正序或倒序覆盖：每个 dp[i] 只读取不同且更早的下标，写入当前下标不会改变任何后续状态所需的前驱。

代码实现

两份源码都创建 n + 1 个位置的 dp，保留 dp[0] = 0，再按递增顺序应用同一条递推式。

C++

C++17

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
};

Python

Python 3

class Solution:
    def countBits(self, n: int) -> list[int]:
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = dp[i >> 1] + (i & 1)
        return dp

复杂度分析

每个整数只进行一次常数时间的转移，时间复杂度为 O(n)。dp 是题目要求返回的数组，额外占用 O(n) 空间。

易错点

• 误用 i & (i - 1)：它删除的是最低位的 1，适合另一种递推，但不是本题这里的右移前驱。
• 从 0 开始套用递推式：dp[0] 是基例，不能访问不存在的更小状态。
• 只返回 1..n 的答案：题目要求数组包含 0，首项必须是 0。
• 把 i >> 1 当作除以二后向上取整：对非负整数，它正是向下整除二，因而严格小于正数 i。

模式迁移

当一个状态能通过删除末尾元素、最低位或最后一步操作化为更小状态时，先定义“小状态保存什么”，再确认被删除部分的局部贡献。本题的删除操作是右移，局部贡献是最低位；类似地，按位 DP、前缀递推和构造型 DP 都可用“更小前驱 + 新增部分”来推导转移。