Given two integers a and b, return the sum of the two integers without using the operators + and -.
Example 1:
Input: a = 1, b = 2 Output: 3
Example 2:
Input: a = 2, b = 3 Output: 5
Constraints:
-1000 <= a, b <= 1000Problem Overview: Given two integers a and b, return their sum without using the + or - operators. The trick is to simulate how addition works at the bit level using operations from bit manipulation.
Approach 1: Bitwise Iterative Approach (Time: O(1), Space: O(1))
Addition in binary can be separated into two parts: the sum without carry and the carry itself. The XOR operation (a ^ b) gives the partial sum where bits differ, which is exactly how addition behaves without carrying. The AND operation (a & b) identifies positions where both bits are 1, which produces a carry. Shifting this carry left by one ((a & b) << 1) moves it to the correct position for the next addition step.
The algorithm repeatedly computes the partial sum using XOR and the carry using AND + left shift. Then it replaces a with the partial sum and b with the carry. This continues until the carry becomes zero, meaning no more bits need propagation. Because integers are limited to a fixed number of bits (typically 32), the loop runs at most a constant number of times, giving O(1) time complexity.
This approach relies purely on bit-level operations and works for both positive and negative numbers using two's complement representation. It is the standard solution expected when the problem is tagged with math and bit manipulation.
Approach 2: Recursive Bitwise Approach (Time: O(1), Space: O(1))
The same XOR-and-carry logic can be expressed recursively. Compute the partial sum with a ^ b and compute the carry with (a & b) << 1. Instead of looping, call the function again with these two new values. Each recursive call resolves one level of carry propagation.
The base case occurs when the carry becomes zero. At that point, the partial sum already represents the final result and can be returned directly. Since the maximum number of carry propagations is bounded by the number of bits in the integer representation (around 32), the recursion depth is constant.
This version is conceptually elegant because it mirrors how binary addition propagates carries step by step. However, many engineers prefer the iterative version in production code to avoid recursion overhead and keep stack usage minimal.
Recommended for interviews: The iterative bitwise approach is what interviewers usually expect. It demonstrates that you understand how addition works at the binary level and how XOR and AND simulate sum and carry. Mentioning the recursive variation shows deeper understanding, but implementing the iterative version quickly signals strong familiarity with bit manipulation fundamentals.
This approach imitates the addition mechanism in digital circuits using bitwise operations. The key operations involved are:
The solution utilizes a while-loop that continues until there is no carry left. The carry is calculated as a & b, and the sum without carry is calculated via a ^ b. The carry is then shifted left by one position (as happens in binary addition) and added to 'b' for the next iteration until the carry becomes zero. Each iteration moves the carry one bit to the left (achieved by << 1), imitating the binary addition process.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of bits needed to represent the numbers.
Space Complexity: O(1), constant space usage.
This approach is an extension of the iterative bitwise method but uses recursive calls to achieve the result. Instead of using a loop, it relies on recursive function calls to process the sum and carry until the carry becomes zero.
In this C solution, the base case for the recursion is when b (carry) becomes zero, at which point a contains the result. sum is calculated using XOR and carry is calculated and shifted. These new values are passed in the next recursive call.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of bits.
Space Complexity: O(n), due to the recursive call stack.
| Approach | Complexity |
|---|---|
| Bitwise Iterative Approach | Time Complexity: O(n), where n is the number of bits needed to represent the numbers. |
| Recursive Bitwise Approach | Time Complexity: O(n), where n is the number of bits. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitwise Iterative Approach | O(1) | O(1) | Best general solution. Preferred in interviews and production due to constant space and clear carry handling. |
| Recursive Bitwise Approach | O(1) | O(1) | Useful for explaining the concept of recursive carry propagation in binary addition. |
Two Sum - Leetcode 1 - HashMap - Python • NeetCode • 1,640,490 views views
Watch 9 more video solutions →Practice Sum of Two Integers with our built-in code editor and test cases.
Practice on FleetCode