在python中不使用“+”运算符的两个整数的总和

Question

需要一些帮助来理解 leetcode 371 的 Python 解决方案。“两个整数的总和”。我发现https://discuss.leetcode.com/topic/49900/python-solution/2是投票最多的 python 解决方案，但我在理解它时遇到了问题。

• 如何理解“% MASK”的用法以及为什么“MASK = 0x100000000”？
• 如何理解“~((a % MIN_INT) ^ MAX_INT)”？
• 当 sum 超过 MAX_INT 时，函数会大喊负值（例如 getSum(2147483647,2) = -2147483647），这不是不正确吗？

---

class Solution(object):

    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        MAX_INT = 0x7FFFFFFF
        MIN_INT = 0x80000000
        MASK = 0x100000000
        while b:
            a, b = (a ^ b) % MASK, ((a & b) << 1) % MASK
        return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)

Answer 1

让我们暂时忽略MASK,MAX_INT和MIN_INT。

为什么这个黑魔法按位工作？

计算工作的原因是因为(a ^ b)将a和的位“求和” b。回想一下，按位异或是指位1不同时和0位相同时。例如（其中 D 是十进制，B 是二进制），20D == 10100B 和 9D = 1001B：

 10100
  1001
 -----
 11101

和 11101B == 29D。

但是，如果你有一个带手提箱的箱子，它就不会那么好用了。例如，考虑将（按位异或）20D 和 20D 相加。

10100
10100
-----
00000

哎呀。20 + 20 肯定不等于 0。输入(a & b) << 1术语。该术语代表每个位置的“进位”。在 while 循环的下一次迭代中，我们添加来自前一个循环的进位。所以，如果我们使用之前的例子，我们会得到：

# First iteration (a is 20, b is 20)
10100 ^ 10100 == 00000 # makes a 0
(10100 & 10100) << 1 == 101000 # makes b 40

# Second iteration:
000000 ^ 101000 == 101000 # Makes a 40
(000000 & 101000) << 1 == 0000000 # Makes b 0

现在b是0，我们完成了，所以返回a。该算法一般适用，不仅适用于我概述的特定情况。正确性证明留给读者作为练习；)

口罩有什么作用？

所有屏蔽做的是确保该值是一个整数，因为你的代码，甚至有评论指出a，b和返回类型的类型的int。因此，由于可能的最大值int（32 位）是 2147483647。因此，如果您将此值加 2，就像您在示例中所做的那样，int溢出并得到负值。您必须在 Python 中强制执行此操作，因为它不遵守int其他强类型语言（如 Java 和 C++）定义的此边界。考虑以下：

def get_sum(a, b):
    while b:
        a, b = (a ^ b), (a & b) << 1
    return a

这是getSum不戴口罩的版本。

print get_sum(2147483647, 2)

产出

2147483649

尽管

 print Solution().getSum(2147483647, 2)

产出

-2147483647

由于溢出。

这个故事的寓意是，如果您将int类型定义为仅表示 32 位，则实现是正确的。