Generated by Codex with GPT-5

Quick facts

Problem gist

The task is to return the sum of two signed integers without using the + or - operators. The important constraint is not about math knowledge; it is about understanding how binary addition works under the hood.

For each bit position, XOR gives the sum bit when carry is ignored. AND finds the positions where both numbers have a 1, which means those positions create a carry into the next higher bit. Shifting that carry left by one moves it where it needs to be added next.

So the whole problem becomes a loop:

  1. a ^ b is the partial sum without carries.
  2. (a & b) << 1 is the carry.
  3. Repeat with the partial sum and carry until there is no carry left.

That is exactly grade-school addition, but expressed with bit operations.

Key idea

In languages with fixed-width integers, the loop naturally stops because carries eventually fall out of the word. Python integers are different: they have unlimited precision, so negative numbers conceptually have infinitely many leading 1 bits. Without extra care, a case like adding -1 and 1 can keep carrying forever.

The practical fix is to simulate a 32-bit signed integer:

  • Keep every intermediate value inside 0xFFFFFFFF.
  • Treat values up to 0x7FFFFFFF as non-negative.
  • Convert anything with the sign bit set back into Python’s negative integer representation at the end.

This matches LeetCode’s expected signed 32-bit behavior and keeps the carry loop finite.

Python solution

class Solution:
    WORD_MASK = 0xFFFFFFFF
    MAX_SIGNED_INT = 0x7FFFFFFF

    def getSum(self, a: int, b: int) -> int:
        return self._add_as_signed_32_bit(a, b)

    def _add_as_signed_32_bit(self, left: int, right: int) -> int:
        left &= self.WORD_MASK
        right &= self.WORD_MASK

        while right:
            # XOR adds each bit position without carrying.
            partial_sum = (left ^ right) & self.WORD_MASK

            # AND finds carry positions; shifting moves carries left.
            carry = ((left & right) << 1) & self.WORD_MASK

            left, right = partial_sum, carry

        if left <= self.MAX_SIGNED_INT:
            return left

        # Convert from unsigned 32-bit two's complement to Python int.
        return ~(left ^ self.WORD_MASK)

The loop runs at most once per bit in the simulated word, so the time complexity is O(1) for fixed 32-bit integers. More generally, for a word size of w, it is O(w). The algorithm uses O(1) extra space.

How to derive it in an interview

Start from a one-bit addition table. If the two input bits differ, the result bit is 1; if they match, it is 0. That is XOR. A carry happens only when both input bits are 1. That is AND. Since a carry affects the next column, shift the AND result left.

Once that connection is clear, the iterative formula is natural: keep replacing the two numbers with “sum without carry” and “carry” until the carry becomes zero. At that point, the partial sum is the real sum.

The Python-specific part is worth mentioning without overcomplicating the answer. State that Python does not have fixed-width signed integers, so the implementation masks intermediate values to 32 bits and converts the final two’s-complement value back to a regular Python integer.

Interview follow-ups

How would this change for 64-bit signed integers?

The algorithm stays the same. Only the constants change: the word mask becomes 0xFFFFFFFFFFFFFFFF, and the largest positive signed value becomes 0x7FFFFFFFFFFFFFFF.

The reason this works is that two’s-complement addition is identical across word sizes; the word size only decides where overflow wraps. The complexity becomes O(64), which is still constant time in normal interview terms.

Can this method implement subtraction too?

Yes. In two’s complement, subtracting b is the same as adding the negation of b. The negation can be built as ~b plus one, using the same bitwise addition helper.

This works because two’s complement represents negative numbers by inverting the bits and adding one. The tradeoff is that the implementation needs the same fixed-width masking discipline; otherwise, Python’s unlimited sign extension can make negative values behave differently from a fixed-width machine integer.

Why does the loop eventually stop?

Each iteration moves unresolved carries one bit to the left. With a fixed word size, a carry can only move across a finite number of positions before it either settles into the sum or overflows out of the word.

Masking is what makes that guarantee true in Python. Without the mask, negative values have infinitely many leading sign bits, so there is no fixed edge where carries disappear.

What if the interviewer forbids helper methods or class constants?

The same logic can be written inline inside getSum. The helper method and constants mainly improve readability and make the signed-width assumptions explicit.

For a whiteboard answer, the core loop is what matters: compute XOR for the carry-free sum, compute shifted AND for the carry, mask both values when using Python, and convert the final unsigned result back to signed form.