Sum of Two Integers

1. The obvious way

   Increment one number b times with ++: far too slow.

2. The key insight

   While the carry (b) is not 0: new_sum = a XOR b; carry = (a AND b) shifted left by one; a = new_sum; b = carry. Return a. In Python integers are unbounded, so mask to 32 bits and convert a negative result back.

3. The algorithm
   1. partial = a XOR b.
   2. carry = (a AND b) shifted left one.
   3. Set a = partial, b = carry.
   4. Stop when carry is 0; return a.

Watch it run

6 and 2

def get_sum(a, b):
    mask = 0xFFFFFFFF                                    # keep 32 bits, like a real int
    while b != 0:
        partial = (a ^ b) & mask                         # sum of each column, ignoring carries
        carry = ((a & b) << 1) & mask                    # carries move one column left
        a, b = partial, carry
    return a if a <= 0x7FFFFFFF else ~(a ^ mask)         # turn a 32-bit negative back into a Python negative

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.