Sum of Two Integers
MedPrompt
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: 3Example 2:
Input: a = 2, b = 3
Output: 5
Constraints:
-1000 <= a, b <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses recursion to simulate the process of binary addition. It's based on the principle that a + b can be expressed as the sum of two parts: the sum without considering carries (a XOR b) and the carries themselves ((a AND b) << 1). The function calls itself with these two new values until the carry part becomes zero.
Algorithm
- The function
getSum(a, b)is defined to compute the sum recursively. - Base Case: If
b(which represents the carry) is 0, it means there are no more carries to add. The current value ofais the final sum, so we returna. - Recursive Step: If
bis not 0, we need to perform another round of addition.- The sum of bits without considering the carry is calculated as
a ^ b. - The new carry is calculated as
(a & b) << 1. The&operation finds where both bits are 1, and<< 1shifts this carry to the next significant bit position. - The function calls itself with these two new values:
getSum(a ^ b, (a & b) << 1).
- The sum of bits without considering the carry is calculated as
Walkthrough
The core idea is to break down the addition into simpler bitwise operations.
a ^ bgives the sum ofaandbat each bit position, but without handling the carry. For example,1+1=0(correct sum bit),1+0=1,0+1=1.a & bidentifies the bit positions where a carry is generated (i.e., where both bits are 1).(a & b) << 1shifts these carries one position to the left, so they can be added to the next higher bit position. The problema + bis thus transformed into(a ^ b) + ((a & b) << 1). We can solve this new addition problem recursively. The base case for the recursion is when the second number (representing the carries) becomes 0. At this point, the first number holds the final sum.
class Solution { public int getSum(int a, int b) { // Base case: if the second number (carry) is 0, the first number is the sum. if (b == 0) { return a; } // Recursive step: // a ^ b is the sum without carry // (a & b) << 1 is the carry return getSum(a ^ b, (a & b) << 1); }}Complexity
Time
O(1) - The number of recursive calls is at most the number of bits in the integer. For a fixed-size integer (like a 32-bit `int` in Java), this is a constant number of operations.
Space
O(1) - The recursion depth is bounded by the number of bits in the integer type (e.g., 32). Since this is a fixed number, the space used by the call stack is constant.
Trade-offs
Pros
Elegant and concise implementation.
Correctly handles negative numbers due to two's complement arithmetic.
Cons
Slightly more overhead than the iterative version due to function calls.
In theory, could lead to a stack overflow if integers had a very large number of bits, though this is not an issue for standard 32-bit or 64-bit integers.
Solutions
Solution
public class Sum_of_Two_Integers { public static void main ( String [] args ) { Sum_of_Two_Integers out = new Sum_of_Two_Integers (); // System.out.println(out.getSum(1, 2)); // no carry // 2+2 // recurion-1: sum=0, carry= (10)左移1位 =(100)=4 // recursion-2: a=0,b=4 // recursion-3: b=0 System . out . println ( out . getSum ( 2 , 2 )); // with carry } public int getSum ( int a , int b ) { if ( b == 0 ){ // complete the operation when there is no carry return a ; } int sum , carry ; sum = a ^ b ; // step-1 sum carry = ( a & b )<< 1 ; // step-2 sum return getSum ( sum , carry ); } } ///////// class Solution { public int getSum ( int a , int b ) { return b == 0 ? a : getSum ( a ^ b , ( a & b ) << 1 ); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.