Sum of Two Integers (LC 371)

Pattern: Bit Manipulation (full adder / XOR–carry)
Difficulty: Medium
Key Concept: XOR gives sum without carry; AND (shifted) isolates carry—repeat until carry disappears.

Problem Statement

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

Input

• a, b: int (32-bit signed; on LeetCode the result fits in 32-bit two’s complement)

Output

• int — a + b as if computed with normal addition

Example

• a = 1, b = 2 → 3
• a = 2, b = 3 → 5

Constraints (typical)

• -1000 <= a, b <= 1000 (LeetCode); conceptually works for full 32-bit range with masking where needed

---

1. Algorithm & Pseudocode

Brute force

Build the answer bit by bit from least significant to most significant, like pen-and-paper binary addition with a running carry.

result = 0
carry = 0
for bit position i from 0 to 31:
    abit = (a >> i) & 1
    bbit = (b >> i) & 1
    sumbit = abit XOR bbit XOR carry
    carry = majority(abit, bbit, carry)  // 1 if at least two 1s
    if sumbit == 1:
        result |= (1 << i)
return result as signed int

This always does a fixed 32 steps—easy to reason about, no “magic” XOR formula.

Optimal

Use the ripple-carry identity in bulk: a ^ b is sum bits ignoring carry; (a & b) << 1 is the carry to add next. Repeat until carry is 0.

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

Same math as the brute approach, but updates all bits at once each iteration (typically very few iterations in practice).

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why XOR? For a single bit, 0^0=0, 0^1=1, 1^0=1, 1^1=0 — that is exactly the sum bit when there is no incoming carry.

2. Where does carry come from? A carry appears when both bits are 1. The expression a & b has a 1 exactly in those positions. Shifting left by one (<< 1) moves that carry to the next higher bit—same as school addition.

3. Why a loop? After you fold in one layer of carry, new carries can appear (e.g. three 1s in a column). You keep combining until no carry remains.

4. Why not use +? The problem forbids it; the loop is how hardware adds—so you are reimplementing a tiny adder.

5. Java and negatives Two’s complement means the same XOR/AND rules work for negative numbers; you do not treat the sign separately.

---

3. The Dry Run

Sample: a = 5 (0101), b = 3 (0011) — optimal XOR–carry loop.

Iteration	a (binary)	b (binary)	carry = (a&b)<<1	a ^ b (new a)	b becomes
start	0101 (5)	0011 (3)	—	—	—
1	0101	0011	0100	0110 (6)	0100 (4)
2	0110	0100	0100	0010 (2)	0100 (4)
3	0010	0100	0000	0110 (6)	0000 (0)

Stop: b == 0 → return a = 8 (1000).
(Check: 5 + 3 = 8.)

ASCII (one iteration idea)

     a: 0 1 0 1   (5)
     b: 0 0 1 1   (3)
    ------------
 a^b: 0 1 1 0   sum w/o carry
a&b:  0 0 0 1 -> <<1 -> 0 1 0 0   carry to add next

---

4. Java Solution

Brute Force

class Solution {
    public int getSum(int a, int b) {
        int result = 0;
        int carry = 0;
        for (int i = 0; i < 32; i++) {
            int abit = (a >> i) & 1;
            int bbit = (b >> i) & 1;
            int sumBit = abit ^ bbit ^ carry;
            carry = (abit & bbit) | (abit & carry) | (bbit & carry);
            if (sumBit == 1) {
                result |= (1 << i);
            }
        }
        return result;
    }
}

Time: O(1) — fixed 32 iterations.
Space: O(1).

Optimal

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}

Time: O(1) — at most a small constant number of passes for 32-bit (worst-case ~32).
Space: O(1).

---

5. The “Java vs. Others” Edge

• int is always 32-bit signed on the JVM; there is no separate “unsigned int” type. Bit hacks still match two’s complement addition.
• Right shift >> is arithmetic (sign-extends). Here we mostly use & 1 on shifted values, which is safe. If you ever need logical right shift for unsigned-style parsing, use >>>.
• Overflow of carry: (a & b) << 1 can overflow the conceptual “33rd” bit; in Java the bits simply wrap, which is exactly what two’s-complement addition expects for int.
• Versus Python: Python integers are arbitrary precision, so the same loop without masking can behave differently on huge values; Java stays in fixed-width int.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute (bit-by-bit)	O(1)	O(1)	32 iterations; very explicit carry bookkeeping.
Optimal (XOR–carry)	O(1)	O(1)	Few iterations typical; worst ~32 for full ripple.