企业官网建设流程全解析

刷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 这六个数字的二进制分别为：

所以返回结果就是[0, 1, 1, 2, 1, 2]。

这个题目本身不难理解，难的是它的附加要求：你能不能做到时间复杂度 O(n)？也就是说，你不能真的挨个把每个数字转换成二进制再数一遍，那样时间复杂度会到 O(n log n) 甚至更差。题目真正想考的是：你能否利用相邻数字之间的二进制关系，把前面已经算好的结果复用起来。一句话概括，这就是动态规划的思路。

1.2 为什么这道题能进 Hot100

Hot100 的选题标准向来不是“最难”，而是“最典型”。338 题涉及的核心知识点有三个：位运算、动态规划、递推关系。这三个东西几乎出现在每一轮算法面试里，而 338 题恰好把三者放在了一个不到二十行的代码里。

更关键的是，它不像很多 DP 题那样需要你定义复杂的二维状态，也不需要你维护什么dp[i][j]，它只有一个一维数组，而且状态转移极其优美。这种“看起来很简单，但你就是想不出来”的题目，恰恰是面试官最爱出的。如果能把 338 题的递推逻辑讲明白，至少说明你对二进制和 DP 的基础不是死记硬背的。

2. 解法演进：从暴力到动态规划

2.1 解法一：逐个数统计（暴力法）

最容易想到的办法，肯定是对 0 到 n 的每个数字单独统计 1 的个数。统计单个数字二进制中 1 的个数，可以用一个循环每次右移一位，然后看最低位是不是 1：

def 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 的二进制是 10，1 的二进制是 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 = 0，dp[i] = dp[i >> 1]；当 i 是奇数时，i & 1 = 1，dp[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 的二进制全部列了一遍，才真正看明白：

你会发现，每个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 dp

i & (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)，然后在循环体里同时处理 i=0 的情况，虽然逻辑上没错，但会多一次无意义的赋值。更干净的做法是从 1 开始。

还有一个小细节：题目给的 n 是非负整数，所以 n=0 的时候，返回[0]。这个边界条件千万不能漏，我见过不少人在代码里默认 n ≥ 1，导致 n=0 时数组越界或者返回空列表。在 LeetCode 上，这种问题会直接判 Wrong Answer，非常可惜。

4. 复杂度与边界条件分析

4.1 三种解法复杂度对照

注意，题目要求的返回值本身就是一个长度为 n+1 的数组，所以空间复杂度 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: vector<int> countBits(int n) { vector<int> 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)在 n=0 时是[0]，恰好正确，所以 Python 写起来比较省心。但如果你习惯先初始化长度为 n 的数组，然后在循环里 append，就要特别小心 n=0 的情况。

再说一个更隐蔽的坑：如果你用最高有效位的写法，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 题真的需要动态规划吗？暴力不也能过吗？”确实，在 n=10^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 题的思路之后，有几个同类的题目你可以顺带刷掉：

• 191. 位1的个数：单个数统计 1 的个数，Brian Kernighan 算法的直接应用。
• 231. 2 的幂：判断一个数是不是 2 的幂，n & (n - 1) == 0。
• 268. 丢失的数字：可以用位运算异或解决，但也可以用和值相减法。
• 476. 数字的补数：跟按位取反有关，注意处理前导零。
• 137. 只出现一次的数字 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, f"n={n}, expected={expected}, got={result}" print(f"n={n}: {result} OK") # 性能测试 import time start = time.time() result = countBits(100000) print(f"n=100000 耗时: {time.time() - start:.4f} 秒")

我自己跑下来，n=100000的情况下，O(n) 的 DP 解法耗时在 0.005 秒左右，体感上是瞬间完成。暴力法的耗时大约是 0.03 秒，看着也很快，但一旦把 n 放大到 10^7，DP 的优势就会非常明显。

6.2 验证递推公式的正确性

如果你对dp[i] = dp[i >> 1] + (i & 1)这个公式还有疑虑，可以用一个笨办法来验证：把每个数字的二进制写出来，手动比对。

以 i=7 为例，7 的二进制是 111。i >> 1 = 3，3 的二进制是 11，1 的个数是 2。i & 1 = 1，所以 7 的 1 的个数应该是 3。而 7 的二进制 111 确实有 3 个 1，验证通过。

再以 i=10 为例，10 的二进制是 1010。i >> 1 = 5，5 的二进制是 101，1 的个数是 2。i & 1 = 0，所以 10 的 1 的个数是 2。而 1010 里确实是两个 1，验证通过。

这种手动验证做上几个数字之后，公式就不再是死记硬背，而是变成了一种直觉。

6.3 常见报错与排查方法

写这道题时，我遇到过三个最常见的报错：

第一个是数组越界。如果初始化dp = [0] * n，那么下标dp[n]就会越界。正确写法是[0] * (n + 1)，多留一个位置。这个错误在 n=0 的时候不一定暴露，但只要 n ≥ 1，跑dp[i >> 1]时很可能就崩了。

第二个是循环起始下标错了。从 0 开始循环，dp[0] = dp[0] + 0，虽然不会越界，但纯属浪费；如果你在循环体里用i - 1之类的东西，还可能在 i=0 时出现负下标。建议统一从 1 开始。

第三个是运算符优先级问题。前面提到过i & (i - 1) == 0在某些语言里会和预期不一致。解决办法很简单：所有位运算参与布尔比较时，两侧都加括号。别嫌丑，可靠最重要。

7. 从刷题到面试：这道题怎么说才能加分

7.1 避免“背答案式”讲解

如果你在面试里遇到原题，千万不要上来就默写三行代码。面试官想看的是你的思考过程，而不是结果。比较好的回答顺序是：先说最暴力的思路，比如“我可以对每个数字循环除 2 数 1 的个数，时间复杂度 O(n log n)”；然后说“这个过程中有很多重复计算，因为 i 右移一位就是 i/2，它的 1 的个数我已经算过了”，从而自然引出动态规划。

这个过程看起来简单，但很多候选人栽在“直接跳到最后解法”上。面试官问“为什么 dp[i] 等于 dp[i>>1] 加 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 这道题作为练手，再合适不过了。