LeetCode LCR 003. 比特位计数

约 3 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 简单 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
动态规划 LCR 位运算

题目描述

✅ LCR 003. 比特位计数

image-20260928234626409

image-20260928234626410

题意分析

对每个整数 i = 0..n，统计其二进制表示中一的个数，按数值顺序返回长度为 n + 1 的数组。要求的是整段范围的答案，不只是 n 自身的计数。

n 可以为零，此时仍要返回包含零计数的一项。进阶要求不用内置位计数函数，通过一趟线性扫描求出全部结果，因此可以让较大数复用此前已算出的较小数状态。

解法：删除最低位 1 的递推

核心思路

[!blue]

令 f[i] 表示整数 i 的二进制中一的个数，初始 f[0] = 0。要在常数时间求出新状态，需要把 i 转成一个已经求解、且置位数量与它存在确定关系的更小数。

对正数 i，减一会把最低的一位从一变零，同时把它右边原有的零全部变成一，更高位保持不变。再与原数按位与，右侧因为原来全为零仍然为零，最低的那一位被清除，其余高位不变。因此 i & (i - 1) 恰好比 i 少一个一。

得到转移 f[i] = f[i & (i - 1)] + 1。清掉一个置位会使数值严格减小，所以按 i 从小到大处理时，依赖下标已经计算完成，不需要继续循环剥掉其他位。

每个新数只做一次按位运算和一次查表，前面完成的位计数通过数组被复用。零不能应用“删除一位”的转移，因为它没有任何一，保留初始零状态即可；结果数组也就是状态数组，无需第二份存储。

解题步骤

  1. 创建长度为 n + 1 的零数组，保留 f[0] = 0。
  2. 从 i = 1 递增到 n，计算去掉最低置位后的下标 i & (i - 1)。
  3. 将该下标的计数加一写入 f[i]。
  4. 返回整个数组，包含零到 n 的全部结果。

代码实现

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 + 1)$，创建并填充长度为 n + 1 的数组，每个非零状态只做常数次操作。
  • 空间复杂度：结果及状态数组占 $O(n + 1)$；若不计必须返回的数组，额外空间为 $O(1)$。

关键点总结

[!green]

  • i & (i - 1) 清除最低的一位，计数恰好减少一，而不是任意改变数值。
  • 依赖下标严格更小，使递增填表可以直接复用已完成答案。
  • 状态下标就是对应整数，数组要包含 n 本身。
  • 一趟扫描的关键是复用计数，不是对每个整数重新统计所有位。

易错点总结

[!yellow]

  • 数组长度写成 n 会漏掉最后一个数，n = 0 时也失去应返回的零项。
  • 从零开始套用转移，会把 f[0] 错误地更新成一，应从一开始。
  • 反向填表可能读取未完成的较小状态，无法保证递推正确。
  • 位运算要显式保留必要括号，避免把减法、位与及数组下标的结合关系写错。

相似题目

题目 难度 关联与区别
191. 位1的个数 简单 原题只统计一个数的1，本题连续求0到n，可复用较小状态避免逐个重新计数。
461. 汉明距离 简单 异或先定位两数不同位，再用位计数得到汉明距离。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/58946351
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！