Sum of Two Integers — Bitwise Addition Without Plus or Minus

Problem Statement#

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

Constraints:

• -1000 <= a, b <= 1000

Example 1:

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

Example 2:

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

Example 3:

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

Why This Problem Matters#

Sum of Two Integers reveals what every digital adder inside a CPU is doing under the hood. Hardware adders are built from half-adders (XOR for sum, AND for carry) chained into full-adders with carry propagation. Solving this problem teaches you to think like silicon — and that mental model is exactly what FAANG interviewers (especially at Apple, Amazon, and Microsoft systems teams) probe with this question.

The problem also forces you to confront two's complement representation head-on: handling negative numbers without - requires understanding why ~x + 1 = -x and how sign extension interacts with XOR. Candidates who breeze through this question on a whiteboard signal deep low-level fluency, which translates well to embedded, compiler, and operating-systems roles.

The Core Insight#

Binary addition decomposes into two parallel operations on bit positions:

1. Sum without carry is exactly the XOR of the two bits: a ^ b. Why? 0+0=0, 0+1=1, 1+0=1, 1+1=10 (sum bit is 0). The first three match XOR exactly; the fourth has sum bit 0, which is 1 ^ 1 = 0. So XOR captures the sum bit perfectly.

2. Carry happens only when both bits are 1: a & b. The carry must shift left by one position to apply to the next bit, giving (a & b) << 1.

Adding the no-carry sum and the shifted carry can itself produce more carries, so we iterate:

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

For negative numbers in two's complement, the same iteration converges because subtraction is just adding the two's complement (bit pattern). The only language-specific subtlety is how to simulate fixed-width 32-bit arithmetic in Python, which uses arbitrary-precision integers.

Visual Dry Run#

Compute 5 + 3:

Loop exits when b == 0. Final answer: 8. Note that the loop ran four times because each iteration pushes the carry one bit higher; in the worst case the loop runs O(word_size) times, which is constant for fixed-width integers.

Solution (Optimal)#

Python#

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # Python integers are unbounded, so simulate 32-bit arithmetic
        MASK = 0xFFFFFFFF       # keep only the low 32 bits
        MAX_INT = 0x7FFFFFFF    # boundary between positive and negative
 
        while b != 0:
            # carry is shifted up by one and masked to 32 bits
            carry = ((a & b) << 1) & MASK
            # XOR computes the sum without carry, masked to 32 bits
            a = (a ^ b) & MASK
            b = carry
 
        # If a falls in the negative range, recover its signed value
        return a if a <= MAX_INT else ~(a ^ MASK)

JavaScript#

var getSum = function(a, b) {
    // JS bitwise ops are 32-bit signed; sign extension is automatic
    while (b !== 0) {
        const carry = (a & b) << 1;   // bits where both are 1, shifted up
        a = a ^ b;                    // sum bits with no carry
        b = carry;                    // remaining carry to add next round
    }
    return a;
};

Complexity: Time O(1) bounded by 32 iterations (one per bit position), Space O(1).

Common Mistakes#

1. Using arbitrary-precision integers without masking in Python. Without & 0xFFFFFFFF, the carry shifts grow without bound when a or b is negative, causing infinite loops.

2. Forgetting to recover the signed value in Python. After the loop, a is a non-negative integer in [0, 2^32). Values above 2^31 - 1 represent negatives in two's complement; convert with ~(a ^ MASK).

3. Confusing carry direction. Carry shifts left because it represents the next-higher bit position. Shifting right is wrong.

4. Using (a + b) - 0 or arithmetic tricks. The problem disallows + and -. Trying to sneak them in via subtraction or unary minus violates the constraint.

5. Not handling the case where one input is zero. Some candidates write while a != 0 || b != 0. The correct loop condition is while b != 0 because once there's no carry, a already holds the sum.

6. Stack overflow with naive recursion. A recursive form getSum(a ^ b, (a & b) << 1) works in compiled languages with tail-call optimization but blows the Python recursion limit for adversarial inputs. Prefer iteration.

Interview Tips#

• Start by drawing a 1-bit half-adder: input a, b; output sum = a ^ b, carry = a & b. This grounds your explanation in hardware.
• Generalize to multi-bit by chaining half-adders into a ripple-carry adder, motivating the iterative carry propagation.
• Mention that real CPUs use carry-lookahead adders to compute multi-bit carries in parallel for speed; the iterative approach is conceptually simpler but slower in hardware.
• For negative inputs, explicitly explain two's complement: "Negation flips bits and adds one." This signals you understand the representation, not just the arithmetic.
• In Python, walk through the masking step. Interviewers love to see candidates handle language-specific quirks consciously.

Follow-up Questions#

Q: How would you subtract without using -? Compute a + (~b + 1) because -b == ~b + 1 in two's complement. Use your getSum to add a and ~b + 1 (where + 1 is itself implemented via getSum(b, 1) flipped).

Q: How would you multiply without using *? Use shift-and-add: iterate through each bit of b. If bit i is set, add a << i to the running result.

Q: How does this map to hardware? Each iteration corresponds to one stage of a ripple-carry adder. Real CPUs use carry-lookahead adders to compute carries in O(log n) stages instead of O(n).

Q: What is the maximum number of iterations needed? For 32-bit integers, the carry can propagate at most 32 bit positions, so the loop runs at most 32 times. After that, the carry must be zero.

Key Takeaways#

• Binary addition splits into XOR (sum without carry) and AND-shift-left (carry to apply to the next bit).
• Iterate until the carry becomes zero; the loop runs at most word_size times.
• Two's complement representation makes the same algorithm work for negatives without modification — in fixed-width languages.
• In Python, mask each step with 0xFFFFFFFF and recover the signed value at the end to simulate 32-bit arithmetic.
• This problem mirrors real CPU adders; understanding it pays off in compiler, embedded, and systems interviews.
• Pair with shift-based multiplication and two's complement subtraction to round out the bitwise arithmetic toolkit.