面试题15：二进制中1的个数

题目：https://www.nowcoder.com/ta/coding-interviews

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

求整数的补码：

1、正整数的补码是其二进制表示，与原码相同；

例如：5（00000101）

2、负整数的补码：将其对应正数二进制表示所有位取反（包括符号位，0变1，1变0）后加1。

例如：-5对应正数5（00000101）→所有位取反（11111010）→加1(11111011)

根据补码求原码：

已知一个数的补码，则对应原码为：对该补码再求补码。

python中得到一个数n的补码：n & 0xffffffff(这个做法来自网络，具体原因未知)，
所以直接的做法如下：

class Solution1:
    def NumberOf1(self, n):
        if n < 0:
            n = n & 0xffffffff
        return bin(n).count('1')

1
2
3

method = Solution1()
answer = method.NumberOf1(-1)
answer

把一个整数减去1之后再和原来的整数做按位与，得到的结果相当于是把整数的二进制表示中最右边的一个1变成0,一个整数的二进制表示有多少个1则可以进行多少次这样的操作

根据上述特点可以得到一种求解方案，这也是《剑指offer》一书提供的精巧思路

class Solution2:
    def NumberOf1(self, n):
        count = 0
        if n < 0:
            n = n & 0xffffffff#得到负数的补码，计算机中负数以二进制补码形式存在
        while n:
            n = n & (n-1)
            count += 1#count =count + 1
        return count

1
2
3

method = Solution2()
answer = method.NumberOf1(-1)
answer

以下也是一种特别的方案，来自参考链接中的博主。

具体是：将负数-n转换为正n，然后计算(n-1)中的1的位数，再用32减之，刚好得到负数补码中1的位数

class Solution3:
    def NumberOf1(self, n):
        if n>=0:
            count = bin(n).count('1')
        else:
            n=abs(n)
            count = 32 - bin(n-1).count('1')#和之前Solution2中的做法的联系是什么？
        return count

1
2
3

method = Solution3()
answer = method.NumberOf1(-1)
answer

bin(-11)

'-0b1011'

1	bin(-11).replace('0b','')

'-1011'

移位操作：（确定位长）

class Solution4:
    def NumberOf1(self, n):
        count = 0
        for i in range(0,32):
            if n & 1:#与1做位与
                count = count + 1
            n = n >> 1#右移n，舍弃最右位，最左尾添0。右移一次，丢弃最右一个‘1’。
        return count

1
2
3

method = Solution4()
answer = method.NumberOf1(-1)
answer

另一种移位操作：（确定位长）

class Solution5:
    def NumberOf1(self, n):
        count = 0
        operator = 1
        for i in range(0, 32):#32位
            if n & operator:#带判断数n与操作数operator做位与
                count = count + 1
            operator = operator << 1#操作数operator左移，而不是n右移。左移一次，消掉最右一个‘1’。
        return count

1
2
3

method = Solution5()
answer = method.NumberOf1(-1)
answer

参考：
1、https://blog.csdn.net/Datawhale/article/details/82182612

2、https://blog.csdn.net/fuxuemingzhu/article/details/79512764

1
2

面试题15：二进制中1的个数

谢谢大爷~