4.30.6 — Sum of Two Integers

LeetCode 371 · Medium · ★ Blind 75

The problem

Return a + b without using + or −. Both may be negative.

a = 1, b = 2     →  3
a = 2, b = 3     →  5
a = -1, b = 1    →  0

The pattern

Addition is two separate operations that a CPU does in parallel, and separating them is the whole solution.

Add each column, ignoring carries. That is exactly XOR: 0+0=0, 0+1=1, 1+0=1, and 1+1=0 with the 1 carried out.

Work out the carries. A carry is generated wherever both bits are 1, which is a & b, and it belongs one column to the left, so shift it: (a & b) << 1.

Now add the sum-without-carry to the carry — which is the same problem again, so repeat until there is nothing left to carry.

while b:
    carry = (a & b) << 1
    a = a ^ b            # sum without carries
    b = carry            # what still needs adding
return a

This is a ripple-carry adder, and it is literally how the circuit in Chapter 1.2 works. Each iteration is one propagation step through the hardware.

Why it terminates

Each iteration shifts the carry one place left, so after at most 32 iterations the carry has fallen off the end and b is 0.

The Python problem

In most languages the loop above is the whole answer. In Python it does not terminate for negative inputs, and understanding why is the real content of this problem.

Python integers are unbounded, and a negative number behaves as though it has infinitely many leading 1s. So (a & b) << 1 keeps producing a non-zero carry forever — the 1s never run out.

The fix is to simulate 32-bit arithmetic by hand:

1. Mask after every step with 0xFFFFFFFF, which keeps only the low 32 bits.
2. At the end, convert back to a signed value. If the result's top bit is set, it represents a negative number in two's complement, and Python must be told: ~(result ^ 0xFFFFFFFF).

That conversion line deserves unpacking. result ^ 0xFFFFFFFF flips all 32 bits, and ~ of that gives Python's own negative representation of the same value. It is the standard idiom for "reinterpret these 32 bits as signed".

The solution

Python

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF
        MAX_INT = 0x7FFFFFFF

        while b:
            carry = ((a & b) << 1) & MASK      # mask to stay in 32 bits
            a = (a ^ b) & MASK
            b = carry

        # reinterpret the 32 bits as a signed integer
        return a if a <= MAX_INT else ~(a ^ MASK)

TypeScript

function getSum(a: number, b: number): number {
  while (b !== 0) {
    const carry = (a & b) << 1;
    a = a ^ b;
    b = carry;
  }
  return a;
}

TypeScript needs no masking, because its bitwise operators already coerce to 32-bit signed integers — the overflow behaviour you want happens for free. Java, C and C++ are the same.

Python is the awkward one precisely because its integers are better. Unbounded arithmetic is normally a gift; here it is the obstacle.

Trace

a = 3 (011), b = 5 (101).

iteration	a ^ b	(a & b) << 1	new a	new b
1	110 (6)	001 << 1 = 010 (2)	6	2
2	100 (4)	010 << 1 = 100 (4)	4	4
3	000 (0)	100 << 1 = 1000 (8)	0	8
4	1000 (8)	0	8	0

3 + 5 = 8 ✓. Four iterations, because the carry rippled through three positions.

Subtraction

a − b is a + (−b), and negation in two's complement is ~b + 1 — which itself needs the adder. So subtraction is one extra call:

def subtract(a, b):
    return getSum(a, getSum(~b, 1))

That is exactly how a CPU's ALU implements subtraction: negate and add, reusing the same adder circuit rather than building a second one.

Complexity

O(1) — at most 32 iterations. O(1) space.

Where this goes next

• Add Binary, Add Two Numbers — the same carry logic, digit by digit rather than bit by bit. 4.9.6.
• Multiply without * — repeated shift-and-add, which is 4.28.6 Pow's structure applied to multiplication.
• Divide Two Integers (LeetCode 29) — repeated shift-and-subtract, with a famous overflow case at INT_MIN / −1.
• Chapter 1.2 builds the half adder and full adder as circuits, and this problem is that circuit written as software. Mentioning that connection is the strongest finish available here.

What the interviewer will push on

"Why is XOR the sum?" It is addition per column with the carry discarded.

"Why (a & b) << 1?" A carry is generated where both bits are 1, and it applies to the next column left.

"Why does the loop terminate?" The carry shifts left each time and falls off after 32 steps.

"Why does this break in Python?" Unbounded integers mean a negative value has infinitely many leading 1s, so the carry never dies. Mask to 32 bits and convert back to signed.

"How would you subtract?" Negate with ~b + 1 and add — which is what an ALU does.

One thing to volunteer: name it as a ripple-carry adder and say it is the circuit from Chapter 1.2. It reframes the problem from a puzzle about forbidden operators into an explanation of how the hardware actually adds.

Next: 4.30.7 Reverse Integer — the last problem in Part 4, and it is entirely about checking for overflow before it happens.