LeetCode 371 - Sum of Two Integers

The problem asks us to compute the sum of two integers without using the arithmetic operators + and -. Instead of relying on normal arithmetic, we must use bit manipulation to simulate how addition works at the binary level. The input consists of two integers, a and b.

leetcodemediummathbit-manipulation

LeetCode Problem 371

Difficulty: 🟡 Medium
Topics: Math, Bit Manipulation

Solution

Problem Understanding

The problem asks us to compute the sum of two integers without using the arithmetic operators + and -. Instead of relying on normal arithmetic, we must use bit manipulation to simulate how addition works at the binary level.

The input consists of two integers, a and b. These integers can be positive, negative, or zero. The expected output is a single integer representing their sum.

Although the constraints are relatively small, from -1000 to 1000, the intent of the problem is not about handling large inputs efficiently. Instead, the goal is to demonstrate an understanding of binary arithmetic and bitwise operations.

The key challenge comes from the restriction against using + and -. A naive implementation that directly uses those operators is invalid. We must instead reconstruct the addition process manually using bit operations such as XOR, AND, and left shift.

Several edge cases are important to think about upfront. Adding zero should return the other number unchanged. Adding negative numbers introduces complications because Python integers are not limited to 32 bits, unlike many other languages. Cases involving both positive and negative values can also create infinite loops if signed integers are not handled carefully. Finally, overflow behavior must be simulated consistently with 32-bit signed integer arithmetic.

Approaches

Brute Force Approach

A straightforward way to solve the problem without directly using + would be to repeatedly increment or decrement one number while adjusting the other.

For example, if b is positive, we could repeatedly increase a by one and decrease b by one until b becomes zero. Similarly, if b is negative, we could repeatedly decrease a and increase b.

This approach is conceptually simple because it mimics counting. However, it is inefficient because the number of operations depends directly on the magnitude of the numbers involved. Even though the constraints are small in this problem, the solution does not scale well and misses the intended bit manipulation insight.

Optimal Bit Manipulation Approach

The important observation is that binary addition can be separated into two independent operations.

First, XOR (^) computes the sum of bits without considering carries. For example:

  • 0 ^ 0 = 0
  • 1 ^ 0 = 1
  • 1 ^ 1 = 0

The last case matches ordinary addition except that the carry is ignored.

Second, AND (&) identifies positions where carries occur. If both bits are 1, a carry must be propagated to the next position. Shifting the result left by one places the carry in the correct position.

This leads to a repeating process:

  1. Compute the partial sum using XOR.
  2. Compute the carry using AND and left shift.
  3. Repeat until no carry remains.

This method efficiently simulates binary addition and runs in constant time for fixed-width integers.

Approach Time Complexity Space Complexity Notes
Brute Force O(|b|) O(1) Repeatedly increments or decrements values
Optimal O(1) O(1) Uses bitwise operations to simulate binary addition

Algorithm Walkthrough

  1. Start with two integers, a and b.
  2. Use XOR (a ^ b) to compute the sum without carries. XOR behaves like binary addition where 1 + 1 becomes 0 instead of generating a carry.
  3. Use AND (a & b) to identify all bit positions that generate a carry. Shift the result left by one because carries affect the next higher bit position.
  4. Replace a with the partial sum and replace b with the carry value. This effectively prepares the next iteration of addition.
  5. Continue repeating the process while the carry is nonzero. Each iteration resolves one level of carries.
  6. Because Python integers are unbounded, apply a 32-bit mask during computation. This ensures negative numbers behave like standard signed integers in languages such as C++ or Java.
  7. After the loop finishes, convert the result back into a proper signed integer representation if necessary.

Why it works

The algorithm works because binary addition can always be decomposed into two parts: the current digit sum and the carry. XOR correctly computes the digit sum without carries, while AND followed by a left shift correctly computes the carry contribution. Repeating this process eventually eliminates all carries, at which point the remaining value is the final sum.

Python Solution

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

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

            a = partial_sum
            b = carry

        # Convert from unsigned to signed integer
        if a <= MAX_INT:
            return a

        return ~(a ^ MASK)

The implementation follows the exact bit manipulation process described in the algorithm walkthrough.

The MASK constant ensures all intermediate values remain within 32 bits. This is necessary because Python integers can grow arbitrarily large, unlike fixed-width integers in many programming languages.

