本文共 1227 字，大约阅读时间需要 4 分钟。

解决LeetCode‘剑指 Offer’问题——计算二进制中的1的个数

在LeetCode上，剑指 Offer系列题目一直是程序员必备的基础练习。今天，我们来看看题目15，计算一个整数的二进制表示中1的个数。这题看似简单，但对刚入行的程序员来说，可能还是有一些小技巧需要掌握。

问题分析

给定一个整数n，返回其二进制表示中1的个数。例如，n=9的二进制是1001，有2个1，所以程序应该返回2。

双向思路——模拟统计1的位置

最初，我想可能需要按位检查每一位是否为1，这种方法虽然简单，但效率不高。我的思路是，从左到右暴力扫描每一位，判断是否为1，如果是，就计数加一。然而，这种方法的缺点是，当n非常大的时候，会导致大量的循环次数。

换个思路想，对于二进制数来说，每一位其实可以独立处理。每一步，检查当前位是否为1，然后右移n，继续处理下一位。这与我以前学习位运算时学过的“右移逐位处理”思路很像。

但是，二进制数的表示方式可能包括前导零。这种情况下，是否应该考虑前面的零？比如说，当n的二进制形式为0b100000...的时候，前面有很多位是0，我们在统计的时候是否需要忽略这些0？

最优解法——位运算获取1的个数

经过认真分析，我意识到可以利用位运算的特点来高效地解决这个问题。基本思路是这样的：

这一系列的操作很好地体现了位运算的独特优势，避免了逐个检查每一位的低效操作。

位运算的绝学——理解基础符号

在这个解决方案中，主要用到以下位运算符号：

• n & 1：检查当前位是否为1。
• n >> 1：对n进行无符号右移。

理解这些符号的意义非常关键。无符号右移（n >> 1）会将n的所有位全部右移一位，并在最低位补零。这保证了我们可以逐步处理n中的每一位。

代码实现

最终的Python代码大致如下：

def count_ones(n):    res = 0    while n != 0:        res += n & 1        n >>= 1    return res

时间复杂度

这道题的时间复杂度是O(log2(n))，因为每次右移都会将n缩小为原来的二分之一。而空间复杂度为O(1)，因为我们只使用了几个额外的变量。

边界条件

在实际编程中，我们需要特别考虑以下几种特殊情况：

• 当n等于0时，直接返回0。
• 当n的最高有效位是1，例如n=2^k-1（全1二进制数），此时应该返回k位。

这些检查在现实中虽然不影响算法的时间复杂度，但对代码的鲁棒性有一定的提升。

总结

通过分析题目和位运算的特性，我们找到了一个高效的解决方案。这种方法不仅节省了时间，还简化了代码的逻辑。希望这篇文章能为你解答疑惑，帮助你在对抗LeetCode难题中脱颖而出！

转载地址：http://tphqz.baihongyu.com/