leetcode1/leetcode 仓库实战解析Counting BitsLeetCode 338从位掩码到 O(n) 动态规划的完整解法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以leetcode1/leetcode仓库中的 articles/counting-bits.md 为核心系统拆解「给定整数 n返回 0 到 n 每个整数的二进制中 1 的个数」这一经典问题的五种解法32 位掩码逐位检查、Kernighan 算法、语言内置 popcount、按 2 的幂 offset 的动态规划DP、右移 DP。并结合仓库中 11 种语言的 0338 题目实现 与 hints/counting-bits.md 官方提示逐条交叉印证读完你可以独立推导任意一种 bit counting 递推式并规避移位方向、运算符优先级、循环边界等常见错误。一、题目陈述与前置知识问题定义与 c/0338-counting-bits.c 头部注释一致给定整数n返回长度为n 1的数组ans其中ans[i]是i的二进制表示中 1 的个数。约束为0 n 10^5。例如n 2时返回[0, 1, 1]0有 0 个 11有 1 个 12 10有 1 个 1这一示例在 cpp/0338-counting-bits.cpp 的注释中也有记载。原始文档在动手解题前列出了三项前置能力要求位操作Bit Manipulation理解二进制表示与按位与、按位或、移位运算动态规划Dynamic Programming能够基于已计算结果增量地构建解二进制数系统Binary Number System理解整数如何以二进制存储、如何统计置位set bit。hints/counting-bits.md 给出的「目标复杂度」是O(n) 时间、O(n) 空间其中空间主要指输出数组本身提示还明确指出逐位遍历的朴素做法是 O(n log n)应通过观察连续数字的二进制模式寻找更优递推关系。二、解法一32 位掩码逐位检查Bit Manipulation - I核心思想对0到n中的每个数独立地检查它的每一位整数通常按32 位表示用位掩码(1 i)测试第i位是否置位。该解法不是最优的但最直观地展示了位运算在底层是如何工作的适合作为位操作的入门范本。算法步骤初始化空列表res对每个num ∈ [0, n]置计数器one 0对每一位i ∈ [0, 31]若(1 i) num非零one加一将one追加进res返回res。class Solution: def countBits(self, n: int) - List[int]: res [] for num in range(n 1): one 0 for i in range(32): if num (1 i): one 1 res.append # 占位示意完整写法见下 return res完整可运行版本Python 与 Javaclass Solution: def countBits(self, n: int) - List[int]: res [] for num in range(n 1): one 0 for i in range(32): if num (1 i): one 1 res.append(one) return respublic class Solution { public int[] countBits(int n) { int[] res new int[n 1]; for (int num 1; num n; num) { for (int i 0; i 32; i) { if ((num (1 i)) ! 0) { res[num]; } } } return res; } }原文档中此解法还附有 C、JavaScript、C#、Go、Kotlin、Swift、Rust 共 10 种语言的完整实现统一遵循「外层遍历数字、内层遍历 32 个位」的结构可查阅 articles/counting-bits.md 获取全部代码。复杂度时间复杂度O(n log n)按原文档口径内层循环固定 32 次实际执行量是 32n 次位与操作常数因子与机器字长相关空间复杂度O(1) 额外空间输出数组 O(n)。三、解法二Kernighan 算法Bit Manipulation - II核心思想高效统计单个整数的 1 位数可以使用Brian Kernighan 算法其关键观察是n (n - 1)会抹掉n最低位的 1重复该操作直到n变为 0操作次数就是 1 位的个数。这样就避免了「每个数字都检查全部 32 位」的浪费——循环次数只与该数实际含有的 1 位数成正比。算法步骤创建长度为n 1、初始全 0 的数组res对每个i ∈ [1, n]令num i当num ! 0时res[i]加一并执行num (num - 1)返回res。class Solution: def countBits(self, n: int) - List[int]: res [0] * (n 1) for i in range(1, n 1): num i while num ! 0: res[i] 1 num (num - 1) return respublic class Solution { public int[] countBits(int n) { int[] res new int[n 1]; for (int i 1; i n; i) { int num i; while (num ! 0) { res[i]; num (num - 1); } } return res; } }仓库实现印证仓库中的 Rust 与 Swift 实现正是这一思路的独立落证rust/0338-counting-bits.rs 将 Kernighan 循环抽成独立函数set_bits(n)主函数对0..n逐个调用swift/0338-counting-bits.swift 中的popCount(_ x: Int)同样是while x ! 0 { x x - 1; count 1 }。此外 java/0338-counting-bits.java 给出了一个值得注意的变体——把 Kernighan 思想直接融入 DP 的一行式class Solution { public int[] countBits(int n) { int res[] new int[n 1]; for (int i 1; i n; i) res[i] 1 res[i (i - 1)]; return res; } }因为i (i - 1)恰好是「抹掉i最低位 1 之后的数」所以i的 1 位数等于该数的 1 位数加 1一行同时完成了去位与查表把 O(n log n) 的逐数循环压缩成 O(n) 的单次查表。复杂度时间复杂度O(n log n)内层 while 执行次数等于该数的 1 位数空间复杂度O(1) 额外空间输出数组 O(n)。四、解法三语言内置函数In-Built Function适用场景很多语言提供了「转二进制字符串」或「直接统计置位」的内置手段写出来的解法非常简洁。原文明确其适用条件n为小到中等规模可读性优先于极限性能想要快速、可靠的实现。算法步骤初始化空结果列表对每个i ∈ [0, n]用内置工具把i转为二进制表示或调用 popcount 原语统计其中 1 的个数返回结果。原文档给出的 10 种语言实现可以归纳成一张内置函数速查表每种语言的具体代码均可在 articles/counting-bits.md 中对照语言核心调用示例写法Pythonbin(i).count(1)return [bin(i).count(1) for i in range(n 1)]JavaInteger.bitCount(i)res[i] Integer.bitCount(i);C__builtin_popcount(i)GCC/Clang 内建res[i] __builtin_popcount(i);JavaScripti.toString(2).split(1).length - 1转二进制字符串后按1分割计数C#Convert.ToString(i, 2)配合 LINQ...Count(c c 1)Gobits.OnesCount(uint(i))math/bits包res[i] bits.OnesCount(uint(i))Kotlin标准库扩展it.countOneBits()return IntArray(n 1) { it.countOneBits() }Swiftnum.nonzeroBitCountres[num] num.nonzeroBitCountRusti.count_ones()(0..n).map(\|i\| i.count_ones() as i32).collect()JavaScript 版本的具体实现展示了「无 popcount 原语时如何用字符串技巧数 1」class Solution { countBits(n) { let res []; for (let i 0; i n; i) { res.push(i.toString(2).split(1).length - 1); } return res; } }仓库中的 typescript/0338-counting-bits.ts 走的也是字符串路线只是把逐字符判断封装成了辅助函数hammingWeight(n)function hammingWeight(n: number): number { let base2 n.toString(2).split(); let count 0; base2.forEach((item) { if (item 1) count 1; }); return count; }从源码结构看TS 版与原文档 JS 版都属于「O(log n) 转字符串 O(log n) 计数」一类与上表的字符串路线一致。复杂度时间复杂度O(n log n)每个数的二进制转换/计数是 O(log n)空间复杂度O(1) 额外空间输出数组 O(n)。五、解法四按 2 的幂 offset 的动态规划Bit Manipulation - DP这是 hints/counting-bits.md 提示逐步引导出的官方 DP 关系。核心思想二进制表示有一个关键模式每到一个 2 的幂位图就整体重复一遍。2 的幂次本身就只含1 个 1 位任意数i都可以拆成i highestPowerOfTwo(≤ i) 余数因此i的 1 位数 1最高 2 的幂贡献 余数的 1 位数。这使我们可以增量地复用已算出的结果正是动态规划的标准形态。以 hints/counting-bits.md 中 Hint 2 的例子计算 7 的 1 位数时等于在 3 的 1 位数上加 1而 3 的 1 位数又是在 1 的 1 位数上加 1。观察可推广为小于 4 的数在「往前 2 个位置」的计数上加 1小于 8 的数在「往前 4 个位置」的计数上加 1。算法步骤创建 DP 数组dp长度n 1dp[i]存放i的 1 位数初始化dp[0] 0offset 1追踪最近的 2 的幂对每个i ∈ [1, n]若i 2 * offset到达下一个 2 的幂更新offset i递推dp[i] 1 dp[i - offset]返回dp。class Solution: def countBits(self, n: int) - List[int]: dp [0] * (n 1) offset 1 for i in range(1, n 1): if offset * 2 i: offset i dp[i] 1 dp[i - offset] return dppublic class Solution { public int[] countBits(int n) { int[] dp new int[n 1]; int offset 1; for (int i 1; i n; i) { if (offset * 2 i) { offset i; } dp[i] 1 dp[i - offset]; } return dp; } }func countBits(n int) []int { dp : make([]int, n1) offset : 1 for i : 1; i n; i { if offset*2 i { offset i } dp[i] 1 dp[i - offset] } return dp }仓库实现印证这一解法在仓库中是「官方主解」多语言实现几乎逐行对应文档python/0338-counting-bits.py 的主体实现与文档 Python 版完全一致offset * 2 i时更新 offsetdp[i] 1 dp[i - offset]go/0338-counting-bits.go 与 kotlin/0338-counting-bits.kt 同样是 offset 递推hints/counting-bits.md 的 Hint 3 直接点明递推式dp[i] 1 dp[i - offset]以及「offset * 2等于当前数时更新 offset」这一判定技巧与上述代码一一对应。另外 python/0338-counting-bits.py 还附带了一个注释为「Another dp solution」的奇偶拆分变体思路更直白奇数的 1 位数等于前一个偶数加 1偶数右移一位 1 位数不变class Solution2: def countBits(self, n: int) - List[int]: res [0] * (n 1) for i in range(1, n 1): if i % 2 1: res[i] res[i - 1] 1 else: res[i] res[i // 2] return resruby/0338-counting-bits.rb 则是 offset 递推的一个更复杂的 Ruby 风格写法用offset初值 2、每轮翻倍的方式处理边界从源码结构看属于同一递推关系的不同工程化实现。复杂度时间复杂度O(n)每个数只做一次查表空间复杂度O(1) 额外空间输出数组 O(n)。六、解法五右移 DPBit Manipulation - Optimal核心思想这是原文档标注的最优解递推式最短i 1相当于「去掉最低位」后的数即i / 2i 1告诉最低位是 1 还是 0即i mod 2因此setBits(i) setBits(i 1) (i 1)。每个结果只依赖一个已算出的更小值天然是 DP。cpp/0338-counting-bits.cpp 的注释里把这个等式写成了整数语言f(x) f(x / 2) (x mod 2)并注明 Time O(n)、Space O(1)输出数组不计入。算法步骤创建 DP 数组dp长度n 1dp[0] 0对每个i ∈ [1, n]dp[i] dp[i 1] (i 1)返回dp。class Solution: def countBits(self, n: int) - List[int]: dp [0] * (n 1) for i in range(n 1): dp[i] dp[i 1] (i 1) return dpint *countBits(int n, int *returnSize) { int *ret calloc(n 1, sizeof(int)); *returnSize n 1; for (int i 1; i n; i) ret[i] ret[i 1] (i 1); return ret; }C 语言版本c/0338-counting-bits.c值得逐行注意两个 C 特有的细节用calloc一次性清零分配n 1个int等价于dp [0] * (n 1)通过输出参数*returnSize n 1向调用者返回数组长度且文件头注释声明「返回数组由 malloc 分配由调用者负责 free」——这是 LeetCode C 题模板的内存约定移植到其他项目时必须保留否则会泄漏内存。JavaScript 版则展示了「以函数参数承载 DP 表」的等价写法见 javascript/0338-counting-bits.jsvar countBits function (n, dp [0]) { for (let i 1; i n 1; i) { const [mid, bit] [i 1, i 1]; dp.push(dp[mid] bit); } return dp; };原文档该解法同样覆盖 C、C#、Go、Kotlin、Swift、Rust 等语言结构均为「一行递推 单循环」可对照 articles/counting-bits.md。复杂度时间复杂度O(n)空间复杂度O(1) 额外空间输出数组 O(n)。七、五种解法横向对比结合原文档的复杂度结论与 hints/counting-bits.md 的目标复杂度要求解法核心操作时间复杂度额外空间特点32 位掩码(1 i) num逐位测试O(n log n)O(1)最直观展示位运算底层Kernighannum num - 1逐个去 1O(n log n)O(1)循环次数与 1 位数成正比内置函数bitCount/popcount等O(n log n)O(1)最简洁可读性优先offset DPdp[i] 1 dp[i - offset]O(n)O(1)利用 2 的幂周期官方提示路线右移 DPdp[i] dp[i 1] (i 1)O(n)O(1)递推最短仓库 C/C/JS 主选表中所有解法的输出数组均为 O(n)不计入额外空间与原文档口径一致。仓库各语言实现的实际选型也印证了这组权衡追求最优复杂度的 c/0338-counting-bits.c、cpp/0338-counting-bits.cpp、javascript/0338-counting-bits.js 选右移 DPpython/0338-counting-bits.py、go/0338-counting-bits.go、kotlin/0338-counting-bits.kt 选 offset DP而 rust/0338-counting-bits.rs、swift/0338-counting-bits.swift 选 Kernighan 循环java/0338-counting-bits.java 选i (i - 1)单行 DP——同一题目在不同实现里各取所长恰好可以作为多语言刷题时的对照样本。八、常见陷阱Common Pitfalls原文档专门列出两类高频错误结合仓库代码逐一展开陷阱 1移位方向与运算符优先级在递推dp[i] dp[i 1] (i 1)中两个经典失误# 错误一把右移写成左移 dp[i] dp[i 1] (i 1) # i 1 越界访问索引大于 i # 错误二加法先于移位执行运算符优先级陷阱 dp[i] dp[i 1 (i 1)] # 实际计算的是 i (1 (i 1)) # 正确写法 dp[i] dp[i 1] (i 1)对照 c/0338-counting-bits.c 中ret[i] ret[i 1] (i 1)的括号组织方式以及 javascript/0338-counting-bits.js 中先解构出mid i 1、bit i 1再组合的写法可以看出把移位与取位拆成两个中间变量本身就是对抗优先级错误的有效手段。陷阱 2循环边界 off-by-one题目要求统计0到n含 n结果数组必须是n 1个元素# 错误一数组开小了 dp [0] * n # 缺少 dp[n] # 错误二循环没有包含 n for i in range(n): # 应为 range(n 1) # 正确 dp [0] * (n 1) for i in range(n 1): # processC 语言里对应的正确姿势见 c/0338-counting-bits.ccalloc(n 1, sizeof(int))分配n 1个元素*returnSize n 1与循环for (int i 1; i n; i)三者保持一致任何一处写成n都会直接越界或漏算最后一个数。九、仓库文件索引围绕本题当前仓库中可直接查阅的材料如下路径内容articles/counting-bits.md本文核心来源五种解法 × 10 种语言完整实现hints/counting-bits.md官方提示目标复杂度、DP 递推推导python/0338-counting-bits.pyoffset DP 主解 奇偶拆分 DP 变体java/0338-counting-bits.java1 res[i (i - 1)]单行 DPc/0338-counting-bits.c右移 DP含returnSize与内存约定说明cpp/0338-counting-bits.cpp右移 DP附 f(x) f(x/2) x%2 推导注释rust/0338-counting-bits.rsKernighan 循环实现go/0338-counting-bits.gooffset DPkotlin/0338-counting-bits.ktoffset DPswift/0338-counting-bits.swiftKernighan popCount 实现javascript/0338-counting-bits.js右移 DP默认参数承载 DP 表typescript/0338-counting-bits.ts二进制字符串计数ruby/0338-counting-bits.rboffset 递推的 Ruby 风格实现以上实现均属于 README.md 所述的多语言题解集合该仓库收录 Python、Java、JavaScript、C、Go、Swift、C#、TypeScript、Rust、Kotlin、Ruby、C 等语言的 LeetCode 题解各文件保持独立、可直接复制到对应语言的 LeetCode 判题环境中运行验证。小结Counting Bits 是「位运算 动态规划」交叉点的教科书式问题——先学会 32 位掩码建立底层直觉再用 Kernighan 的n (n - 1)消除无谓的位检查最后用dp[i] dp[i 1] (i 1)或dp[i] 1 dp[i - offset]两条递推到 O(n) 收尾。仓库中 11 个语言的 0338 实现与官方提示文件提供了完整的交叉验证素材适合作为多语言位运算 DP 的对照学习样本。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考