刷LeetCode的人应该都有这种体会有些题一看就会一做就废有些题代码短得可怜但背后的思路能让你卡上半天。338. 比特位计数就属于后者。题目本身几句话就能说清楚给定一个非负整数 n统计 0 到 n 这 n 1 个数各自二进制表示中 1 的个数返回一个数组。但它能进 Hot100靠的不是题目本身有多难而是背后那条从暴力到位运算、再到动态规划的递进路径几乎把面试里最常考的几类技巧串在了一起。我最早刷这道题是在准备算法面试的中期当时刚把数组、链表、二叉树过完一轮自认为基础还行结果看到这题第一反应是这不就是循环里调用一下内置函数数 1 吗写完之后倒是能过但一看题解里那个只有三行的动态规划瞬间觉得自己确实还差得远。后来我把这道题反复拆了几遍发现它其实是一个很典型的“一层窗户纸”题目——你捅破了后面好多位运算题都能顺带想通。这篇文章就把我踩过的坑、推导的过程、以及从这题延伸出去的思路完完整整写出来希望能帮到正在刷 Hot100 的朋友。1. 先从题目说起它到底在考什么1.1 题目描述与示例LeetCode 338. 比特位计数Counting Bits题面非常简洁给定一个非负整数 n对于 0 ≤ i ≤ n 范围内的每个数字 i计算其二进制表示中 1 的个数并将它们作为数组返回。具体看一个例子。假设 n 5那么从 0 到 5 这六个数字的二进制分别为数字二进制1 的个数000111210131124100151012所以返回结果就是[0, 1, 1, 2, 1, 2]。这个题目本身不难理解难的是它的附加要求你能不能做到时间复杂度 O(n)也就是说你不能真的挨个把每个数字转换成二进制再数一遍那样时间复杂度会到 O(n log n) 甚至更差。题目真正想考的是你能否利用相邻数字之间的二进制关系把前面已经算好的结果复用起来。一句话概括这就是动态规划的思路。1.2 为什么这道题能进 Hot100Hot100 的选题标准向来不是“最难”而是“最典型”。338 题涉及的核心知识点有三个位运算、动态规划、递推关系。这三个东西几乎出现在每一轮算法面试里而 338 题恰好把三者放在了一个不到二十行的代码里。更关键的是它不像很多 DP 题那样需要你定义复杂的二维状态也不需要你维护什么dp[i][j]它只有一个一维数组而且状态转移极其优美。这种“看起来很简单但你就是想不出来”的题目恰恰是面试官最爱出的。如果能把 338 题的递推逻辑讲明白至少说明你对二进制和 DP 的基础不是死记硬背的。2. 解法演进从暴力到动态规划2.1 解法一逐个数统计暴力法最容易想到的办法肯定是对 0 到 n 的每个数字单独统计 1 的个数。统计单个数字二进制中 1 的个数可以用一个循环每次右移一位然后看最低位是不是 1def countBits(n: int) - List[int]: res [] for i in range(n 1): cnt 0 x i while x: cnt x 1 x 1 res.append(cnt) return res复杂度是多少对于每个数字 i它的二进制位数大约是 log₂(i)所以总时间复杂度是 O(n log n)。当 n 很小的时候没什么感觉但如果 n 到了 10⁵ 甚至 10⁶ 这个量级这个写法就会明显变慢。我第一次交这个解法的时候LeetCode 上数据范围是 0 ≤ n ≤ 10⁵勉强能过但耗时排在倒数。如果面试官问你“能不能 O(n)”你就得拿出更漂亮的解法。2.2 解法二Brian Kernighan 算法优化在讲动态规划之前先提一个经典的位运算技巧——Brian Kernighan 算法。它的作用是快速统计一个数字二进制中 1 的个数核心操作是x x - 1这个操作每次能消掉 x 二进制表示中最右边的那个 1。举个例子x 12二进制是 1100。12 - 1 11二进制是 1011。1100 1011 1000刚好消掉了原来从右边数第三个位置的 1。重复这个操作直到 x 变成 0操作次数就是 1 的个数。def countBits(n: int) - List[int]: res [] for i in range(n 1): cnt 0 x i while x: x x - 1 cnt 1 res.append(cnt) return res这个解法比纯右移要快因为循环次数不是二进制位数而是 1 的个数。但总时间复杂度仍然不是严格的 O(n)最坏情况下比如 n 是 2^k - 1每个数字都是满 1依然是 O(n log n) 的级别。2.3 动态规划的思路是怎么来的前面两种方法本质上都是“孤立”地处理每个数字没有利用数字之间的关系。可仔细看 0 到 n 的二进制序列你会发现明显有规律2 的二进制是 101 的二进制是 1那 2 的 1 个数其实等于 (2 - 2) 的 1 个数再加 1。3 的二进制是 11等于 1 的二进制 1 左移一位再加 1也就是 2 1。4 的二进制是 100去掉最高位变成 0。最直观的一个规律是偶数的最低位一定是 0奇数的最低位一定是 1。如果一个数是偶数 i那它的最低位是 0右移一位不会损失任何 1所以i的 1 个数等于i / 2的 1 个数。如果一个数是奇数那它的最低位是 1右移一位恰好把最低位的 1 丢掉所以i的 1 个数等于i / 2的 1 个数再加 1。写成公式就是dp[i] dp[i 1]当 i 为偶数dp[i] dp[i 1] 1当 i 为奇数这个递推关系就是动态规划的核心。它不是凭空冒出来的而是来自“二进制右移一位 除以 2”这个基本事实。想通了这一点这道题就破了一大半。3. 动态规划状态转移的两种推导方式3.1 方式一利用最低有效位最常见写法这里“最低有效位”指的就是二进制表示里的最后一位也就是i 1。不管 i 是奇数还是偶数下面的式子都成立dp[i] dp[i 1] (i 1)当 i 是偶数时i 1 0dp[i] dp[i 1]当 i 是奇数时i 1 1dp[i] dp[i 1] 1。i 1一定小于i吗对于所有非负整数右移一位相当于除以 2 后向下取整所以i 1一定小于等于 i。当 i ≥ 1 时i 1 i所以dp[i 1]一定已经在前面的循环里算完了这就满足了动态规划“无后效性”的要求。代码实现def countBits(n: int) - List[int]: dp [0] * (n 1) for i in range(1, n 1): dp[i] dp[i 1] (i 1) return dp这就是那个“三行核心代码”的版本。整个循环从 1 开始因为 dp[0] 天然等于 0不需要额外处理。时间复杂度 O(n)空间复杂度 O(n)完美满足题目要求。我最初看这个公式的时候觉得它像魔术一样怎么就能这么刚好后来我手动把 0 到 8 的二进制全部列了一遍才真正看明白i二进制i 1i 1dp[i]0000011011210101311112410020151012126110302711131381000401你会发现每个dp[i]都恰好等于它前面某个已经算好的值加上最后一位的贡献。这其实就是在做“把 i 的二进制去掉最低位然后看剩下的部分有几个 1再加上最低位自己是不是 1”这件事。3.2 方式二利用最高有效位另一种思路最低有效位的推导适合理解但在面试中如果你能说出另一种思路会让面试官觉得你不是背答案。最高有效位的思路是这样的每个数字 i 都可以拆成“最高位的那个 1”加上“剩余部分”。比如 13二进制 1101它的最高位是 8二进制 1000剩余部分是 5二进制 101。那么 13 的 1 的个数就等于 5 的 1 的个数再加 1。这里的关键是怎么找到“不超过 i 的最大的 2 的幂次”。可以用一个变量highBit来记录它表示当前数字的最高位对应的是 2 的几次方。当i (i - 1) 0时说明 i 本身就是 2 的幂此时highBit i。否则i的最高位和i - 1的最高位相同highBit保持不变。def countBits(n: int) - List[int]: dp [0] * (n 1) highBit 0 for i in range(1, n 1): if i (i - 1) 0: highBit i dp[i] dp[i - highBit] 1 return dpi (i - 1) 0是一个很常用的位运算技巧用来判断一个数是不是 2 的幂。自己的推导过程可以这样理解如果一个数只有一个 1那么它减去 1 之后原来那个 1 会变成 0后面的所有位都变成 1两者按位与的结果必然是 0。这个写法在思路上比最低有效位稍微绕一点但它把“二进制拆位”的思想表达得更直接。面试的时候如果能快速写出这两种写法基本就证明你对位运算和 DP 都掌握得比较扎实了。3.3 动态规划的边界与初始化不管用哪种写法dp[0] 0是天然的基准条件。循环从 1 开始dp[i]依赖的都是已经计算过的更小下标的值。这里有个容易犯的小错如果你上手就写for i in range(n 1)然后在循环体里同时处理 i0 的情况虽然逻辑上没错但会多一次无意义的赋值。更干净的做法是从 1 开始。还有一个小细节题目给的 n 是非负整数所以 n0 的时候返回[0]。这个边界条件千万不能漏我见过不少人在代码里默认 n ≥ 1导致 n0 时数组越界或者返回空列表。在 LeetCode 上这种问题会直接判 Wrong Answer非常可惜。4. 复杂度与边界条件分析4.1 三种解法复杂度对照解法时间复杂度空间复杂度适用场景暴力逐位统计O(n log n)O(1) 额外空间n 很小代码简单Brian KernighanO(n log n) 最坏O(1) 额外空间比暴力常数小面试过渡用动态规划最低位O(n)O(n) 存储结果题目标准解动态规划最高位O(n)O(n) 存储结果题目标准解换一种理解方式注意题目要求的返回值本身就是一个长度为 n1 的数组所以空间复杂度 O(n) 是不可避免的LeetCode 一般也不会在这个点上刁难你。这里说的“空间复杂度 O(1) 额外空间”是指除了返回结果之外不额外申请跟 n 相关的存储。4.2 不同语言实现时的细节坑拿 C/C 举例要注意int可能溢出吗这道题的 n 最大到 10^5所有中间结果都不会超过 20所以不存在溢出问题。但如果你习惯性地把i 1和i 1写成位运算要注意运算符优先级。比如dp[i] dp[i 1] (i 1);这里的括号加不加结果都一样因为的优先级高于。但为了避免读者产生困惑建议还是加上括号。Java 的写法也差不多class Solution { public int[] countBits(int n) { int[] dp new int[n 1]; for (int i 1; i n; i) { dp[i] dp[i 1] (i 1); } return dp; } }C 版本class Solution { public: vectorint countBits(int n) { vectorint dp(n 1, 0); for (int i 1; i n; i) { dp[i] dp[i 1] (i 1); } return dp; } };这个解法在三种主流语言里的核心逻辑完全一致区别只是语法细节。面试时也不一定要写满三种熟练一种理解另外两种能读即可。4.3 一个容易被忽略的边界条件题目说“非负整数 n”意味着 n 可能等于 0。这个时候要返回[0]不能用[0] * n这种长度错误的初始化。Python 里[0] * (n 1)在 n0 时是[0]恰好正确所以 Python 写起来比较省心。但如果你习惯先初始化长度为 n 的数组然后在循环里 append就要特别小心 n0 的情况。再说一个更隐蔽的坑如果你用最高有效位的写法highBit的更新条件是i (i - 1) 0。但要注意在 Python 里的优先级低于所以i (i - 1) 0会被解释成i ((i - 1) 0)这就完全错了。必须写成(i (i - 1)) 0。这种优先级问题在 C/C/Java 里也存在因为的优先级都低于所以最稳妥的做法就是任何位运算参与比较时两边都加上括号。注意位运算 、|、^ 的优先级普遍低于 、!所以写if (i (i - 1)) 0时千万别省括号。5. 这道题背后的思维模型与延伸5.1 从“右移一位”到“除以 2”的跳跃动态规划最低位版本之所以能成立本质上是因为二进制右移一位正好等价于整除 2。这个性质在很多题目里都能用到最典型的就是 191. 位1的个数Hamming Weight。那道题给你一个无符号整数让你返回二进制中 1 的个数。如果你理解了 338 题的状态转移再回头看 191 题就会发现它们其实是同一类问题一个是在统计单个数字一个是把 0 到 n 的结果全部算出来。我曾经在一个刷题群里看到有人问“338 题真的需要动态规划吗暴力不也能过吗”确实在 n10^5 的范围内暴力法花的时间连一秒都不到刷题网站上也能 AC。但面试官紧接着问一句“如果 n 是 10^9 呢”暴力法就会卡住。O(n log n) 和 O(n) 的差距在数据规模放大之后会变得非常明显。所以刷题不能只看“能不能过”还要看“能不能稳定地过”。5.2 这道题还能用什么姿势解除了动态规划之外还有一些选手喜欢用二分法配合预处理来写先把 0 到 65535 所有的结果打表存下来然后对于更大的数字每 16 位查一次表把四次查表结果加起来。这种思路在竞赛圈里很常见叫做“分块打表”代码会更长但常数比 DP 更小。对于 338 题的约束范围来说没必要但它提醒我们位运算题目的优化方向不只有 DP还有“空间换时间”和“预处理”。另外一个思路是用Integer.bitCount()这种语言内置函数。C 的__builtin_popcount、Java 的Integer.bitCount、Python 的bin(i).count(1)在工程上直接调用完全没问题而且性能也不差。但面试的时候如果你上来就用内置函数面试官可能会觉得你不了解底层实现。最好的回答方式是先说出动态规划的思路然后补一句“实际工程中也可以直接用内置的 bitCount性能已经优化得很好了”这样既有深度又有工程感。5.3 从 338 题迁移到其他 Hot100 题目掌握 338 题的思路之后有几个同类的题目你可以顺带刷掉位1的个数单个数统计 1 的个数Brian Kernighan 算法的直接应用。2 的幂判断一个数是不是 2 的幂n (n - 1) 0。丢失的数字可以用位运算异或解决但也可以用和值相减法。数字的补数跟按位取反有关注意处理前导零。只出现一次的数字 II位运算统计每一位上 1 出现的次数取模 3。这些题全部刷完你基本就能形成一个“位运算 状态转移”的方法论。以后再遇到类似“给你一个范围让你统计某种二进制特征”的题目第一反应就不会再是暴力遍历而是想一想能不能用递推关系减少重复计算。6. 上手实测手把手跑一遍完整流程6.1 环境准备与测试用例设计不管你是用本地 IDE 还是直接在 LeetCode 网页上写都建议自己多跑几个测试用例。我个人的习惯是在本地写一份完整的测试脚本覆盖普通用例、边界用例和大数据用例这样能快速发现逻辑漏洞。核心测试用例至少包括这几个n 0期望输出[0]n 1期望输出[0, 1]n 5期望输出[0, 1, 1, 2, 1, 2]n 8期望输出[0, 1, 1, 2, 1, 2, 2, 3, 1]n 100000主要用于性能测试观察是否在 1 秒内出结果from typing import List def countBits(n: int) - List[int]: dp [0] * (n 1) for i in range(1, n 1): dp[i] dp[i 1] (i 1) return dp # 简单测试 test_cases [ (0, [0]), (1, [0, 1]), (5, [0, 1, 1, 2, 1, 2]), (8, [0, 1, 1, 2, 1, 2, 2, 3, 1]), ] for n, expected in test_cases: result countBits(n) assert result expected, fn{n}, expected{expected}, got{result} print(fn{n}: {result} OK) # 性能测试 import time start time.time() result countBits(100000) print(fn100000 耗时: {time.time() - start:.4f} 秒)我自己跑下来n100000的情况下O(n) 的 DP 解法耗时在 0.005 秒左右体感上是瞬间完成。暴力法的耗时大约是 0.03 秒看着也很快但一旦把 n 放大到 10^7DP 的优势就会非常明显。6.2 验证递推公式的正确性如果你对dp[i] dp[i 1] (i 1)这个公式还有疑虑可以用一个笨办法来验证把每个数字的二进制写出来手动比对。以 i7 为例7 的二进制是 111。i 1 33 的二进制是 111 的个数是 2。i 1 1所以 7 的 1 的个数应该是 3。而 7 的二进制 111 确实有 3 个 1验证通过。再以 i10 为例10 的二进制是 1010。i 1 55 的二进制是 1011 的个数是 2。i 1 0所以 10 的 1 的个数是 2。而 1010 里确实是两个 1验证通过。这种手动验证做上几个数字之后公式就不再是死记硬背而是变成了一种直觉。6.3 常见报错与排查方法写这道题时我遇到过三个最常见的报错第一个是数组越界。如果初始化dp [0] * n那么下标dp[n]就会越界。正确写法是[0] * (n 1)多留一个位置。这个错误在 n0 的时候不一定暴露但只要 n ≥ 1跑dp[i 1]时很可能就崩了。第二个是循环起始下标错了。从 0 开始循环dp[0] dp[0] 0虽然不会越界但纯属浪费如果你在循环体里用i - 1之类的东西还可能在 i0 时出现负下标。建议统一从 1 开始。第三个是运算符优先级问题。前面提到过i (i - 1) 0在某些语言里会和预期不一致。解决办法很简单所有位运算参与布尔比较时两侧都加括号。别嫌丑可靠最重要。7. 从刷题到面试这道题怎么说才能加分7.1 避免“背答案式”讲解如果你在面试里遇到原题千万不要上来就默写三行代码。面试官想看的是你的思考过程而不是结果。比较好的回答顺序是先说最暴力的思路比如“我可以对每个数字循环除 2 数 1 的个数时间复杂度 O(n log n)”然后说“这个过程中有很多重复计算因为 i 右移一位就是 i/2它的 1 的个数我已经算过了”从而自然引出动态规划。这个过程看起来简单但很多候选人栽在“直接跳到最后解法”上。面试官问“为什么 dp[i] 等于 dp[i1] 加 1 或 0”如果答不上来推导过程那这道题就算写过也等于没写。我自己的经验是把 2.1 到 3.3 整个推导主线在脑子里过一遍不管面试官怎么追问你都能接住。7.2 可以顺带提一嘴的优化方向在讲完 DP 解法之后如果面试时间还有富余你可以顺带提一下“这个问题其实还有利用语言内置 bitCount 的实现方式实际生产中更推荐使用内置函数因为底层会利用 CPU 指令优化”。这几句话会显得你有工程视野而不只是一个刷题机器。另外还可以提一下这个 DP 本质上是“用空间换时间”它要求你保存前面所有数字的结果所以空间复杂度是 O(n)。如果你需要在内存受限的环境下处理超大 n可以考虑分段计算、只用前一段结果滚动更新但题目本身没这个要求。提示面试里可以主动说“这个解法时间和空间都是 O(n)如果要求 O(1) 空间可能需要重新设计存储方式”这种“主动暴露边界”的做法比等面试官来问要好得多。7.3 这道题对后续刷题的实际作用338 题还有一个隐藏价值它是理解“数位 DP”的入门砖。数位 DP 的经典问题是“统计某个区间内满足某种数位性质的数字个数”比如“1 到 n 中所有数字里一共出现了多少次数字 1”。这类题的核心思想也是“利用已经计算好的低位信息来推导高位信息”和 338 题的递推逻辑一脉相承。所以不要小看这道“简单题”。把它吃透等于帮你打通了位运算、递推、数位统计三块内容。我当时刷完 338 之后再去做 233. 数字 1 的个数那道题明显觉得思路顺畅了很多虽然那道题更复杂但底层思维模型是一样的。8. 最后的操作建议与个人体会如果让我给一个明确的建议那就是先动手把 0 到 15 的二进制和 1 的个数列表亲手列一遍然后不看任何题解尝试找出数字之间的递推关系。这个过程花不了十分钟但比看十篇题解都管用。我自己当时列完表之后首先发现的规律就是偶数、奇数的差异然后才想到右移一位这个操作。说实话这个发现过程比记住公式本身重要得多。因为面试的时候你当场写出的不是“背下来的 dp 公式”而是“从问题中现场推导出来的递推关系”。另外一个体会是这道题很适合用来练“先讲暴力解再讲优化解”的面试节奏。你可以在白板上先写一个 O(n log n) 的解法然后盯着它想一想“哪里重复了”再逐步改进。这种从差到好的演进过程本身就是面试官非常乐意看到的思考路径。最后再分享一个小技巧刷题时不要只在一个语言里写一遍就完事。同一个解法用 Python 写完再用 Java 或 C 各写一遍你对位运算优先级的敏感度会提升很多而且面试的时候不管面试官要求用什么语言你都不会慌。338 这道题作为练手再合适不过了。