为何无法用XOR、AND和左移实现整数加法？附LeetCode测试情况

先逐个分析你尝试的三个版本代码的问题，再解释最终正确代码的工作原理：

第一个版本：正数正常，负数超时 #

class Solution:
    def getSum(self, a: int, b: int) -> int:
        while b:
            withoutcarry = (a ^ b)
            b = (a & b) << 1
            a = withoutcarry
        return a

这个代码的核心逻辑是对的：用a^b计算无进位和，(a&b)<<1计算进位，循环直到进位为0。但问题出在Python的整数特性上——Python的整数是任意精度的，负数用无限位补码表示（比如-1是无限个1的二进制串）。当处理负数时，进位会无限左移，永远无法清零，导致循环死循环（比如a=-1、b=1的情况）。

第二个版本：解决超时，但边界用例出错 #

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xffffffff
        while b:
            sum_ = (a ^ b) & mask
            carry = ((a & b) << 1) & mask
            a = sum_
            b = carry
        if (a >> 31) & 1:
            return ~(a ^ mask)
        return a

加入0xffffffff（32位全1）掩码是为了模拟32位有符号整数的行为，把运算限制在32位内，解决了循环超时的问题。但在a=-1、b=0的用例中出错，原因是：

• 当b=0时，循环不执行，a还是Python原生的无限位负数（-1）
• 判断(a >>31)&1时，-1右移31位还是-1，与1按位与结果为1，进入负数还原分支
• a^mask会把无限位的-1和32位全1的掩码异或，得到前面无限个1、后面32位0的数，取反后变成前面无限个0、后面32位1的数，也就是正数4294967295，而非正确的-1

第三个版本：通过所有测试用例的原理 #

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xffffffff

        while b != 0:
            tmp = (a & b) << 1
            a = (a ^ b) & mask
            b = tmp & mask

        if a > mask // 2:
            return ~(a ^ mask)
        else:
            return a

这个代码完美解决了前两个版本的问题，细节拆解：

1. 掩码的核心作用 #

0xffffffff是32位全1的十六进制数，用来模拟32位有符号整数的运算范围。每次运算后用& mask截断，确保a和b始终是32位范围内的正数（Python中没有无符号整数，这里用正数表示32位补码），避免了无限进位的问题。

2. 位运算加法的逻辑不变 #

• a ^ b：计算两个数的无进位和（异或运算，相同位为0、不同位为1，对应加法中不进位的情况）
• (a & b) << 1：计算进位（与运算找到同时为1的位，左移1位就是进位的位置）
• 循环直到进位b为0，此时a就是32位补码表示的和

3. 负数的正确还原 #

32位有符号整数的最高位（第31位）是符号位，mask//2等于0x7fffffff（2^31-1），这是32位有符号整数的最大值：

• 如果a大于这个值，说明a的最高位是1，代表这是一个负数的32位补码（比如-1的32位补码是0xffffffff，大于0x7fffffff）
• a ^ mask：把32位补码的每一位取反（因为mask是全1，异或等价于按位取反）
• ~(a ^ mask)：对取反后的结果再取反，得到Python原生的负整数（比如0xffffffff ^ mask是0，~0就是-1）

4. 边界用例的处理 #

当b=0时，循环不执行：

• 如果a是正数，直接返回即可
• 如果a是负数（比如-1），此时a > mask//2不成立（-1 < 2147483647），直接返回a本身，避免了第二个版本中对无限位负数的错误判断

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