剑指offer 面试题15. 二进制中1的个数（易）& LeetCode 191.位1的个数（易）

在程序员圈子里有一则流传了很久的笑话，说世界上有10种人，一种人知道二进制，而另一种人不知道二进制……

Tag

位运算

本题考点

考查应聘者对二进制及位运算的理解。 考查应聘者分析、调试代码的能力。如果应聘者在面试过程中采用的是第一种思路，则当面试官提示他输入负数将会出现问题时，面式官会期待他能在心中运行代码，自己找出运行出现死循环的原因。这就要求应聘者有一定的调试功底。

题目

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1： 

1
2
3
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2： 
1
2
3
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3： 
1
2
3
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

直觉

方法一、两次循环（n右移，1不动）

第一次循环计算得到n的位数，第二次循环，逐步对比每一位上的值是否为1。

方法二、一次循环（n不动，1左移）

不右移输入的数字n。首先把n和1做与运算，判断n的最低位是不是为1。接着把1左移一位得到2，再和n做与运算，就能判断n的次低位是不是1……这样反复左移，每次都能判断n的其中一位是不是1。

方法三、惊喜解法

前面的解法中，循环的次数等于整数二进制的位数，32位的整数需要循环32次。下面再介绍一种算法，整数中有几个1就只需要循环几次。

把一个整数减去1，就是将这个整数对应的二进制数的最右边的1变成0，如果它的右边还有0，则所有的0都变成1，而它左边的所有位都保持不变。

例如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1100
 ^
  -1
----
1011
 ^
最右边的1，位于第1位，从1变成了0。

1011
   ^
  -1
----
1010
   ^
最右边的1，位于第3位，从1变成了0。

我们再把1100和1011做位与运算，得到的结果是1000。我们把1100最右边的1变成了0，结果刚好就是1000。同理，把1011和1010做位与运算，得到的结果是1010。我们把1011最右边的1变成了0，结果刚好就是1010。

我们把上面的分析总结起来就是：把一个整数减去1，再和原整数做与运算第会把该整数最右边的1变成0。那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。基于这种思路，我们可以写出新的代码。

代码

  • 方法一、两次循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import unittest
from typing import List


class Solution:
    def hammingWeight(self, n: int) -> int:
        if n < 0: n = abs(n)
        res = 0
        count = 0
        tmp = n
        # 第一次循环
        while tmp:
            tmp //= 2
            count += 1
		# 第二次循环
        for i in range(count):
            if (n >> (count - 1 - i)) & 1 == 0:
                pass
            else:
                res += 1
        return res


class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        inputs = [
            9, 11,  # 功能测试
            2147483647, -2147483648,  # 边界测试 -2147483648 & 2147483647
            0,      # 特殊样例
        ]
        answers = [2, 3, 31, 1, 0]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.hammingWeight(inputs[i]))
        self.assertEqual(res, answers)
 
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    unittest.main()

时间复杂度 \(O(n)\) 空间复杂度 \(O(1)\)

  • 方法二、一次循环（n不动，1左移）
1
2
3
4
5
6
7
8
9
10
class Solution:
    def hammingWeight(self, n: int) -> int:
        if n < 0: n = abs(n)
        res = 0
        flag = 1
        while flag<=n:
            if n & flag:
                res += 1
            flag = flag << 1
        return res

时间复杂度 \(O(n)\) 空间复杂度 \(O(1)\)

  • 方法三、惊喜解法
1
2
3
4
5
6
7
8
class Solution:
    def hammingWeight(self, n: int) -> int:
        if n < 0: n = abs(n)
        res = 0
        while n:
            res += 1
            n = (n-1) & n
        return res

时间复杂度 \(O(n)\) 空间复杂度 \(O(1)\)

举一反三

  • 把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的1变成0。很多二进制的问题都可以用这种思路解决。
  • 用一条语句判断一个整数是不是2的整数次方。一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其他所有位都是0。根据前面的分析，把这个整数减去1之后再和它自己做与运算，这个整数中唯一的1就会变成0。
  • 输入两个整数m和n，计算需要改变m的二进制表示中的多少位才能得到n。比如10的二进制表示为1010，13的二进制表示为1101，需要改变1010中的3位才能得到1101。我们可以分为两步解决这个问题：第一步求这两个数的异或；第二步统计异或结果中1的位数。
  • 判断一个数是不是奇数 if number & 1 == 1: print("{} is odd number".format(number))