Sum of Two Integers — InterviewPrepKit

Solving tips

Rebuild addition from bits: a ^ b is the sum with no carry, (a & b) << 1 is the carry; feed these back as new a and b and loop until the carry is 0.
The XOR term alone is the answer once carry becomes 0; at most 32 iterations, so O(1) time and O(1) space.
Python wrinkle: ints don't wrap, so negatives have infinite leading 1s and the loop never ends, mask with & 0xFFFFFFFF every iteration.
At the end reinterpret the sign: if result >= 0x80000000 return result - 0x100000000; pitfall is shifting the XOR instead of the AND, or masking only once up front.

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.

The point is to rebuild addition itself out of 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

Hint 1

Recall how a schoolbook adds two binary numbers: add each column, and when a column overflows, carry a `1` into the next column. Which bitwise operator gives the column sum ignoring carries, and which one tells you where a carry is generated?

Hint 2

`a ^ b` is the sum of each bit position *without* carrying (`1 ^ 1 = 0`). `a & b` marks every position where both bits are `1` — exactly where a carry is born — and that carry lands one position to the left, so it is `(a & b) << 1`. Add those two together... but "add" is what you're building, so repeat.

Hint 3

Loop: `sum_no_carry = a ^ b`, `carry = (a & b) << 1`, then set `a = sum_no_carry`, `b = carry`, and repeat until `carry` is `0`. In Python, `&`-mask both to `0xFFFFFFFF` each iteration and, at the end, reinterpret a value `>= 2^31` as a negative number.

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:

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

There is no legitimate arithmetic fallback here — every counting or sum()-based trick ultimately performs + under the hood, which the constraints ban. So the ladder starts at the bit method, which is the actual intended solution.

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

The insight — take addition apart 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. Look at 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 — that is a ^ b (XOR).
The “carry-out” column is 1 exactly when both bits are 1 — that is a & b (AND), and since a carry belongs in the next column to the left, it is (a & b) << 1.

So a + b equals (a ^ b) + ((a & b) << 1) — but that still contains a +. The escape: the carry term has fewer set bits pushed leftward, so if we feed the two pieces back in as the new a and b and repeat, the carry shrinks toward zero. When the carry becomes 0, the XOR term alone is the full answer. 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 wrinkle: Python ints don’t wrap at 32 bits, so negative numbers have infinitely many leading 1s and the loop would never terminate. We 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 we map it back by subtracting 2^32.

class Solution:
    def getSum(self, 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):

-2 masked into 32 bits is 0xFFFFFFFE; 3 is 0x00000003.
- carry = (0xFFFFFFFE & 3) << 1 = (2) << 1 = 4.
- a = (0xFFFFFFFE ^ 3) & mask = 0xFFFFFFFD; b = 4.
carry = (0xFFFFFFFD & 4) << 1 = (4) << 1 = 8.
- a = (0xFFFFFFFD ^ 4) & mask = 0xFFFFFFF9; b = 8.
The carry keeps marching left through the run of 1s; after the carry finally reaches bit 32 it is masked away to 0, leaving a = 0x00000001, b = 0.
b == 0; 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 insight: the loop is plain tail recursion — “the answer of a + b is the answer of (a ^ b) + carry,” bottoming out when the carry is 0. Some interviewers like to see it stated this way; it is the identical algorithm with the loop replaced by a call.

class Solution:
    def getSum(self, 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 worries about stack frames; they compute the same thing.

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 vanishes. Carry the meta-lesson too — 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.