Python solution with detailed explanation


  • 0
    G

    Solution

    Sum of Two Integers https://leetcode.com/problems/sum-of-two-integers/?tab=Description

    Algorithm

    • Build a truth table and implement the truth table. In python, integers are arbit long. Therefore, if the 32nd bit is 1, then you need to subtract 2^32 or subtract 2^31 from the positive part.
             if result & 0x80000000: # 1 in bit number 32
    				 result = (result & 0x7fffffff) - 2**31
                #   result = result - 2**32 # Same thing as above
    
    class Solution(object):
        def getSum(self, a, b):
            """
            :type a: int
            :type b: int
            :rtype: int
            """
            carry = 0
            result = 0
            mask = 1
            for i in range(32):
                a_bit = (a >> i) & mask
                b_bit = (b >> i) & mask
                res = a_bit ^ b_bit ^ carry
                carry = (a_bit&b_bit) | (a_bit&carry) | (b_bit&carry)
                result = result | (res << i)
            # Python has arbit long integers. If the last bit is 1, then we have a negative number in two's complement.
            # However, it will be treated as a positive number. Therefore, take the positive part out and remove -2**31
            # Another alternate way is to remove 2**32
            if result & 0x80000000: # 1 in bit number 32
                result = (result & 0x7fffffff) - 2**31
                #   result = result - 2**32 # Same thing as above
            return result   
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.