[LeetCode]#371. Sum of Two Integers

Environment: Python 3.7

Key technique: adder, Binary, 32 bit limit

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = -2, b = 3
Output: 1

Analysis:

Use adder to calculate a + b. We can see below example. a and b are 1 and 5. We use “and” logic and search same bit and carry it. In another way, use “xor” logical to find different bit. When the “and” can’t find any same bit, we can return the number.

Solution:

class Solution:
    def getSum(self, a, b):
mask = 0xffffffff
        sum = (a ^ b) & mask
        carry = a & b
        while carry!=0:
            a = sum
            b = (carry << 1) & mask
            sum = (a ^ b) & mask
            carry = a & b
        if sum & 0x80000000:
            sum -= 0x100000000
        return sum

Submitted result:

Lesson learn:

Due to Python doesn’t have 32 bit limit, we need use mask to simulate it. I don’t consider it, so I get many Time Limit Exceeded.

Reference:

https://www.polarxiong.com/archives/LeetCode-371-sum-of-two-integers.html