Sum of Two Integers: Adding Without the + Operator

LeetCode Sum of Two Integers (Problem 371) gives you two integers a and b and asks you to return their sum without using + or -. That sounds like a trick question, but it has a principled answer: simulate what a hardware adder does at the bit level.

Every CPU adds numbers the same way: XOR for the partial sums, AND-then-shift for the carries, repeated until there are no carries left. This problem is asking you to reproduce that process in software.

The key insight

Three observations drive the whole solution:

1. XOR gives sum bits without carry. When you XOR two bits, you get 1 only when they differ. That is exactly what happens in a single-bit adder when no carry is produced: 0 + 1 = 1, 1 + 0 = 1, 0 + 0 = 0, 1 + 1 = 0 (carry handled separately).

2. AND gives the carry bits. AND produces 1 only when both bits are 1, which is exactly the condition that generates a carry in binary addition. Shift the AND result left by one position to move each carry into the column where it belongs.

3. Repeat until carry is zero. After one round of XOR and AND-shift, you have a new pair of values: the partial sum and the carry. Feed them back into the same process. Eventually, no two bits in the same position are both 1 at the same time, so the AND result is zero and the loop stops.

The approach: loop

The algorithm is a while loop with two operations per iteration:

sum   = a ^ b          # sum bits without carry
carry = (a & b) << 1   # carry bits, shifted into position
a     = sum
b     = carry

Repeat while b != 0. When b reaches zero there are no pending carries, so a holds the final answer.

Note for Python: Python integers have arbitrary precision. They do not overflow or wrap around the way 32-bit integers do in C++ or Java. XOR-ing two large negative numbers in Python will never produce zero on its own, so the loop can run forever. You must mask intermediate values to 32 bits to simulate 32-bit integer arithmetic.

Use mask = 0xFFFFFFFF. Apply it to both the XOR result and the AND-shift result on every iteration. After the loop, if the result has bit 31 set (value greater than 0x7FFFFFFF), it represents a negative number in 32-bit two's complement. Convert it back with ~(a ^ mask).

Python solution

def getSum(a: int, b: int) -> int:
    mask = 0xFFFFFFFF
    while b & mask:
        carry = ((a & b) << 1) & mask
        a = (a ^ b) & mask
        b = carry
    if b == 0:
        return a if a <= 0x7FFFFFFF else ~(a ^ mask)
    return b

The Python masking explained

Without the mask, Python integers grow arbitrarily. Consider a = -1 and b = 1. In binary, -1 in two's complement is all 1-bits extending infinitely to the left. XOR-ing with 1 flips the last bit, giving all 1-bits still extending to the left, a different negative number and not zero. The carry is nonzero, so the loop continues forever.

Masking with 0xFFFFFFFF after each operation truncates values to 32 bits. Now the arithmetic stays in the range that 32-bit integers can represent, and the loop terminates within at most 32 iterations.

The sign extension step at the end handles the conversion back to Python's native signed integers. A 32-bit result with bit 31 set would be negative if this were actual 32-bit hardware. In Python, the masked value is positive (for example, 0xFFFFFFFF is 4294967295). The expression ~(a ^ mask) flips all bits after XOR-ing with the mask, which is equivalent to the two's complement negation. This gives you the correct negative Python integer.

Complexity

The loop runs at most 32 times because each iteration resolves at least one bit position. All operations (XOR, AND, shift) are O(1). No auxiliary data structures are needed.

Building blocks

XOR as sum without carry. This is the foundational primitive. When you apply XOR bit by bit, you get what addition looks like at each position before carries are considered. The XOR cancellation property you see in Single Number is the same primitive applied differently: there, pairs cancel to zero; here, differing bits add to one.

AND as carry detector. AND reveals only the positions where both operands had a 1, which is exactly where addition would overflow a single bit. Shifting that result left by one places each carry into the next column, ready to be added in the next iteration.

These two primitives together simulate a full adder. Once you see them as a pair, the loop structure follows naturally.

Edge cases

One or both inputs are zero. If b is zero on entry, the loop does not execute and a is returned immediately. If a is zero, the XOR result is b and the AND result is zero, so the loop runs once and returns b.

Negative numbers. Two's complement handles this transparently. XOR and AND operate on the bit patterns, and those bit patterns correctly encode negative numbers in two's complement. The Python mask and sign extension handle the precision mismatch.

a == -b. The sum should be zero. In this case, the XOR will eventually produce zero with zero carry, and the loop will exit returning zero.

From understanding to recall

The two primitives are the anchor: XOR gives the sum, AND-shift gives the carry. If you can recall that sentence, you can reconstruct the loop immediately. The Python-specific mask is a separate wrinkle that you layer on top once the base algorithm is solid.

Practice the base loop until it feels mechanical. Then add the mask and sign extension. After a few spaced repetitions, both the simple case and the Python case should flow without hesitation.

Related posts

• Single Number - XOR for cancellation, the same primitive used here for bit-level addition
• Counting Bits - bit manipulation DP, building results from smaller subproblems
• Number of 1 Bits - bit inspection patterns, including the AND trick to clear the lowest set bit