Sustie

关于Python中负数的位运算

引言

最近做了一道LeetCode题目，题目本身不难，只需要将两个整数进行按位XOR操作，然后计算结果的二进制表示中1的个数即可。下面是我最初的实现：

a = int(input())
b = int(input())
c = a ^ b
n = 0
while c:
    n += c & 1
    c >>= 1
print(n)

但是这么做会超时，查看题解之后发现原因在于输入的整数有可能是负数，改正后的代码如下：

a = int(input()) & 0xFFFFFFFF
b = int(input()) & 0xFFFFFFFF
c = a ^ b
n = 0
while c:
    n += c & 1
    c >>= 1
print(n)

为什么最初的代码会超时？为什么需要将输入的整数与0xFFFFFFFF进行按位AND操作？这就涉及到Python中对负数进行位运算时，负数的表示方式。

Python中负数的二进制表示

我们知道，在计算机中，负数是以补码的形式存储的，对于一个整数x，其补码为~x+1。在Python中，整数是无限精度的，因此概念上一个整数是有无限多位的，这就导致负数在概念上前面会有无限多个1。举例来说，2的二进制表示为...00010，将其取反就得到...11101，再加1就得到...11110，这就是-2的二进制表示。可以看到，负数的二进制表示中前面有无限多个1。

因此，对一个负数进行右移操作，最终一定会得到...11111，也就是-1，所以我最初的代码无法正确统计负数的二进制表示中1的个数。

在实际实现中，负数到底有几个1取决于其占用的位数。由于题目已经告诉我们输入的整数类型为32位整数，因此我们需要将输入的整数与0xFFFFFFFF进行按位AND操作，去除掉前面多余的1，将其限制在32位范围内。