Sum of Two Integers

def getSum(a, b):
    MASK = 0xFFFFFFFF            # 32 bits
    while b != 0:
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
    if a > 0x7FFFFFFF:           # sign bit set
        a = ~(a ^ MASK)          # back to negative
    return a

Sum of Two Integers. Given two integers, a and b, return their sum without using the plus or minus operators.

Take a equals two and b equals three. The answer is five. Picture each one bit as a bird on a wire: two is one zero, three is one one, and five is one zero one.

The naive way counts up: add one to a, b times. But adding one is still a plus, and it takes b steps, so a billion takes a billion.

Better: add each column on its own. One bird alone means the sum bit is one. That's XOR. Two birds mean the sum bit is zero, and a carry hops one column left. That's AND, shifted left.

So a plus b is the XOR plus the carry, which is another sum. Repeat: a takes the XOR, b takes the carry, until the carry is zero. Two and three give one, carry four. Then five, carry zero.

In code, loop while b is not zero. Python integers never overflow, so mask both to thirty two bits, and negatives work as two's complement. At the end, if a is past the largest positive int, convert it back.

Try eleven plus seven. Round one: XOR twelve, carry six. Round two: ten, carry eight. Round three: two, carry sixteen. Round four: eighteen, carry zero. Eighteen.

Each round, the carry's lowest bit moves at least one place left, so there are at most thirty two rounds. Time is order one, and space is order one.

XOR adds, AND carries, shift and repeat. That's Sum of Two Integers.