149.Sum of Two Integers

MediumBlind 75Bit Manipulation · 6/7

Problem

Given two integers a and b, return their sum without using the operators + and -.

This is really a question about how hardware adds numbers: you must build addition out of bitwise operations (^, &, <<), and it must work for negative numbers too.

Examples

Input:  a = 1, b = 2
Output: 3

Input:  a = 2, b = 3
Output: 5
Explanation: 010 + 011 = 101.

Input:  a = -1, b = 1
Output: 0
Explanation: In two's complement, ...1111 + ...0001 carries all the way out of the 32nd bit, leaving 0.

Constraints

-1000 <= a, b <= 1000

💡 Key Insight

Binary addition of two bits splits into two parts: the sum bit without carry is x ^ y, and the carry is x & y, which belongs one position to the left. So a + b == (a ^ b) + ((a & b) << 1). Repeat with the new pair until the carry is 0. Java ints are 32-bit two's complement, so negatives work automatically and any carry past bit 31 simply falls off.

Brute Force (Bit-by-Bit Full Adder)

TimeO(32) = O(1)SpaceO(1).

Intuition

Simulate a ripple-carry adder, one bit position at a time, exactly like a circuit. For bit i with input bits x, y and incoming carry c:

sum bit = x ^ y ^ c
carry out = (x & y) | (x & c) | (y & c) (at least two of the three are 1)

Do this for all 32 positions and assemble the result.

Algorithm

result = 0, carry = 0.
For i from 0 to 31:
- x = (a >> i) & 1, y = (b >> i) & 1.
- sum = x ^ y ^ carry; carry = (x & y) | (x & carry) | (y & carry).
- result |= sum << i.
Return result.

Visualization

a = 2 = 010, b = 3 = 011

bit 0: x=0 y=1 c=0 → sum 1, carry 0
bit 1: x=1 y=1 c=0 → sum 0, carry 1
bit 2: x=0 y=0 c=1 → sum 1, carry 0
result = 101 = 5

Code

java

class Solution {
    public int getSum(int a, int b) {
        int result = 0;
        int carry = 0;
        for (int i = 0; i < 32; i++) { // loop counter only; no + used on a or b
            int x = (a >> i) & 1;
            int y = (b >> i) & 1;
            int sum = x ^ y ^ carry;                          // sum bit of a full adder
            carry = (x & y) | (x & carry) | (y & carry);      // carry if at least two bits are 1
            result |= sum << i;
        }
        return result; // carry out of bit 31 is discarded (two's-complement wraparound)
    }
}

Complexity

Time: O(32) = O(1) — one step per bit.
Space: O(1).

Recursive XOR and Carry

TimeO(32) = O(1)SpaceO(32) = O(1)

Intuition

Process all bit positions at once: a ^ b adds every position ignoring carries, and (a & b) << 1 is every carry moved to where it must be added. Their sum equals a + b, so recursively add those two numbers. Each round pushes the lowest possible carry position at least one bit left, so after at most 32 rounds the carry is 0.

Algorithm

If b == 0, return a.
Otherwise return getSum(a ^ b, (a & b) << 1).

Dry Run

getSum(2, 3):  2^3 = 1, (2&3)<<1 = 4  → getSum(1, 4)
getSum(1, 4):  1^4 = 5, (1&4)<<1 = 0  → getSum(5, 0)
getSum(5, 0):  b == 0 → return 5

Code

java

class Solution {
    public int getSum(int a, int b) {
        if (b == 0) {
            return a; // no carry left: a holds the answer
        }
        // partial sum without carries, plus the carries shifted into place
        return getSum(a ^ b, (a & b) << 1);
    }
}

Complexity

Time: O(32) = O(1) — at most 32 rounds before the carry vanishes.
Space: O(32) = O(1) — recursion depth.

Iterative XOR and CarryOptimal

TimeO(32) = O(1)SpaceO(1).

Intuition

Same idea without recursion: keep replacing (a, b) with (a ^ b, (a & b) << 1) until there is no carry. This is how adders combine "half adders" in parallel.

For negatives, e.g. a = -1 (111...1) and b = 1: each round the carry moves one bit left and finally shifts out past bit 31, which Java discards, so the loop ends with a = 0.

Algorithm

While b != 0:
- carry = (a & b) << 1.
- a = a ^ b.
- b = carry.
Return a.

Dry Run

flowchart TD
    A["a = 010 (2), b = 011 (3)"] --> B["carry = (a AND b) shl 1 = 100<br/>a = a XOR b = 001"]
    B --> C["a = 001 (1), b = 100 (4)"]
    C --> D["carry = (001 AND 100) shl 1 = 000<br/>a = 001 XOR 100 = 101"]
    D --> E["a = 101 (5), b = 000"]
    E --> F{"b == 0?"}
    F -->|"yes"| G["return 5"]

Code

java

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1; // positions where both bits are 1 produce a carry
            a = a ^ b;                // add without carrying
            b = carry;                // now add the carries in the next round
        }
        return a;
    }
}

Complexity

Time: O(32) = O(1) — the carry chain is at most 32 bits long.
Space: O(1).

Complexity Comparison

Approach	Time	Space
Bit-by-Bit Full Adder	O(32)	O(1)
Recursive XOR and Carry	O(32)	O(32) stack
Iterative XOR and Carry	O(32)	O(1)

Common Pitfalls

Overwriting a before computing the carry — compute (a & b) << 1 from the old a, then update a.
Porting this to Python: integers are unbounded, so for negatives the carry never falls off and the loop runs forever. You must mask with 0xFFFFFFFF and convert back; Java's fixed 32-bit int does this for free.
Thinking negatives need special handling — two's complement makes subtraction the same circuit as addition.
Using >> versus << incorrectly: carries move left (towards higher bits), so it is always << 1.