229. Sum of Two Integers

Binary addition splits into two parts: the sum of bits ignoring carries (XOR) and the carries themselves (AND shifted left). Repeat until there is no carry left.

Two pieces of addition

For each bit position, adding two bits gives a sum bit and a carry bit:

• a ^ b produces the sum of every bit position ignoring carries.
• (a & b) << 1 produces the carries, shifted into the next position.

Add them again (repeat) until the carry becomes 0.

while b != 0:
    carry = (a & b) << 1
    a = a ^ b
    b = carry
return a

In Python we mask to 32 bits and reinterpret negatives; in Java/C++ the int overflow wraps automatically.

Worked example

a = 11 (1011), b = 6 (0110):

• sum = 1011 ^ 0110 = 1101 (13); carry = (1011 & 0110)<<1 = 0010<<1 = 0100 (4).
• sum = 1101 ^ 0100 = 1001 (9); carry = (1101 & 0100)<<1 = 0100<<1 = 1000 (8).
• sum = 1001 ^ 1000 = 0001 (1); carry = (1001 & 1000)<<1 = 1000<<1 = 10000 (16).
• continue until carry 0 → 17.

Complexity

• Time: O(1) (at most 32 iterations).
• Space: O(1).

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;  // 32-bit overflow wraps automatically in Java
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}