medium Sum of Two Integers

Sum of Two Integers

Problem. Return a + b without using the operators + or -. The only tools allowed are bitwise operations. This is really a question about one thing: do you know how a hardware adder works? Because that is exactly what you are going to rebuild.

From nothing — how addition decomposes into XOR and carry

Add two bits at a time, the way you add two decimal digits: you produce a digit for this column and possibly a carry into the next. In binary the single-bit addition table is:

Read the two output columns as functions of the inputs:

• The sum bit column is 0,1,1,0 — that is exactly XOR. So a ^ b is the sum of every column ignoring all carries ("sum without carry").
• The carry column is 0,0,0,1 — that is exactly AND. A carry is generated only where both bits are 1. And a carry belongs to the next higher column, so it is (a & b) << 1.

So a + b equals "sum without carry" plus "the shifted carries" — but that inner "plus" is itself an addition, which we again split the same way. Each round the carry pattern moves left and thins out; because a 32-bit carry can only travel left 32 times before falling off the top, the carry eventually becomes 0 and we are done. That gives the loop:

while (b != 0) {          // b holds the carry still to be folded in
    carry = (a & b) << 1;  // where both are 1, carry the next column
    a     = a ^ b;         // add the columns, ignoring carry
    b     = carry;         // now add that carry the same way
}
return a;                  // no carry left → a is the total

Traced example — 2 + 3 = 5

a = 2 = 010, b = 3 = 011. Watch the carry (in b) shrink to 0:

Iteration 1 says "2 and 3 share the 2's-place bit, so column-sum is 001 and we owe a carry of 100." Iteration 2 folds that carry in: no more overlap, so the columns settle to 101 = 5 and the carry dies. Two rounds, exactly matching how you would add 10 + 11 on paper.

Why it still works for negatives — two's complement is free

Nothing above assumed the numbers were positive. Two's complement is precisely the representation that makes the same add/carry circuit compute signed sums correctly — a negative number is stored as its bit pattern and the identical XOR/AND/shift loop applies. We verified getSum(-2, 3) = 1, getSum(-1, 1) = 0, and getSum(-3, -5) = -8 by execution. Trace of -2 + 3: the carry starts at 4, then climbs 8, 16, 32, … as the lone carry bit marches toward bit 31; on the step where it would shift past bit 31 it falls out of the 32-bit word, b becomes 0, and a is left holding 1. The climb is guaranteed finite because the carry can only move left, and there are only 32 positions.

Java: add via XOR + carry

public class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1; // carries, moved to the next column
            a = a ^ b;                // columns summed, carry ignored
            b = carry;                // fold the carry in next round
        }
        return a;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.getSum(2, 3));   // 5
        System.out.println(s.getSum(-2, 3));  // 1
        System.out.println(s.getSum(-3, -5)); // -8
    }
}

Go: add via XOR + carry

package main

import "fmt"

func getSum(a, b int) int {
    for b != 0 {
        carry := (a & b) << 1
        a = a ^ b
        b = carry
    }
    return a
}

func main() {
    fmt.Println(getSum(2, 3))   // 5
    fmt.Println(getSum(-2, 3))  // 1
    fmt.Println(getSum(-3, -5)) // -8
}

Complexity

Each iteration moves the lowest carry at least one position higher, and a carry cannot exceed the word width, so the loop runs at most w = 32 times → O(w) = O(1) for fixed-width integers. Space is O(1) (two scalars). This is not faster than + — the CPU does the same work in one instruction — it is a reconstruction of that instruction.

Judgment layer — when this trick is right, and when it is a red flag

• When to use it: essentially never in production — write a + b. This solution exists for two legitimate reasons: (1) the interview explicitly bans +/- and is probing whether you understand carry propagation and two's complement; (2) you are implementing an ALU, a hardware model, or a language/VM where + genuinely is not available at that layer.
• The named alternative is just +. It is O(1), one instruction, and impossible to get wrong. The entire value of the bit version is explaining why + works. If you reach for XOR-carry when + is allowed, that is over-cleverness — a maintainability cost with zero benefit. Say this out loud in the interview; it shows engineering judgment, not just trick knowledge.
• Multiplication analogue: the same decomposition (shift-and-add) underlies "multiply without *", so understanding this generalizes.

Traps & edge cases

• Language width matters. Java int (32-bit) and Go int both wrap in two's complement, so the loop terminates naturally. In Python the same code loops forever, because ints are arbitrary-precision — a negative "carry" never shifts off a top bit. There you must mask each step to 32 bits (a & 0xffffffff) and re-interpret the sign at the end. This is the single most common bug on this problem.
• Overflow of the true sum (e.g. Integer.MAX_VALUE + 1) wraps exactly as ordinary + would in Java/Go — the bit method matches the language's defined overflow behavior, it does not add protection.
• Left-shifting a negative (a & b) is well-defined on Java int and Go int (it operates on the bit pattern); do not "fix" it.
• Do not use b > 0 as the loop guard — the carry can be negative mid-loop for negative inputs. The guard must be b != 0.

Authored for this guide from first principles (LeetCode 371). The half-adder identities (sum = a^b, carry = (a&b)<<1) are derived from the truth table above; 2+3=5, -2+3=1, -1+1=0, 7+8=15, and -3+-5=-8 were all confirmed by running the Java and Go code in Java 8 and Go 1.25.