Sum of Two Integers

Difficulty: Medium Source: NeetCode

Problem

Given two integers a and b, return the sum of the two integers without using the operators + or -.

Example 1: Input: a = 1, b = 2 Output: 3

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

Constraints:

• -1000 <= a, b <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

• XOR (^) — adds bits without carrying
• AND (&) — finds bits where both inputs are 1 (i.e., where a carry will occur)
• Left shift (<<) — shifts carry bits one position left (to the correct position)
• Two’s complement — how negative numbers are represented in binary (important for Python’s unbounded integers)

1. Brute Force

Intuition

In Python, you can get around the restriction trivially using subtraction-based counting or sum(). But that’s clearly cheating the spirit of the problem. The intended approach is pure bit manipulation, so let’s focus there.

For completeness, here’s the iterative increment approach that technically avoids + and - — but don’t actually use this in an interview!

Algorithm

1. Use operator.add or functools.reduce — these call __add__ under the hood.
2. Or just admit the brute force is meaningless here and skip to the real solution.

Solution

import operator

def getSum_trivial(a, b):
    # This "avoids" + and - syntactically but uses the same operation internally.
    # Don't use in an interview — show the bit manipulation approach instead.
    return operator.add(a, b)


print(getSum_trivial(1, 2))  # 3
print(getSum_trivial(2, 3))  # 5

Complexity

• Time: O(1)
• Space: O(1)

2. Bit Manipulation (XOR + Carry)

Intuition

Think about how addition works at the bit level. When you add two bits:

0 + 0 = 0   (no carry)
0 + 1 = 1   (no carry)
1 + 0 = 1   (no carry)
1 + 1 = 0   (carry 1 to the next position)

This is exactly what XOR computes for the sum bits (ignoring carry) and what AND computes for the carry bits:

• a ^ b — sum without carry
• (a & b) << 1 — carry bits shifted into the correct position

Now, add the partial sum and the carry the same way. Repeat until there’s no more carry.

For a = 3 (011), b = 5 (101):

iteration 1:
  sum  = 011 ^ 101 = 110  (6)
  carry = (011 & 101) << 1 = 001 << 1 = 010  (2)

iteration 2:
  sum  = 110 ^ 010 = 100  (4)
  carry = (110 & 010) << 1 = 010 << 1 = 100  (4)

iteration 3:
  sum  = 100 ^ 100 = 000  (0)... wait that's wrong

Hmm, let me redo: 3 + 5 = 8. Let me retrace:

a=3=011, b=5=101
iter 1: sum=110(6), carry=001<<1=010(2)
iter 2: a=6=110, b=2=010 → sum=100(4), carry=010<<1=100(4)
iter 3: a=4=100, b=4=100 → sum=000(0), carry=100<<1=1000(8)
iter 4: a=0, b=8 → sum=1000(8), carry=0
done: 8 ✓

Python-specific issue: Python integers are unbounded — they never overflow. But (a & b) << 1 can grow infinitely for negative numbers, creating an infinite loop. The fix is to mask to 32 bits with & 0xFFFFFFFF at each step and convert back to a signed integer at the end.

Algorithm

1. Use a 32-bit mask MASK = 0xFFFFFFFF.
2. While b != 0:
   • Compute carry = (a & b) << 1 masked to 32 bits.
   • Compute a = (a ^ b) masked to 32 bits.
   • Set b = carry.
3. If the result fits in a 31-bit positive integer (a <= 0x7FFFFFFF), return a.
4. Otherwise, convert from unsigned 32-bit to Python signed integer: return ~(a ^ MASK).

Solution

def getSum(a, b):
    MASK = 0xFFFFFFFF
    MAX = 0x7FFFFFFF

    while b != 0:
        carry = (a & b) << 1
        a = (a ^ b) & MASK
        b = carry & MASK

    # If a is a valid positive 32-bit int, return it directly.
    # Otherwise, interpret the 32-bit unsigned value as a signed negative.
    if a <= MAX:
        return a
    else:
        return ~(a ^ MASK)


print(getSum(1, 2))     # 3
print(getSum(2, 3))     # 5
print(getSum(-1, 1))    # 0
print(getSum(-10, 4))   # -6
print(getSum(0, 0))     # 0

Complexity

• Time: O(1) — at most 32 iterations (one per bit)
• Space: O(1)

Common Pitfalls

Infinite loop with negative numbers in Python. Unlike C++ or Java, Python integers don’t wrap around at 32 bits. Without masking, the carry can keep growing indefinitely for negative inputs. Always mask intermediate results with & 0xFFFFFFFF.

Not converting back to signed. After masking, values >= 2³¹ represent negative numbers in 32-bit two’s complement. The expression ~(a ^ MASK) effectively flips the sign: a ^ MASK inverts all 32 bits, and ~ then adds -1 via Python’s bitwise complement, giving the correct negative value.

Forgetting that b must also be masked. The carry (a & b) << 1 can exceed 32 bits too. Mask both a and b at every iteration.