Sum of Two Integers

Problem

Given two integers a and b, return their sum a + b — without using the + or - operators (and without any helper that hides them, such as sum() or operator.add). Inputs and the result are signed 32-bit integers, and negative values are allowed.

You must rebuild addition from bitwise operations.

Examples

• a = 1, b = 2 → 3 01 + 10 = 11.
• a = 2, b = 3 → 5 010 + 011 = 101.
• a = -2, b = 3 → 1 Works across signs using 32-bit two’s-complement arithmetic.
• a = -1, b = 1 → 0 The carries propagate all the way out and cancel.

Constraints

• -1000 <= a, b <= 1000 on LeetCode, but the method must be correct for any signed 32-bit inputs [-2^31, 2^31 - 1].
• You may not use + or -.
• In Python, integers are arbitrary precision, so you must mask to 32 bits yourself and convert the result back to a signed value — the language will not overflow-wrap for you.

Think about it first

TL;DR

XOR gives the carry-less sum, AND << 1 gives the carry; loop until the carry is gone — O(1) time (≤32 iterations), O(1) space.

Approach 1 — Just add (the disallowed brute force)

The arithmetic brute force is the one line the problem forbids:

def getSum(a: int, b: int) -> int:
    return a + b        # not allowed: uses '+'

There is no legitimate arithmetic fallback: every counting or sum()-based trick performs + under the hood, which the constraints ban. The real solution is the bit method below.

Approach 2 — Add with XOR and carry (the bit-level insight)

Split addition into two independent bitwise pieces. When you add two bits in one column, two things can happen: a partial sum stays in this column, and a carry may spill into the next column. The four cases:

 a  b | sum-here  carry-out
 0  0 |    0         0
 0  1 |    1         0
 1  0 |    1         0
 1  1 |    0         1

• The “sum-here” column is 1 exactly when the two bits differ, which is a ^ b (XOR).
• The “carry-out” column is 1 exactly when both bits are 1, which is a & b (AND). A carry belongs in the next column to the left, so it is (a & b) << 1.

So a + b equals (a ^ b) + ((a & b) << 1), but that still contains a +. Feed the two pieces back in as the new a and b and repeat: each pass pushes the carry farther left, so it shrinks toward zero. When the carry becomes 0, the XOR term alone is the full answer.

flowchart TD
    A[Start with a and b] --> B{b == 0?}
    B -- yes --> C[Return a as signed 32-bit]
    B -- no --> D[carry = a AND b, shifted left 1]
    D --> E[a = a XOR b, masked to 32 bits]
    E --> F[b = carry, masked to 32 bits]
    F --> B

Trace 1 + 2:

a = 01, b = 10
  a ^ b = 11   (sum with no carry)
  a & b = 00 -> carry (<<1) = 000
carry is 0  ->  answer = 11 = 3

and 2 + 3, where a carry actually appears:

a = 010, b = 011
  a ^ b = 001,  (a & b) << 1 = (010) << 1 = 100
a = 001, b = 100
  a ^ b = 101,  (a & b) << 1 = 000
carry is 0  ->  answer = 101 = 5

The Python detail: Python ints don’t wrap at 32 bits, so negative numbers have infinitely many leading 1s and the loop would never terminate. Pin everything to 32 bits with mask = 0xFFFFFFFF each iteration. At the end, a value >= 0x80000000 has its sign bit set, meaning it represents a negative 32-bit number, so map it back by subtracting 2^32.

def getSum(a: int, b: int) -> int:
    mask = 0xFFFFFFFF          # keep only the low 32 bits
    while b != 0:
        carry = (a & b) << 1
        a = (a ^ b) & mask     # sum without carry, clipped to 32 bits
        b = carry & mask       # carry to fold in next, clipped to 32 bits
    # a now holds the 32-bit result; reinterpret as signed
    return a if a < 0x80000000 else a - 0x100000000

Walkthrough on a = -2, b = 3 (expect 1):

1. -2 masked into 32 bits is 0xFFFFFFFE; 3 is 0x00000003.
   • carry = (0xFFFFFFFE & 3) << 1 = (2) << 1 = 4.
   • a = (0xFFFFFFFE ^ 3) & mask = 0xFFFFFFFD; b = 4.
2. carry = (0xFFFFFFFD & 4) << 1 = (4) << 1 = 8.
   • a = (0xFFFFFFFD ^ 4) & mask = 0xFFFFFFF9; b = 8.
3. The carry keeps moving left through the run of 1s; once it reaches bit 32 it is masked away to 0, leaving a = 0x00000001, b = 0.
4. b == 0, and a = 1 < 0x80000000, so return 1.

Complexity: O(1) time — at most 32 iterations, one per bit position the carry can travel — and O(1) space.

Approach 3 — Same idea, recursive

The loop is plain tail recursion: the sum of a + b equals the sum of (a ^ b) and the carry, bottoming out when the carry is 0. It is the identical algorithm with the loop replaced by a call.

def getSum(a: int, b: int) -> int:
    mask = 0xFFFFFFFF

    def add(a: int, b: int) -> int:
        if b == 0:
            return a if a < 0x80000000 else a - 0x100000000
        return add((a ^ b) & mask, ((a & b) << 1) & mask)

    return add(a & mask, b & mask)

Complexity: O(1) time (≤32 frames), O(1) space aside from the bounded recursion stack. Prefer the iterative version if the interviewer is concerned about stack frames; the two compute the same result.

Common pitfalls

• No masking in Python → infinite loop. Negative operands carry endless leading 1s; without & 0xFFFFFFFF on the carry, b never reaches 0. Always clip to 32 bits.
• Forgetting to reinterpret the sign at the end. A result >= 0x80000000 is a negative 32-bit number; return a - 0x100000000, not the raw masked value.
• Shifting the wrong term. The carry (a & b) is what shifts left by 1; the XOR sum stays put. Swapping them computes nonsense.
• Looping on b before masking it. Mask b (the carry) inside the loop each pass — masking only once up front lets a fresh carry escape the 32-bit window.

Pattern takeaway

Any arithmetic operator can be rebuilt from bit primitives by separating the part that stays from the part that carries: XOR is addition without carry, AND << 1 is the carry, and iterating folds the carry back in until it reaches zero. In a language with arbitrary-precision ints, you are responsible for the fixed width: mask to the intended bit count every step and translate the sign bit back by hand.