Sum of Two Integers

MediumBit Manipulation · Binary Addition🧩 Bit Manipulation LeetCode #371 ↗Updated Oct 30, 2026

Problem

Return a + b for two integers a and b without using the + or - operators on them. You have to build the addition out of bitwise operations, and it must work for negative numbers too.

Inputa = 1, b = 2Output3

Inputa = 2, b = 3Output5

Inputa = -7, b = 4Output-3

-1000 ≤ a, b ≤ 1000

Try it yourself

Java

class Solution {
    public int getSum(int a, int b) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Binary addition splits into two parts: a ^ b is the sum ignoring carries, and (a & b) << 1 is exactly the carries. Add those two the same way until no carry is left. Two's complement makes negatives work automatically.

PatternBit Manipulation

Instinct Pairs that cancel, counting 1s, powers of two, subsets as numbers, or 'no + or - allowed' - drop to binary and use XOR, AND, OR and shifts.

Memory hack XOR is a forgetful twin detector - see something twice and it vanishes; n & (n-1) snips off the last lit bulb.

Open the Bit Manipulation guide →

Approaches

Brute ForceRipple-Carry Adder, Bit by Bit

Time O(32)Space O(1)

Simulate a hardware full adder for each of the 32 bit positions: the sum bit is x ^ y ^ carry, and the new carry is 1 when at least two of the three inputs are 1. Since Java ints are two's complement, the final carry out of bit 31 is simply dropped, giving the right result for negatives.

Java

public int getSum(int a, int b) {
    int result = 0, carry = 0;
    for (int i = 0; i < 32; i++) {
        int x = (a >>> i) & 1, y = (b >>> i) & 1;
        int sum = x ^ y ^ carry;                     // full-adder sum bit
        carry = (x & y) | (x & carry) | (y & carry); // majority of three = carry out
        result |= sum << i;
    }
    return result;
}

Easy to justify from first principles, but always walks all 32 bits.

OptimalXOR + Shifted AND Until No Carry

Time O(32) worst, usually far fewerSpace O(1)

Handle all bit positions in parallel: a ^ b adds without carrying, (a & b) << 1 moves every carry one column left. Repeat with these two numbers as the new a and b. Each round the carry chain gets one bit shorter, so it finishes in at most 32 rounds.

Java

public int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1; // columns that produce a carry
        a = a ^ b;                // sum without carries
        b = carry;                // carries still to be added
    }
    return a;
}

Short, works for negatives, and only loops as long as the longest carry chain.

Pro tip

In Python the loop never ends for negatives (unbounded ints) — you must mask to 32 bits there. In Java, overflow wraps for free.

At a glance

Level	Approach	Time	Space
Brute Force	Ripple-Carry Adder, Bit by Bit	`O(32)`	`O(1)`
Optimal	XOR + Shifted AND Until No Carry	`O(32) worst, usually far fewer`	`O(1)`

Common pitfalls

Forgetting the << 1 on the carry — a carry belongs in the next column.
Overwriting a before computing the carry from the old a.
Thinking negatives need special handling — two's complement already makes the same loop correct.

Interview tips

Explain with a decimal analogy: add digits without carrying, then add the carries.
Mention the bit-by-bit adder as the conceptual baseline, then compress it to the XOR/AND loop.
Walk through -1 + 1 to show the carry running off the top of 32 bits.

Pattern

XOR = add without carry, AND<<1 = carry → arithmetic using only bit operations.

My notes saved in this browser