338. 比特位计数（简单）

Blind 75 › 338. 比特位计数（简单）（第 2 章）

题目

给定整数 n，返回一个长度为 n + 1 的数组 ans：ans[i] 表示 i 的二进制表示里一共有几个 1（即「汉明重量」）。

例如 6 = 110，有 2 个 1，所以 ans[6] = 2。

自造示例：n = 7 → [0,1,1,2,1,2,2,3]。逐个看：

约束：0 ≤ n ≤ 10⁵；不得使用内置函数直接数 1（如 C++ 的 __builtin_popcount、Python 的 bin(x).count("1")）。进阶：做到 O(n) 时间、一趟扫描。

一句话：0 到 n 每个数的 1 的个数，可以由「更小的数」递推出来，一次遍历填完整张表。

先想最直白的：对每个 i，反复用 x &= (x - 1) 消掉最低位的 1，同时计数，直到变成 0。单个 i 最多有 log n 个二进制位，所以总时间是 O(n log n)。这已经能过 n ≤ 10⁵，但进阶要求线性，说明存在可以复用的结构。

关键观察：i 的二进制，等于「把 i 右移一位得到 i >> 1」再在末尾补上最低位 i & 1。右移丢掉的恰好就是最低位，于是：

popcount(i) = popcount(i >> 1) + (i & 1)

因为 i >> 1 < i，按 i 从小到大算时，右边永远已经算好了。等价递推还有两种，思路相同，都是「去掉一个位」：

去掉最低的 1：popcount(i) = popcount(i & (i - 1)) + 1。
去掉最高的 1：设 offset 是不超过 i
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。