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]。逐个看：

i二进制1 的个数
000
111
2101
3112
41001
51012
61102
71113

约束：0 ≤ n ≤ 105；不得使用内置函数直接数 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 ≤ 105，但进阶要求线性，说明存在可以复用的结构。

关键观察：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

    🔒

    本篇为付费内容

    您已阅读试读部分，购买后即可解锁全文。

    ⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。