0371._sum_of_two_integers.md

Navigation

• Navigation
• Links
• Solution 1 built-in sum
• Solution 2 位运算

Links

1. https://leetcode.com/problems/sum-of-two-integers/
2. https://leetcode-cn.com/problems/sum-of-two-integers/

Solution 1 built-in sum

okay, okay, no operators like "-", "+" :)

class Solution:
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        return sum([a, b])

Solution 2 位运算

1. a + b 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)
2. 无进位加法使用异或运算计算得出
3. 进位结果使用与运算和移位运算计算得出
4. 循环此过程，直到进位为 0

在 Python 中，整数不是32位，一直循环左移并不会存在溢出的现象，需要手动模拟 32 位 INT 整型。

class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        # 2^32
        MASK = 0x100000000
        # 整型最大值
        MAX_INT = 0x7FFFFFFF
        MIN_INT = MAX_INT + 1

        while b != 0:
            # 计算进位
            carry = (a & b) << 1 
            # 取余范围限制在 [0, 2^32-1] 范围内
            a = (a ^ b) % MASK
            b = carry % MASK
        
        return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)   # > 0x7fff ffff的数字转换成负数