首页 百科大全文章正文

二进制中1的个数：3行代码搞定的面试题

百科大全 2025年08月08日 00:54 2 admin

在面试中，位运算相关的题目总能难倒一批人。今天我们来拆解一道经典面试题：如何快速计算一个整数的二进制表示中1的个数（包括负数的补码情况）。

问题本质：看透二进制的小秘密

二进制中1的个数：3行代码搞定的面试题

先看一个有趣的现象：
对于任意整数n，n-1的二进制会把n最右边的1变成0，而这个1右边的所有0都会变成1。比如：

  • n = 1100（二进制），n-1 = 1011
  • 两者做与运算：1100 & 1011 = 1000，相当于「干掉」了最右边的一个1

规律：每执行一次n = n & (n-1)，就会消除n中最右边的一个1。直到n变成0，执行了多少次就是有多少个1！

代码实现：简洁到离谱

C++版本

class Solution {public:    int NumberOf1(int n) {        int count = 0;        while(n) {            ++count;            n = (n - 1) & n;        }        return count;    }};

Python版本（处理负数）

Python中负数用补码表示，直接运算会有问题。通过n & 0xffffffff可将负数转为32位无符号数处理：

# -*- coding:utf-8 -*-class Solution:    def NumberOf1(self, n):        count = 0        if n < 0:            n = n & 0xffffffff  # 处理负数补码        while n:            count += 1            n = n & (n - 1)        return count

更直观的Python写法

直接遍历32位二进制的每一位：

# -*- coding:utf-8 -*-class Solution:    def NumberOf1(self, n):        return sum([(n >> i & 1) for i in range(32)])

为什么这样高效？

  • 时间复杂度：O(k)，其中k是二进制中1的个数（最坏情况32次循环）
  • 空间复杂度：O(1)，只需要几个变量

相比暴力遍历32位的方法，第一种算法在1的个数较少时更高效（比如计算1000000的二进制1的个数，只需1次循环）。

小试牛刀

  • 输入5（二进制101）→ 输出2
  • 输入-1（补码全为1）→ 输出32
  • 输入0 → 输出0

这个技巧你get了吗？下次面试遇到位运算问题，不妨从「消去最右边的1」这个角度想想~

相关文章

发表评论

泰日号Copyright Your WebSite.Some Rights Reserved. 网站地图 备案号：川ICP备66666666号 由Z-BlogPHP强力驱动