Sum of Two Integers

LeetCode 371: Sum of Two Integers Solution & Explanation

Problem Overview

TL;DR: Compute the sum with bitwise XOR for addition without carries and bitwise AND followed by a left shift for carries, repeating until no carry remains.

The LeetCode 371 Solution must calculate the arithmetic sum of two integers without using the + or - operators in the addition logic. Both positive and negative values are valid, so the implementation must correctly handle fixed-width two’s-complement integer representation.

LeetCode 371, Sum of Two Integers, is a popular interview question because it tests whether you understand how binary addition can be reconstructed using bit manipulation rather than arithmetic operators.

Brute Force Approach for Sum of Two Integers

A naive approach would begin with one input and repeatedly adjust it by one unit:

• If the second input is positive, increase the first value one unit at a time.
• If the second input is negative, decrease the first value one unit at a time.
• Return the resulting value after all adjustments.

Naive Pseudocode

result ← a
remaining ← b

while remaining is not zero:
    if remaining is positive:
        result ← result increased by one
        remaining ← remaining decreased by one
    else:
        result ← result decreased by one
        remaining ← remaining increased by one

return result

This approach has two problems:

1. It directly represents arithmetic addition and subtraction, which violates the operator restriction.
2. It may require one iteration for every unit in the magnitude of b.

Its time complexity is:

O(|b|)

Although the stated constraints are small, this is not the intended bitwise solution and does not scale to fixed-width integer ranges. More importantly, an implementation using the forbidden operators would fail the problem requirements.

Algorithm Strategy: Bit Manipulation Patterns

Maintain two bit patterns:

• x: the current sum excluding carry propagation
• y: the carry value that still must be added

Repeatedly perform:

1. Compute the carry with (x & y) << 1.
2. Compute the partial sum with x ^ y.
3. Assign the carry to y.
4. Continue while y is nonzero.

For signed integer support, constrain all intermediate values to 32 bits. This ensures that the behavior matches standard integer two’s-complement arithmetic and prevents an unbounded sign extension from causing an infinite loop, particularly in Python.

Execution Flow

1. Convert the inputs into 32-bit-compatible bit patterns where required.
2. Check whether the carry value is zero.
3. If a carry exists:
   • Identify bit positions where both operands contain 1.
   • Shift those carry bits one position left.
   • XOR the operands to compute the sum without carries.
4. Store the partial sum as the new first operand.
5. Store the shifted carry as the new second operand.
6. Repeat until the carry becomes zero.
7. Interpret the final 32-bit pattern as a signed integer.
8. Return the result.

For example, when adding two bit patterns:

x = current partial sum
y = current carry source

x XOR y        → partial sum without carry
(x AND y) << 1 → carry for the next iteration

Each iteration moves carry information to a higher bit position. Since the integer width is fixed, the process completes after a bounded number of iterations.

Proof of Correctness

We prove that the algorithm returns the arithmetic sum of the two input integers.

Invariant

At the start of each iteration, the pair (x, y) represents the same total as the original operands, where:

• x contains the sum of the current operands without carry propagation.
• y contains all carry contributions that remain to be applied.

For each bit position:

• x XOR y computes the correct sum bit when carry is ignored.
• x AND y identifies exactly the positions where both bits are 1, which are the positions that produce carries.
• Shifting the carry left moves each carry to the correct next bit position.

Thus, replacing (x, y) with:

((x XOR y), (x AND y) << 1)

preserves the total represented value while moving carry information into a separate operand.

When y becomes zero, no carry remains. Therefore, x contains the complete binary sum. The final signed interpretation of that 32-bit pattern is mathematically equal to the sum of the original integers.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 136: Single Number
• LeetCode 137: Single Number II
• LeetCode 389: Find the Difference
• LeetCode 268: Missing Number

These problems use XOR or related bitwise properties to cancel repeated values, isolate a unique value, or reconstruct a missing value. LeetCode 371 applies the same broader bit-manipulation discipline differently: XOR provides the carry-free component of the sum, while AND and shifting manage carry propagation.

Reference Implementation

C++ Solution for LeetCode 371

1class Solution {
2public:
3    int getSum(int a, int b) {
4        unsigned int x = static_cast<unsigned int>(a);
5        unsigned int y = static_cast<unsigned int>(b);
6
7        while (y != 0u) {
8            unsigned int carry = (x & y) << 1;
9            x = x ^ y;
10            y = carry;
11        }
12
13        return static_cast<int>(x);
14    }
15};

The C++ implementation converts both values to unsigned int so that the bitwise operations use a predictable 32-bit pattern. The loop separates carry generation from the carry-free partial sum. Casting the final pattern back to int restores the intended signed result.

Java Solution for LeetCode 371

1class Solution {
2    public int getSum(int a, int b) {
3        int mask = 0xFFFFFFFF;
4        int maxInt = 0x7FFFFFFF;
5
6        a &= mask;
7        b &= mask;
8        while (b != 0) {
9            int carry = (a & b) << 1;
10            a = (a ^ b) & mask;
11            b = carry & mask;
12        }
13
14        return a <= maxInt ? a : ~(a ^ mask);
15    }
16}

Java integers are signed 32-bit values, so the mask explicitly keeps intermediate states within 32 bits. After the loop, values up to 0x7FFFFFFF are already positive. Larger bit patterns represent negative two’s-complement values and are converted back using the final expression.

Python Solution for LeetCode 371

1class Solution:
2    def getSum(self, a: int, b: int) -> int:
3        mask = 0xFFFFFFFF
4        max_int = 0x7FFFFFFF
5
6        a &= mask
7        b &= mask
8        while b != 0:
9            carry = (a & b) << 1
10            a = (a ^ b) & mask
11            b = carry & mask
12
13        return a if a <= max_int else ~(a ^ mask)

Python integers have arbitrary precision, unlike C++ and Java integers. Without masking, negative values could retain infinitely many leading 1 bits during bitwise operations. Applying the 32-bit mask after each update reproduces fixed-width integer behavior. The final conversion restores the signed interpretation.