LeetCode 371: Sum of Two Integers

Problem Restatement

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

The problem is asking us to implement integer addition using bit operations. The official statement gives examples such as a = 1, b = 2, with output 3.

Input and Output

Example function shape:

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

Examples

Example 1:

a = 1
b = 2

The answer is:

3

Example 2:

a = 2
b = 3

Binary form:

2 = 010
3 = 011

Adding them gives:

5 = 101

So the answer is:

5

Example 3:

a = 2
b = -5

The answer is:

-3

Negative numbers need extra care in Python because Python integers do not have a fixed bit width.

First Thought: Use Normal Addition

Normally we would write:

return a + b

But the problem forbids + and -.

So we need to reproduce addition at the bit level.

Key Insight

Binary addition has two parts:

For one bit:

The sum bit matches XOR.

The carry appears only when both bits are 1, which matches AND. Then the carry moves one bit left.

So we repeatedly do:

sum_without_carry = a ^ b
carry = (a & b) << 1

Then add those two parts again using the same process.

Stop when there is no carry.

Why Python Needs a Mask

In many languages, integers have fixed width, such as 32 bits.

Python integers can grow without limit.

That causes trouble for negative numbers because their sign extension conceptually continues forever.

So we simulate 32-bit signed integer arithmetic with:

MASK = 0xFFFFFFFF
MAX_INT = 0x7FFFFFFF

After each step, we keep only the lower 32 bits:

& MASK

At the end:

To convert a 32-bit negative value back into Python’s negative integer form, use:

~(a ^ MASK)

Algorithm

1. Set:

MASK = 0xFFFFFFFF
MAX_INT = 0x7FFFFFFF

2. While b is not zero:
   • Compute carry:

carry = (a & b) << 1

• Compute sum without carry:

a = a ^ b

• Apply the mask to keep 32 bits.
• Set b to the carry.

3. Convert the result back to Python signed integer form.
4. Return it.

Correctness

At each step, a ^ b computes the bitwise sum without carry.

The expression (a & b) << 1 computes every carry bit and moves it to the position where it must be added next.

Therefore, replacing (a, b) with:

(a ^ b, (a & b) << 1)

preserves the total mathematical value of a + b.

Each iteration moves carries left. Under the 32-bit mask, the process must terminate because there are only 32 bit positions. When b becomes zero, no carries remain, and a contains the final 32-bit sum.

The final conversion interprets the 32-bit result as a signed integer. Therefore, the algorithm returns the same value as normal integer addition under the problem constraints.

Complexity

Implementation

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF
        max_int = 0x7FFFFFFF

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

        if a <= max_int:
            return a

        return ~(a ^ mask)

Code Explanation

The mask keeps numbers inside 32 bits:

mask = 0xFFFFFFFF

The largest positive signed 32-bit integer is:

max_int = 0x7FFFFFFF

Inside the loop, compute carry first:

carry = ((a & b) << 1) & mask

Then compute sum without carry:

a = (a ^ b) & mask

Then continue adding the carry:

b = carry

When the loop ends, a is the 32-bit result.

If it fits in the positive signed range, return it directly:

if a <= max_int:
    return a

Otherwise, convert from 32-bit two’s complement to Python negative integer:

return ~(a ^ mask)

Testing

def run_tests():
    s = Solution()

    assert s.getSum(1, 2) == 3
    assert s.getSum(2, 3) == 5
    assert s.getSum(-1, 1) == 0
    assert s.getSum(2, -5) == -3
    assert s.getSum(-4, -6) == -10
    assert s.getSum(0, 0) == 0
    assert s.getSum(1000, -1000) == 0

    print("all tests passed")

run_tests()

Test meaning: