企业官网建设流程全解析

1. 为什么这道题值得反复琢磨

刷题刷到“Counting Bits”的时候，我第一反应是“这不就是数二进制1的个数吗”，直接循环调内置函数就行。但真正把这道题吃透之后才发现，它几乎把位运算和动态规划最经典的那几个套路都串起来了。LeetCode 338，题目本身不难，但能写出 O(n log n) 的暴力解不难，能写出 O(n) 的 DP 解才算真的理解了位运算的本质。这篇文章我按自己的实战经验，从暴力解法讲起，逐层拆到最优解，还会把题目背后最常用的位运算技巧一次性梳理清楚。

适合正在准备算法面试的开发者，也适合那种“位运算总是似懂非懂、遇到就发怵”的人——看完这篇文章，你至少能掌握两个递推式，碰到类似题目也能比对着套思路。

1.1 题目到底在问什么

题目描述很简洁：给定一个非负整数num，对于0 <= i <= num范围内的每个数字i，计算其二进制表示中1的个数，并将它们作为数组返回。

举个例子：

输入: num = 5 输出: [0, 1, 1, 2, 1, 2]

对应的二进制是0 -> 0，1 -> 1，2 -> 10，3 -> 11，4 -> 100，5 -> 101，所以 1 的个数分别是0, 1, 1, 2, 1, 2。

这道题看起来是个纯计算题，但它真正的考点在于：你能不能利用已经算出来的结果，去推导新的结果？这就是动态规划的核心思想——用已知推未知，而不是每次都从零开始数。

1.2 暴力解法：简单但不高效

最直接的办法就是遍历0到num，对每个数字单独算二进制中 1 的个数。计算单个数字的方法有很多，比如不断取模判断最低位，或者利用内置函数，但整体复杂度是 O(n log n)。

以 Python 为例：

def countBits(num: int) -> List[int]: ans = [] for i in range(num + 1): # bin(i) 返回二进制字符串，count('1') 统计字符 ans.append(bin(i).count('1')) return ans

这段代码能过，但面试官要是让你手写一个单个数 1 个数的函数，你至少得知道比特位操作怎么写：

def count_ones(x): count = 0 while x: count += x & 1 x >>= 1 return count

暴力解的复杂度是 O(n log n)，因为对每个i都要进行约log2(i)次循环。对于num = 10^5这种规模，性能已经肉眼可见地变差。这是一道典型“能做出来但拿不到加分项”的题目，想优化，就得考虑用空间换时间。

2. 高效解法核心：动态规划 + 位运算

先抛出最终结论：Counting Bits 的高效解法都可以归为“递推式 + DP 数组”。你只要找到当前数字与前一个数字（或之前某个数字）在二进制上的关系，就能把时间复杂度压到 O(n)。

2.1 第一个递推式：右移一位 + 最低位

观察二进制数的规律。数字i的二进制表示，和i >> 1（右移一位）的二进制表示有什么关系？

举个例子：

i = 5 (101) -> i >> 1 = 2 (10) i = 6 (110) -> i >> 1 = 3 (11) i = 7 (111) -> i >> 1 = 3 (11)

右移一位相当于去掉最低位。那么i的 1 的个数，就等于“去掉最低位后的数”的 1 的个数，再加上最低位本身是不是 1。写成公式：

dp[i] = dp[i >> 1] + (i & 1)

i & 1如果等于 1，说明最低位是 1；如果等于 0，说明最低位是 0。这个递推式几乎不需要额外空间，我们只需要一个数组存结果，然后按顺序从 1 算到num。

核心代码（C++）：

vector<int> countBits(int num) { vector<int> dp(num + 1, 0); for (int i = 1; i <= num; ++i) { dp[i] = dp[i >> 1] + (i & 1); } return dp; }

2.2 第二个递推式：清零最低位 + 1

另一个同样经典的递推式利用了i & (i - 1)这个操作。i & (i - 1)的作用是“将二进制表示中最右侧的 1 变成 0”，这个技巧在好多位运算题目里都会用到，比如判断一个数是不是 2 的幂。

