Python位运算实现二进制加法：为何需~(a^mask)处理溢出？

我在研究LeetCode「两整数之和」问题时（要求不使用+、-运算符计算两整数a、b的和，输入范围-1000≤a,b≤1000），对解法中当结果a超过32位整数最大值0x7fffffff时，使用~(a ^ mask)而非直接~a的处理逻辑感到困惑。

相关代码 #

def getSum(self, a: int, b: int) -> int:
    
    # 32bit mask
    mask = 0xFFFFFFFF # 8个F代表32位全1

    while True: 
        # 处理加法和进位
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
        if b == 0:
            break

    max_int = 0x7FFFFFFF

    print("A:", a)
    print("Bin A:", bin(a))
    print("Bin M:", bin(mask))
    print("  A^M:", bin(a ^ mask))
    print("~ A^M:", bin(~(a ^ mask)))
    print("  ~ A:", bin(~a))

    return a if a < max_int else ~(a ^ mask)

核心疑问 #

循环结束时，a已经通过&mask完成了32位掩码处理，为什么返回时还要用~(a ^ mask)转换，而非直接对a取反？我查阅了Python按位非运算的资料仍未理解。

示例情况 #

以a=-12、b=-8为例，正确返回结果为-20，代码输出如下：

A: 4294967276
Bin A: 0b11111111111111111111111111101100
Bin M: 0b11111111111111111111111111111111
  A^M: 0b10011
~ A^M: -0b10100
  ~ A: -0b11111111111111111111111111101101

逻辑解析 #

问题根源在于Python的整数是任意精度的，而我们模拟的是32位有符号整数的补码规则：

• 循环中的&mask是把计算结果限制在32位无符号整数范围内，比如-20的32位补码是0xFFFFFFEC，对应十进制的4294967276，这个数在Python中是正整数，但我们需要将其转回符合预期的负整数。
• 直接对a取反（~a）时，Python会把a当作任意精度的正整数处理，取反会将所有高位（不止32位）也翻转，得到-4294967277，这显然不是我们要的-20。
• 而a ^ mask的作用是仅对32位范围内的每一位取反（因为mask是32位全1），得到补码的反码（比如0xFFFFFFEC ^ 0xFFFFFFFF = 0x13）。再对这个反码取反~(a ^ mask)，等价于-( (a ^ mask) + 1 )，正好对应32位补码转原码的规则（补码=反码+1，原码=-补码），最终得到正确的负数-20。

内容的提问来源于stack exchange，提问作者Dracula