Python solution: Bit manipulation (a ripple carry adder!)


  • 0
    K

    Essentially a simple implementation of a ripple carry adder (i.e., a hardware adder).

    class Solution(object):    
        # Without Using + or -
        def getSum(self, a, b):
            """
            :type a: int
            :type b: int
            :rtype: int
            """
            # Carry ripple adder!
            # assume 32 bits & 2s complement
            sum = 0
            cin = 0
            cout = 0
            counter = 0x1
    
            while counter <= 0x080000000: # 32 bits
                a_bit = a&1
                b_bit = b&1
                s = (a_bit ^ b_bit)
                cout = a_bit & b_bit
                if cin:
                    cout = (cin & s) | cout
                    s = s ^ cin
                #print 'i=%d | a=%d b=%d sumb=%d cin=%d cout=%d' % (counter, a_bit, b_bit, s, cin, cout)
                cin = cout
                if s == 1:
                    sum |= counter
                a = a >> 1
                b = b >> 1
                counter <<= 1
    
            # If the final sum is a negative #, the current will be in positive 2's complement number.
            # So we need to convert it to negative 2's complement number.
            MAX = 0x7FFFFFFF
            mask = 0xFFFFFFFF
            if sum > MAX:
                sum = ~(sum ^ mask)
            return sum
    

Log in to reply
 

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