4.30.6 — Sum of Two Integers

LeetCode 371 · Medium · ★ Blind 75

The problem

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

Restating the Problem: You need to add two integers together, but you are forbidden from using the built-in addition or subtraction operators. This forces you to simulate how a computer's CPU Arithmetic Logic Unit (ALU) performs addition at the bit level.

• Constraints to note: The inputs are 32-bit integers, which can be negative.
• Edge cases: Adding a positive and a negative number, or two negatives. Handling overflow correctly in languages without bounded integers (like Python).

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

Brute Force Approach

The brute force here isn't about time complexity, it's about cheating the rules. One naive cheat is sum([a, b]) or utilizing built-in increment functions in a loop. The intended "brute force" bitwise simulation without handling negative numbers properly in Python will result in an infinite loop (Time Limit Exceeded). The core algorithm must precisely handle carries bit by bit.

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;
}

Code Walkthrough (Python):

• Constants: We define a 32-bit MASK (0xFFFFFFFF) to enforce 32-bit bounds, and MAX_INT (0x7FFFFFFF) to distinguish positive from negative numbers.
• Loop (while b): We loop as long as there is a carry (stored in b).
• Carry Calculation: We find the bits where both a and b have a 1 using a & b, shift them left by 1 (because a carry goes to the next higher bit), and apply the 32-bit MASK.
• Addition without Carry: We use XOR (a ^ b) to add the bits that don't generate a carry, applying the MASK.
• Update: We assign the new sum to a and the carry to b.
• Return: If a is less than or equal to MAX_INT, it's positive, so we return it. If it's larger, it represents a negative 32-bit two's complement integer, so we reinterpret it using ~(a ^ MASK).

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.

• Time Complexity: O(1). The while loop executes at most 32 times because we are working within a 32-bit constraint. Each shift moves the carry left until it eventually falls off.
• Space Complexity: O(1). We only use a few integer variables (carry, a, b).

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.