剑指11-二进制中1的个数

Posted on | In |

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

  • 整型数占4个字节
  • 负数的补码，等于其相反数的所有二进制位取反，然后加1。

位移运算子特性：

  • 负数的补码最高位1，右移则在最高位补1而不是0。因此负数时要限定位移运算子使用次数。
1
2
3
4
5
6
7
8
9
10
class Solution2:
    def NumberOf1(self, n):
        # write code here
        count = 0
        bits = 32
        while bits > 0:
            bits -= 1
            count += n&1
            n = n>>1
        return count

比较笨，但是对理解原码和补码很有用处。

  • 非负数比较简单，循环除以2直到除尽，累加每轮循环之前2的余数。
  • 负数的话，用长度为32的数组模拟其相反数的各个二进制位，然后各个二进制位取反，然后加1，最后统计这个数组里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
class Solution1:
    def NumberOf1(self, n):
        # write code here
        if n >= 0:
            count = 0
            while n > 0:
                count += n % 2
                n = n >> 1 #等价于 n=int(n/2)
            return count
        else:
            mylist = [0]*32
            i = 0
            n = -n
            while n > 0:
                mylist[i] = n & 1
                i += 1
                n = n >> 1
            for i in range(32):
                mylist[i] = 1-mylist[i]

            toplus = 1
            i = 0
            for i in range(32):
                if toplus == 0:
                    break
                if mylist[i] == 0:
                    mylist[i] = 1
                    toplus = 0
                else:
                    mylist[i] = 0
                    toplus = 1
            count = sum(mylist)
            return count

一个性质：

  • 把一个整数减去1，在和原整数做与运算，会把该整数二进制的最右边一个1变成0。
  • 用与运算的结果替换掉原整数，可以再次进行上述操作。而一个整数的二进制有多少个1，就可以进行多少次这样的操作，使得与运算结果为0。
1
2
3
4
5
6
7
class Solution:
    def NumberOf1(self, n):
        count = 0
        while n != 0:
            count += 1
            n &= n-1
        return count