Sum of Two Integers (LeetCode 371)

The problem

Return a + b for two integers without using the + or - operators. On LeetCode, both values lie between −1000 and 1000, and the answer must behave like 32-bit integer addition.

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

The usual sum, built only from bit operations.

How to think about it

Start with brute force. You could increment a one at a time, b times, but incrementing needs + too, and it is O(|b|) anyway. You need to build addition itself out of bit operations.

The key insight: split addition into “sum without carry” and “carry”. Add two bits by hand: 0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 10. The digit you write down is a ^ b (XOR). A carry appears only where both bits are 1, which is a & b, and it belongs one place to the left: (a & b) << 1. So a + b == (a ^ b) + ((a & b) << 1). That is still an addition, but repeat the step and the carry moves left each time, so it eventually dies out.

The Python catch: unbounded integers. In C or Java the carry falls off bit 31 and disappears. Python ints have no fixed width, and a negative number has infinitely many leading 1s, so for something like -1 + 1 the carry would walk left forever. The fix is to only look at the low 32 bits of the carry (b & mask). When the carry has escaped past bit 31, the low 32 bits of a are the right answer, so the code masks a back into range.

Which pattern is this? Bit manipulation, building arithmetic from XOR and AND. The tell is “without using + or -“. The same half-adder idea underlies Add Two Numbers, with digits instead of bits.

Approach

1. Let mask = 0xFFFFFFFF (32 ones).
2. While the low 32 bits of b are not all zero, replace (a, b) with (a ^ b, (a & b) << 1).
3. If the loop ended because b is exactly zero, a is the answer.
4. If it ended because the carry moved past bit 31 (b > mask), return a & mask to drop the stray high bits.

Solution

def get_sum(a, b):
    mask = 0xFFFFFFFF
    while b & mask:                          # carry still inside 32 bits
        a, b = a ^ b, (a & b) << 1           # sum without carry, carry
    return a & mask if b > mask else a       # carry escaped: keep low 32 bits
# get_sum(2, 3) -> 5

Dry run

On a = 2, b = 3:

b is 0, so the function returns 5. For get_sum(-1, 1), the carry moves left once per step; after 32 steps a = -4294967296 and b = 4294967296 > mask, so the function returns a & mask = 0.

Complexity

• Time: O(1). At most about 32 iterations, because the carry moves at least one bit left each time.
• Space: O(1).

Edge cases and pitfalls

• Opposite signs (-1 + 1, 5 + -3) are where Python’s infinite sign bits bite. Without the mask the loop never ends.
• Both negative (-2 + -3) ends with b = 0 quickly and returns -5 directly.
• Verified range. This function was checked against a + b for every pair in −1000 to 1000, plus random values up to ±2³⁰. Outside 32-bit range it is not meant to work.
• In Java or C++ the loop is just while (b != 0); the fixed width does the masking for you.

Related problems

• Add Two Numbers (LeetCode 2): addition with a carry, digit by digit on linked lists.
• Reverse Bits (LeetCode 190): another problem that depends on a fixed 32-bit width.
• Single Number (LeetCode 136): XOR as addition mod 2 in its simplest form.