Counting Bits LeetCode 高效解法解析与位运算技巧

Counting Bits是LeetCode第338题，要求计算从0到给定整数n之间每个数字的二进制表示中1的个数。这个问题看似简单，但高效解法涉及位运算和动态规划的巧妙结合，是面试中考察候选人算法思维能力的经典题目。

counting bits leetcode题目是什么意思

这道题给定一个非负整数n，需要返回一个长度为n+1的数组，其中第i个元素表示数字i的二进制形式中1的个数。例如，当n=5时，二进制表示分别为0(0), 1(1), 2(10), 3(11), 4(100), 5(101)，所以应该返回[0,1,1,2,1,2]。题目要求时间复杂度尽可能低，避免对每个数字单独计算。

理解题目后，最直接的思路是对每个数字计算其二进制中1的个数，但这会导致O(nsizeof(integer))的时间复杂度。在实际面试中，面试官通常期待更优的解法，这就需要我们深入分析数字二进制表示的内在规律。

counting bits leetcode如何高效解决

高效解决Counting Bits问题的关键在于发现相邻数字二进制表示之间的关系。通过观察可以发现，对于任意偶数i，其二进制中1的个数等于i/2的二进制中1的个数，因为偶数二进制最后一位是0，右移一位相当于除以2。对于奇数i，其二进制中1的个数等于i/2的二进制中1的个数加1。

基于这个规律，我们可以推导出状态转移方程：bits[i] = bits[i>>1] + (i & 1)。这里i>>1表示i右移一位（即除以2），i & 1用于判断i是否为奇数。这种方法只需一次遍历即可完成计算，时间复杂度为O(n)，空间复杂度也为O(n)。

counting bits leetcode动态规划解法

上述解法本质上是一种动态规划思路，其中bits[i]表示状态，即数字i的二进制中1的个数。状态转移基于已计算的较小数字的结果，充分利用了子问题的解。具体实现时，初始化bits[0]=0，然后从1遍历到n，根据状态转移方程计算每个bits[i]。

在实际编码中，这个解法非常简洁高效。Python实现只需几行代码：def countBits(n): bits = [0]

(n+1); for i in range(1, n+1): bits[i] = bits[i>>1] + (i & 1); return bits。这种解法不仅高效，而且体现了将问题分解为子问题并重复利用结果的动态规划核心思想。

你在解决Counting Bits问题时是否考虑过其他优化方法？在实际面试中遇到这道题，你通常会如何向面试官解释解题思路？欢迎在评论区分享你的经验和看法，如果觉得这篇文章有帮助，请点赞和分享给更多正在准备技术面试的朋友。