当你把i的最低设置位清零之后，得到的新数字一定比i小，所以它的 dp 值已经算出来了。于是：

dp[i] = dp[i & (i - 1)] + 1

为什么加 1？因为i & (i - 1)相对于i，只是少了一个 1，1 的个数自然少一个。

同样用 C++ 实现：

vector<int> countBits(int num) { vector<int> dp(num + 1, 0); for (int i = 1; i <= num; ++i) { dp[i] = dp[i & (i - 1)] + 1; } return dp; }

2.3 两种解法到底有什么区别

从结果来看，两个递推式的时间复杂度都是 O(n)，空间复杂度都是 O(n)，而且都只需要一次循环。但实际写的时候感受不太一样：

• 第一种dp[i >> 1] + (i & 1)更直观，跟二进制移位关系紧密，新手容易理解。
• 第二种dp[i & (i - 1)] + 1更精炼，但需要先理解i & (i - 1)这个操作的含义。

我个人在面试时会更倾向于先说第一种，因为可以从“右移一位相当于除以 2，最低位通过与 1 判断”这个角度讲清楚，逻辑链完整。第二种可以作为“如果你熟悉位运算，还可以这样优化”的补充，展示你的知识广度。

还有第三种进阶解法：根据最高有效位分组。dp[i] = dp[i - highBit] + 1，其中highBit是不超过i的最大 2 的幂。这个思路也能过，但不如前两个简洁，这里就不详细展开了。

3. 位运算技巧，一次整理到位

这道题里涉及到的位运算技巧并不复杂，但都是高频考点。我把它们拆开讲，配合例子，方便以后遇到类似题目直接联想。

3.1 基础位运算符号速查

这里不啰嗦理论，直接用表列出最常用的几个：

在这道题里，最重要的就是&和>>，因为它们直接对应两个递推式中的操作。

3.2 两个必须记住的位运算套路

套路一：x & (x - 1)清除最低位的 1

这个操作的核心是：x - 1会让最低位的 1 变成 0，同时让该位右边的所有 0 变成 1，然后与原来的x相与，自然把最低位的 1 以及它右边的所有位都清了。

举例：

x = 12 (1100) x - 1 = 11 (1011) x & (x - 1) = 8 (1000)

原来 12 有 2 个 1，清掉最低位的 1 后变成了 8，只剩 1 个 1。这个操作在 Counting Bits 的第二个递推式中直接派上用场。

同样的套路还可以用来判断 2 的幂：如果x > 0且x & (x - 1) == 0，那么x就是 2 的幂。

套路二：x & 1判断最低位是不是 1

二进制最低位只有 0 和 1 两种可能。任何整数与 1 做按位与，结果就是最低位的值。这个判断在第一个递推式里用来确认右移后丢掉的那一位是否需要补一个 1。

有的同学会问：为什么不用x % 2来判断奇偶？从结果上看是一样的，但&操作通常比取模更快，而且在位运算类题目里，用位运算更加自然，也便于和其它操作组合。

3.3 面试中如何快速写出位运算解法

我自己的习惯是拿到题目先别急着写代码，先在草稿纸上列一小段数字的二进制，比如从 0 到 7：

0: 0000 -> 0 1: 0001 -> 1 2: 0010 -> 1 3: 0011 -> 2 4: 0100 -> 1 5: 0101 -> 2 6: 0110 -> 2 7: 0111 -> 3

然后盯着这串数列找规律。你会发现：

• 1和2的个数一样，因为1左移一位就是2。
• 3的个数等于1的个数加 1，因为3 = 2 + 1，最低位多了一个 1。
• 所有的偶数2k，它的 1 的个数和k一样，因为左移一位只是把 1 们往前挪了，没增加也没减少。
• 所有的奇数2k+1，它的 1 的个数比k多 1，因为末尾多了一个 1。

把这两条规律合并，就得到dp[i] = dp[i >> 1] + (i & 1)。所以遇到位运算题目，先手动枚举一小段，规律自然就出来了。这是最实操的解题思路，比硬背公式靠谱得多。

4. 多语言代码实现与细节

