371. Sum of Two Integers

Adding two numbers without + sounds like a riddle, but it’s really a question about how a CPU adds in the first place. The trick is to split addition into two pieces — a partial sum and a carry — and both fall straight out of bitwise ops. It’s a staple of the bit manipulation pattern, and once you see the XOR-plus-carry loop, the rest of that family reads the same way.

The problem

Given two signed integers a and b, return their sum — but you’re not allowed to use + or -. (Full statement on LeetCode.)

So getSum(2, 3) still has to return 5; you just have to reach it with bit operations instead of the arithmetic operators.

Intuition: XOR adds, AND carries

Think about adding two single bits the way grade-school addition works, column by column:

• 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 — and 1 + 1 = 10, a 0 with a carry into the next column.

Notice the bottom digit of each result — 0, 1, 1, 0 — is exactly a ^ b. XOR is addition when you ignore carries. The carry only fires in the 1 + 1 case, which is exactly a & b, and a carry moves one column to the left, so it becomes (a & b) << 1.

That gives the whole algorithm as a two-line identity:

$a + b = (a \oplus b) + \big((a \land b) \ll 1\big)$

The right side still has a +, but the carry term now has zeros wherever the sum term had the overlaps — so you keep folding the carry back in until there’s nothing left to carry:

$\text{sum} = a \oplus b, \qquad \text{carry} = (a \land b) \ll 1$

Repeat with those as the new a and b. Each round pushes the remaining carries further left, and since an int is only 32 bits wide, they run off the end after at most 32 passes. When the carry hits 0, the sum term holds the answer. Negatives need no special case: Java’s int is two’s complement and fixed-width, so the same XOR/AND/shift dance adds signed values correctly.

Solution

class Solution {
    public int getSum(int a, int b) {
        // Loop until nothing is left to carry.
        while (b != 0) {
            int carry = (a & b) << 1;  // where both bits are 1, carry moves left
            a = a ^ b;                 // add columns, ignoring carry
            b = carry;                 // fold the carry back in next round
        }
        return a;
    }
}

Here b holds “what still needs to be added” — first the real operand, then successive carries. The moment it reaches 0, a is the sum. Order matters inside the loop: compute carry from the old a and b before you overwrite a with the XOR.

Complexity

Time	Space
$O(1)$	$O(1)$

The loop runs at most once per bit, and an int has a fixed 32 bits — so $O(32)$, which is constant. No extra allocation.

In an interview

Say the mental model out loud before touching code: “XOR gives the sum without carries, AND-then-shift gives the carry, and I loop until the carry is gone.” That single sentence is what’s actually being tested — the loop is trivial once the identity is clear.

The trap people hit is assigning a = a ^ b first and then computing the carry from the already-mutated a — now the carry is wrong. Snapshot the carry first, or use a temp. If the interviewer pushes on negatives, note that two’s complement makes them free: subtraction is just adding a negated operand, and Java’s fixed-width int handles the sign bit without extra logic.

This is the cleanest doorway into the bit manipulation pattern. The same “look at one bit column at a time” habit is what Number of 1 Bits drills, and it carries straight into Counting Bits.

References

• LeetCode 371 — Sum of Two Integers