Sum of Two Integers

medium
Bit ManipulationMathBit Manipulation

Calculate the sum of two integers a and b without using the + or - operators. Implement a function that performs addition using only bitwise operations.

Examples

Example 1

  • Input: a = 1, b = 2
  • Output: 3
  • Explanation: 1 + 2 = 3, computed using bitwise operations.

Example 2

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

Example 3

  • Input: a = -1, b = 1
  • Output: 0

Constraints

  • -1000 <= a, b <= 1000

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Iterative Bit Manipulation

Intuition

When we add two binary numbers, the sum without carrying is equivalent to XOR, and the carry is equivalent to AND shifted left by one. We can repeatedly compute the XOR (partial sum) and the carry until the carry becomes zero. At that point, the XOR result holds the final sum. This works because XOR captures the bit positions where only one bit is set, while AND captures positions where both bits are set and a carry is needed.

Algorithm

  1. Compute the XOR of `a` and `b` to get the partial sum (bits that differ).
  2. Compute the AND of `a` and `b`, then shift left by one to get the carry.
  3. Set `a` to the partial sum (XOR result) and `b` to the carry.
  4. Repeat steps 1-3 until the carry `b` becomes zero.
  5. Return `a` as the final result.
TimeO(1) — at most 32 iterations for 32-bit integersSpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }
};
Java 21
class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }
}
Python 3.12
class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF
        MAX_INT = 0x7FFFFFFF

        a &= MASK
        b &= MASK

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

        return a if a <= MAX_INT else ~(a ^ MASK)
Go 1.26
func getSum(a int, b int) int {
    for b != 0 {
        carry := a & b
        a = a ^ b
        b = carry << 1
    }
    return a
}
Approach 2

Recursive Bit Manipulation

Intuition

The same logic can be expressed recursively. The base case is when there is no carry (b equals zero), at which point we return a. Otherwise, we recurse with the XOR as the new sum and the shifted AND as the new carry. This approach mirrors the iterative version but uses the call stack instead of a loop.

Algorithm

  1. Base case: if `b` is zero, return `a`.
  2. Compute the carry as `(a & b) << 1`.
  3. Compute the partial sum as `a ^ b`.
  4. Recurse with the partial sum and carry as the new arguments.
TimeO(1) — at most 32 recursive calls for 32-bit integersSpaceO(1) — bounded recursion depth of 32

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int getSum(int a, int b) {
        if (b == 0) return a;
        return getSum(a ^ b, (a & b) << 1);
    }
};
Java 21
class Solution {
    public int getSum(int a, int b) {
        if (b == 0) return a;
        return getSum(a ^ b, (a & b) << 1);
    }
}
Python 3.12
class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF
        MAX_INT = 0x7FFFFFFF

        a &= MASK
        b &= MASK

        if b == 0:
            return a if a <= MAX_INT else ~(a ^ MASK)

        return self.getSum((a ^ b) & MASK, ((a & b) << 1) & MASK)
Go 1.26
func getSum(a int, b int) int {
    if b == 0 {
        return a
    }
    return getSum(a^b, (a&b)<<1)
}

Frequently asked questions

What is the optimal time complexity of Sum of Two Integers?

The most efficient approach in this guide ("Recursive Bit Manipulation") runs in O(1) — at most 32 recursive calls for 32-bit integers time and uses O(1) — bounded recursion depth of 32 extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Sum of Two Integers use?

Sum of Two Integers is a medium-level Bit Manipulation problem involving Math, Bit Manipulation. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Sum of Two Integers be solved without extra space?

The most space-efficient approach in this guide uses O(1) — bounded recursion depth of 32 extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1) — bounded recursion depth of 32.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
a=
1
b=
2
Expected Output
3