LeetCode LCR 003. 比特位计数
目录
题目描述
题意分析
给一个非负整数
n，返回长度为n + 1的数组ans，其中ans[i]是i的二进制表示里 $1$ 的个数。注意题目要的不是「某一个数的 $1$ 的个数」，而是 $0$ 到
n全部数的答案。这个「一次性求出一整段前缀的答案」的形式，天然提示我们可以让大的数复用小的数已经算好的结果，而不是对每个数独立数一遍。
n的规模是 $10^5$ 级，即使对每个数独立用n & (n - 1)循环剥位，总代价也只有 $O(n \log n)$，能过。但题目通常附带进阶要求：只扫一遍、不使用任何内建的 popcount 函数。这条进阶才是本题真正的考点，它把题目从「会不会数二进制位」变成了「能不能找到相邻答案之间的递推关系」。边界只有一处但必须处理：
n = 0时结果是长度为 $1$ 的数组[0]。因为答案数组的下标要覆盖到n本身，容量必须是n + 1而不是n。
解法：动态规划递推
核心思路
暴力做法是对每个 $i$ 单独统计：
while (x > 0) { cnt += x & 1; x >>= 1; }。正确，$O(n \log n)$。瓶颈在于每个数都从零开始重新数，完全浪费了「$0$ 到 $i-1$ 的答案都已经算好」这个现成条件。观察的切入点是
x & (x - 1)这个恒等式：它的效果是把x最低位的那个 $1$ 抹掉，其余位原样保留。原因是x - 1会让最低位的 $1$ 变成 $0$、并把它右边的全 $0$ 变成全 $1$，与x按位与之后，最低位的 $1$ 及其右侧全部清零，而更高位不受影响。于是对任意 $i \ge 1$，
i & (i - 1)是一个严格小于i的数（至少少了一个 $1$，数值必然变小），并且它的 $1$ 的个数恰好比i少一个。这就直接给出了状态定义与转移。状态定义：
f[i]表示整数i的二进制表示中 $1$ 的个数。转移方程：$f[i] = f[i \operatorname{\&} (i-1)] + 1$，其中 $i \ge 1$。初始状态：$f[0] = 0$。转移合法的依据是
i & (i - 1) < i，所以按i从小到大的顺序递推时，右侧依赖的状态一定已经算好了——这也是为什么循环方向只能是递增。每个状态只做一次常数级计算，总代价降到 $O(n)$，同时结果数组本身就是答案，不需要额外空间。
解题步骤
- 开一个长度为
n + 1的数组f。长度必须含n自己，Java/Go 的零值初始化正好把f[0] = 0这个初始状态一并完成，不需要显式赋值。- 从
i = 1开始递推到n。起点是 $1$ 而不是 $0$，因为i = 0时i - 1会变成 $-1$（补码全 $1$），0 & -1仍是 $0$，会形成自依赖的死转移；把 $0$ 留作初始状态可以规避。- 写
f[i] = f[i & (i - 1)] + 1。i & (i - 1)抹掉最低位的 $1$，所以它的 $1$ 的个数比i少一个，加一即可。- 方向必须递增。
i & (i - 1)严格小于i，只有从小到大遍历才能保证依赖已经就绪。- 直接返回
f。答案数组与 dp 数组是同一个，按题意进阶要求，这份 $O(n)$ 的额外空间不计入。以
n = 5走一遍。初始f = [0, 0, 0, 0, 0, 0]。i = 1：1 & 0 = 0，f[1] = f[0] + 1 = 1（$1$ 的二进制是1）。i = 2：2 & 1 = 0，f[2] = f[0] + 1 = 1（10）。i = 3：3 & 2 = 2，f[3] = f[2] + 1 = 2（11，比10多一个 $1$）。i = 4：4 & 3 = 0，f[4] = f[0] + 1 = 1（100）。i = 5：5 & 4 = 4，f[5] = f[4] + 1 = 2（101，比100多一个 $1$）。最终返回[0, 1, 1, 2, 1, 2]。可以看到每个i都跳到了一个更小的、已经算好的下标，全程没有任何重复的位统计。
代码实现
class Solution {
public int[] countBits(int n) {
int[] f = new int[n + 1];
for (int i = 1; i <= n; ++i) {
// i & (i - 1) 抹掉最低位的 1，它一定小于 i，答案已算好。
f[i] = f[i & (i - 1)] + 1;
}
return f;
}
}
func countBits(n int) []int {
f := make([]int, n+1)
for i := 1; i <= n; i++ {
// i & (i - 1) 抹掉最低位的 1，它一定小于 i，答案已算好。
f[i] = f[i&(i-1)] + 1
}
return f
}
复杂度分析
- 时间复杂度：$O(n)$。$n$ 个状态，每个状态只做一次按位与、一次数组访问和一次加法，全是常数操作，没有内层循环。
- 空间复杂度：$O(1)$（不计返回值）。除了必须返回的长度
n + 1的答案数组外，只用了循环变量i；dp 表与答案表复用同一块内存，没有任何额外结构。
关键点总结
x & (x - 1)抹掉最低位的 $1$、x & (-x)取出最低位的 $1$，这两个恒等式是位运算题的基本词汇，看到「统计 $1$ 的个数」「判断是否 $2$ 的幂」「枚举子集」都会用到。- 「求 $0$ 到
n全部答案」这种批量形式，第一反应就该是找相邻答案的递推关系，而不是对每个元素跑一遍独立算法。- dp 转移的合法性靠「被依赖的下标严格更小」保证，写完转移方程要立刻确认遍历方向能满足它——本题的
i & (i - 1) < i就是那句关键论证。- 本题还有两个等价转移可以互相印证：按最低位拆 $f[i] = f[i » 1] + (i \operatorname{\&} 1)$，按最高位拆 $f[i] = f[i - \text{highbit}(i)] + 1$。三者都是 $O(n)$，说明关键不在于记住某一条式子，而在于找到「让
i变小且 $1$ 的个数可控」的映射。- 面试视角：这题被问时，直接写
Integer.bitCount(i)是最容易被判负的答案——它把考点整个绕过去了。正确的做法是先说明进阶要求（一次遍历、不用内建函数），再给出递推，并主动解释i & (i - 1)为什么小于i；面试官追问「还有别的递推吗」时，能补上f[i >> 1] + (i & 1)说明你理解的是方法而不是背下了一行代码。
易错点总结
- 错误写法：
int[] f = new int[n]。输入n = 5时数组只能放下下标 $0$ 到 $4$，写f[5]直接数组越界；就算不越界，返回的长度也少了一个。- 错误写法：循环从
i = 0开始。0 - 1在补码下是全 $1$，0 & -1仍是 $0$，f[0] = f[0] + 1把初始状态污染成 $1$，输入n = 0会返回[1]。- 错误写法：写成
f[i] = f[i & (i - 1)] + i & 1。Java/Go 中+的优先级高于&，实际算的是(f[...] + i) & 1，输入n = 3会返回[0, 1, 0, 1]。- 错误写法：用
Integer.bitCount(i)或bits.OnesCount(uint(i))填表。结果对，但等于没做题——面试中这属于用库函数绕过考点，会被要求重写。- 错误写法：把转移写成
f[i] = f[i / 2] + 1。漏了「最低位是否为 $1$」的判断，输入n = 2会返回[0, 1, 2]，正确答案是[0, 1, 1]。- 错误写法：为了「优化」改成从大到小遍历
i。f[i & (i - 1)]依赖的是更小的下标，倒序时它还没算，输入n = 3会返回[0, 1, 1, 1]。- 错误写法：把
i & (i - 1)写成i & (i + 1)。这个式子不减少 $1$ 的个数，i = 3时3 & 4 = 0，f[3]被算成 $1$，输入n = 3返回[0, 1, 1, 1]而不是[0, 1, 1, 2]。- 错误写法：额外开一个数组存 dp、最后再拷贝到答案数组。空间翻倍且毫无必要，本题的 dp 表定义与答案定义完全重合，直接返回即可。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 338. 比特位计数 | 简单 | 与本题同题，可直接套用同一条递推 |
| 191. 位1的个数 | 简单 | 只求单个数，用 n & (n - 1) 循环剥位，剥几次答案就是几 |
| 剑指 Offer 15. 二进制中1的个数 | 简单 | 与 191 同题，需额外注意无符号右移与负数输入 |
| 461. 汉明距离 | 简单 | 先异或再数 $1$，把「两数差异」转成「单数位计数」 |
| 面试题 05.06. 整数转换 | 简单 | 与 461 同题，但输入含负数，Java 需用 >>> 或直接对异或值计数 |
| 477. 汉明距离总和 | 中等 | 求两两距离之和，需按位统计 $0$/$1$ 个数后相乘，避免 $O(n^2)$ 枚举 |