剑指offer——二进制中1的个数（解释n & 0xFFFFFFFF）[通俗易懂]

全栈程序员-站长 • 2022年5月16日下午3:20 • 未分类 • 阅读 39

大家好，又见面了，我是你们的朋友全栈君。

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

解答如下：
环境： python 2.7.3

正数的原码反码补码都一样
负数的补码是其对应正数的反码加1

这里需要弄清楚为什么python中负数需要和 0xFFFFFFFF 做与操作？
在计算机中，所有的数字都是使用补码存储起来的。由于Python没有位数这个概念，所以得到二进制表示需要多一点操作，即将位数限制在32位，通过和一个32位的全1数字按位与运算即可。对于正数来说，上面的按位与操作可以不做，因为正数的符号位为0，补码即原码，所以前面的数字全为0，按位与没有意义。但对于负数来说，直接bin(-1)是不能得到其补码的，而是得到了1的原码前面加上了负号，即-0b1。则通过和一个32位的全1数字按位与运算可得到其补码二进制表示对应的十进制数（按位与运算把符号位的1视为了数字）。
在这里插入图片描述
方法一：转换成字符串，然后统计1的个数。

class Solution:
    def NumberOf1(self, n):
        # write code here
        #与操作是对n补码的与操作
        n = 0xFFFFFFFF & n 
        count = 0
        for c in str(bin(n)):
            if c == "1":
                count += 1
        return count

方法二：按位与，统计1的个数。
这个不需要多解释，1做左移运算，右边补0，然后和n相与。

class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0
        for i in range(32):
            mask = 1 << i
            if n & mask != 0:
                count += 1
        return count

方法三：n和n-1相与
n和n-1做与操作就是把n的二进制的最后一个1变为0，知道n的二进制变为
全0，这样就统计出了1的个数。

class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0
        while n:
        	if n < 0:
        		n = 0xFFFFFFFF & n
            n = n & (n-1)
            count += 1
        return count