同一个递推式，不同语言的写法差异不大，但有一些细节值得注意。

4.1 C++ 实现与常见坑

C++ 版本最干净，直接开一个vector<int>，初始化为 0，然后循环赋值即可：

class Solution { public: vector<int> countBits(int num) { vector<int> dp(num + 1, 0); for (int i = 1; i <= num; ++i) { dp[i] = dp[i >> 1] + (i & 1); // 用右移 + 最低位 // 或者 dp[i] = dp[i & (i - 1)] + 1; } return dp; } };

需要注意的坑：

• num可能为 0，此时dp长度为 1，循环不会执行，直接返回[0]，没问题。
• 如果题目要求num很大，比如10^5甚至更大，vector<int>的空间约为4 * (num+1)字节，控制在几百 KB 内，没问题。但如果题目改了，要求返回所有数字的个数，而num达到10^8量级，就要考虑内存优化了（后面会讲）。
• 有的编译器在循环里写i >> 1和i & 1时，要注意运算符优先级。&的优先级低于+，但高于==，所以在复杂表达式中最好加括号。上面代码已经有括号，安全。

4.2 Python 实现与性能细节点

Python 版本：

class Solution: def countBits(self, num: int) -> List[int]: dp = [0] * (num + 1) for i in range(1, num + 1): dp[i] = dp[i >> 1] + (i & 1) return dp

Python 里i >> 1和i // 2效果一致，但位运算在表达上更贴合本题。另外，Python 列表的创建[0] * (num + 1)很快，不用append是因为提前分配好内存更快，也避免动态扩容的小开销。

如果num特别大，比如10^7，Python 的列表内存可能吃不消，因为每个整数对象占用空间远不止 4 字节。此时要考虑数组模块array('I')或者bytearray（因为 1 的个数不会超过二进制位数，对于 32 位整数，最大值 32，用一个bytearray就够）。不过 LeetCode 上num不超过10^5，普通列表完全没问题。

4.3 Java 实现和微妙差异

Java 版本：

class Solution { public int[] countBits(int num) { int[] dp = new int[num + 1]; for (int i = 1; i <= num; i++) { dp[i] = dp[i >> 1] + (i & 1); } return dp; } }

Java 的int[]默认初始化为 0，所以只需要处理i >= 1的情况。这里有一个小细节：Java 中>>是带符号右移，对于正数没问题；如果题目扩展到负数，>>和>>>的区别就要注意。但本题明确是非负整数，所以放心用。

对比三种语言，表达上几乎没有差别。所以这道题考的不是语法，而是你在面试时能不能说出递推式的推导过程。代码只要写对一次循环，剩下的就是背诵功夫。

5. 常见错误与调试心得

这道题代码量很小，但新手写的时候还是有几个容易踩的坑。我结合自己做题和帮别人 review 代码的经验，列一下高频问题。

5.1 边界条件处理错误

最常见的错误是循环从0开始，然后写dp[0] = dp[0 >> 1] + (0 & 1)，这虽然不会越界，但完全没有意义，纯粹浪费一次计算。更好的做法是初始化dp[0] = 0（默认值），循环从1开始。

另一个边界问题是num为0时，如果代码写成：

vector<int> dp(num + 1); for (int i = 1; i <= num; ++i) { ... }

这没问题，循环不执行。但如果你写成了while (num--)之类的，就很容易把数组长度搞错，返回[0]或[]是常有的事。建议直接记住：返回数组长度是num + 1。

5.2 整型溢出与移位问题

严格来说，Counting Bits 的num不会大到让dp[i]溢出，因为int二进制最多 32 个 1，而num本身也不可能是负数。但如果你扩展一下场景，比如计算一个 64 位数的 1 个数，那么结果最大是 64，依然不会溢出int。真正需要小心的是左移操作：比如1 << 31在 Java 中会变成负数，因为整型溢出。虽然这道题不涉及，但在位运算综合题目中经常出现，平时就要养成 “敏感” 的习惯。

如果你在实现中用了i << 1而不是i >> 1，那就会越界，因为i << 1大于i，无法保证dp[i]已经计算。所以递推式必须从i的较小值转移到较大值，这一条可以当作检错原则：检查递推式中下标是否小于当前值。

5.3 时间与空间的权衡思路

这道题最优解是 O(n) 时间 + O(n) 空间。有没有办法压缩空间？比如只用一个数组肯定是必须的，但如果题目要求你不能用额外数组，只让你从 0 打印到 num 每个数的 1 个数，那就不存在 DP 了，只能每个数重新计算，复杂度回到 O(n log n)。所以这个 O(n) 空间的辅助数组是必要的，不需要纠结省那一两个字节。

我在一次实际做题时，尝试用数组存下所有结果，然后在一次循环中重复利用。实测num = 10^5时，两种递推式的运行时间几乎没有区别，都是几个毫秒。所以不要纠结用哪个递推式更好，重要的是你理解并能在纸上画出来。

5.4 调试小技巧：打印中间结果

如果你第一次写递推式，建议打印出dp数组的前几项，对照手动枚举的结果检查。比如写一个简单的循环，把dp[0]到dp[15]打出来，再用 Python 的bin(i).count('1')验证。这种“对拍”的方法虽然笨，但非常有效，能快速确认公式有没有写反。

我经常见到一些人直接抄公式，抄完发现答案不对，然后开始瞎猜。其实只要花一分钟写一个暴力验证函数，就能定位问题是出在i >> 1还是i & 1上，效率高得多。

6. 从这道题延伸出的思维方法

Counting Bits 虽然只是 LeetCode 上的一道简单题，但它背后代表了一类“利用前一个计算结果推导当前结果”的问题。这类问题的思维方法，可以在很多题目中复用。

6.1 这类题目的通用思路：定义状态 + 找转移方程

动态规划的核心不是记代码，而是定义状态和写出转移方程。Counting Bits 的状态就是dp[i]表示数字i的二进制中 1 的个数。关键在于如何找到i与某个较小值的关系。

常见的关系有三种：

• 利用最低位：i与i >> 1的关系。
• 利用最低设置位：i与i & (i - 1)的关系。
• 利用最高位：i与i - highBit的关系。

类似地，你还会遇到很多题目，比如“判断一个数是否为 2 的幂”可以用n & (n-1)；“找只出现一次的数字”可以用异或；“格雷码”生成也依赖位运算递推。这些都是一个体系的。

6.2 面试中如何一步步推导而不卡壳

面试现场最怕的就是“明明知道答案但讲不出来”。我的建议是：

1. 先说暴力解，明确复杂度，让面试官知道你有基础的保底方案。
2. 然后画一个 0 到 7 的二进制表，说“我准备从二进制规律入手”。
3. 指出偶数与右移一位的关系，奇数与右移一位加 1 的关系，顺势推出递推式。
4. 最后写代码，并主动分析时间和空间复杂度。

这个流程既展示了你的思考过程，也把难题变成了一个顺理成章的结论。如果你还能顺带提一句“还可以用n & (n - 1)递推，思路一样”，面试官一般都会认可。

6.3 扩展到更多位运算题目

掌握了 Counting Bits 之后，建议继续刷这几道题巩固：

• 位 1 的个数（LeetCode 191）：单独求一个数的 1 个数，正好用到n & (n - 1)循环。
• 2 的幂（LeetCode 231）：n > 0 && (n & (n - 1)) == 0。
• 只出现一次的数字（LeetCode 136）：利用a ^ a = 0。
• 颠倒二进制位（LeetCode 190）：移位和按位或的组合应用。

这些题目和 Counting Bits 都属于“位运算”专题，刷下来你会发现自己的位运算敏感度明显提升。

拿我自己来说，以前看到位运算头就大，总觉得那是“装逼技巧”。后来刷了几道题，才意识到位运算是处理器原生支持的操作，在很多场景下就是比算术和逻辑判断更直接。Counting Bits 这道题是极好的入门切入点，代码短、规律明显、递推式优美，非常适合用来建立信心。

如果你正在刷题，遇到这类题目别急着跳过，花十分钟把二进制表画出来，自己推一遍公式，收获会比直接背答案大得多。