Sum of Two Integers

Sum of Two Integers asks you to add two numbers without using the + or - operator. It is a classic bit-manipulation puzzle: it forces you to rebuild addition from the gates a CPU actually uses — XOR and AND.

The slow way first

The tempting "cheat" is sum(range...) or repeatedly incrementing one number b times — but incrementing is just + 1 in disguise, and looping b times is O(b), which is hopeless for large or negative numbers. We need to add in one shot, the way hardware does.

The question to ask: how does a circuit add two bits without already knowing how to add? It splits the job into two pieces — the sum bit and the carry bit — each of which is a single logic gate.

The idea: XOR adds, AND carries

Look at adding two single bits:

• 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 10 (sum 0, carry 1).

That sum-without-carry column is exactly XOR (a ^ b). The carry happens only when both bits are 1, which is exactly AND (a & b), and a carry belongs in the next column to the left, so we shift it: (a & b) << 1.

So one pass gives us a partial sum (a ^ b) plus a set of carries ((a & b) << 1). We just repeat: add the carries in the same way, until there are no carries left.

The whole loop is: while b: carry = (a & b) << 1; a = a ^ b; b = carry. When b (the carry) finally becomes 0, a holds the answer.

Walk through it

Step through the animation with a = 2 (0010) and b = 3 (0011). Each loop highlights the columns where both bits are 1 (those generate a carry), XORs the rows into the new a, then feeds the shifted carry back into b. After two loops the carry drains to 0 and a reads 0101 = 5.

Pseudocode

while b is not zero:
    carry = (a AND b) shifted left by 1   # columns where both are 1 carry into the next
    a = a XOR b                           # add the bits, ignoring carry
    b = carry                             # the carries become the next thing to add
return a                                  # no carry left -> a is the sum

The Python solution

def get_sum(a, b):
    # a, b are 4-bit here for the picture
    while b:
        carry = (a & b) << 1
        a = a ^ b
        b = carry
    return a

• while b: keeps looping as long as there is still a carry to add.
• carry = (a & b) << 1 finds every column where both numbers have a 1 and moves that carry one place left.
• a = a ^ b adds the two numbers column-by-column without carrying.
• b = carry makes the leftover carries the new thing to add, then we go around again.
• When b reaches 0 there is nothing left to carry, so a is the final sum.

Complexity

For fixed-width integers the carry can ripple at most as many times as there are bits, so the loop runs a constant number of times — effectively O(1) with O(1) extra space.

When this pattern shows up

Practice