Inside the loop, partial_sum stores the XOR result, which represents addition without carries. The carry variable stores all carry bits shifted into their correct positions.

The loop continues until no carry remains. At that point, a contains the completed result.

Finally, the code converts the unsigned 32-bit representation back into a signed integer. Values larger than MAX_INT represent negative numbers in two's complement form, so the conversion restores the correct signed result.

Go Solution

func getSum(a int, b int) int {
	const mask = 0xFFFFFFFF
	const maxInt = 0x7FFFFFFF

	for b != 0 {
		partialSum := (a ^ b) & mask
		carry := ((a & b) << 1) & mask

		a = partialSum
		b = carry
	}

	if a <= maxInt {
		return a
	}

	return ^(a ^ mask)
}

The Go implementation is very similar to the Python version because Go also supports bitwise operators directly.

One notable difference is that Go integers are fixed-width, unlike Python integers. However, explicitly using the mask still ensures consistent 32-bit behavior and matches the intended LeetCode solution pattern.

The conversion from unsigned to signed representation is handled the same way as in Python using bitwise negation.

Worked Examples

Example 1

Input:

a = 1
b = 2

Binary representation:

1 = 01
2 = 10
Iteration a b a ^ b (a & b) << 1
Start 1 2 3 0
End 3 0 - -

Since the carry becomes zero immediately, the algorithm stops.

Result:

3

Example 2

Input:

a = 2
b = 3

Binary representation:

2 = 10
3 = 11
Iteration a b a ^ b (a & b) << 1
Start 2 3 1 4
Next 1 4 5 0
End 5 0 - -

The first iteration produces a partial sum of 1 and a carry of 4. The second iteration resolves the carry and produces the final answer.

Result:

5

Complexity Analysis

Measure Complexity Explanation
Time O(1) At most 32 iterations for 32-bit integers
Space O(1) Uses only a constant amount of extra memory

The algorithm runs in constant time because the number of bits in a standard integer is fixed. Each iteration resolves carries for at least one bit position, so the loop cannot exceed the number of bits in the integer representation. The space usage is constant because only a few integer variables are maintained throughout execution.

Test Cases

solution = Solution()

assert solution.getSum(1, 2) == 3          # basic positive addition
assert solution.getSum(2, 3) == 5          # another simple case
assert solution.getSum(0, 0) == 0          # both zero
assert solution.getSum(5, 0) == 5          # adding zero
assert solution.getSum(0, 7) == 7          # zero as first operand
assert solution.getSum(-1, 1) == 0         # positive and negative cancel out
assert solution.getSum(-5, -7) == -12      # both negative
assert solution.getSum(-10, 3) == -7       # negative plus positive
assert solution.getSum(1000, 1000) == 2000 # upper boundary values
assert solution.getSum(-1000, -1000) == -2000 # lower boundary values
assert solution.getSum(123, -123) == 0     # exact cancellation
assert solution.getSum(999, -1) == 998     # carry with negative
Test Why
1, 2 Verifies basic addition
2, 3 Verifies carry handling
0, 0 Tests zero behavior
5, 0 Ensures adding zero works
0, 7 Ensures operand order does not matter
-1, 1 Tests cancellation between signs
-5, -7 Tests negative addition
-10, 3 Tests mixed signs
1000, 1000 Tests upper boundary values
-1000, -1000 Tests lower boundary values
123, -123 Tests exact negation
999, -1 Tests carry propagation with negatives

Edge Cases

One important edge case is adding zero to another number. A buggy implementation might unnecessarily modify the value or fail to terminate correctly. In this implementation, if b is initially zero, the loop never executes, and the function immediately returns a.

Another critical edge case involves negative numbers. Python uses arbitrary-length integers rather than fixed-width integers, so bit operations on negative values can behave differently from languages like C++ or Java. Without masking intermediate results to 32 bits, the carry value might never become zero, causing an infinite loop. The implementation avoids this by consistently applying the 32-bit mask.

A third important edge case is when carries propagate across multiple bits. For example, adding 3 and 1 in binary produces repeated carry propagation:

011
001
---
100

The algorithm correctly handles this because it repeatedly recomputes the carry until no carry bits remain. This iterative process guarantees that all cascading carries are resolved before returning the result.