Sum of Two Integers

Med

#0358Time: 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.1 company

Patterns

Math Bit Manipulation

Companies

Hulu

Prompt

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 <= 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 of a is the final sum, so we return a.
Recursive Step: If b is 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 << 1 shifts this carry to the next significant bit position.
- The function calls itself with these two new values: getSum(a ^ b, (a & b) << 1).

Walkthrough

The core idea is to break down the addition into simpler bitwise operations.

a ^ b gives the sum of a and b at each bit position, but without handling the carry. For example, 1+1=0 (correct sum bit), 1+0=1, 0+1=1.
a & b identifies the bit positions where a carry is generated (i.e., where both bits are 1).
(a & b) << 1 shifts these carries one position to the left, so they can be added to the next higher bit position. The problem a + b is 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.

1class Solution {2    public int getSum(int a, int b) {3        // Base case: if the second number (carry) is 0, the first number is the sum.4        if (b == 0) {5            return a;6        }7        // Recursive step:8        // a ^ b is the sum without carry9        // (a & b) << 1 is the carry10        return getSum(a ^ b, (a & b) << 1);11    }12}

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.

This is an iterative version of the bit manipulation approach. It uses a loop to repeatedly calculate the sum-without-carry and the carry, updating the numbers until the carry becomes zero. This method avoids recursion and is generally the most efficient and standard solution for this problem.

Algorithm

Loop as long as b (the carry part) is not equal to 0.
Inside the loop, first calculate the carry that will be generated from the current a and b. Store it in a temporary variable: carry = (a & b) << 1.
Update a to be the sum of a and b without considering the carry: a = a ^ b.
Update b to be the carry calculated in the first step. This sets up the next iteration to add the carry to the sum.
Once the loop terminates (when b becomes 0), a holds the final sum. Return a.

Walkthrough

This approach mirrors the logic of a digital half-adder circuit iteratively. We use two variables, one to hold the current sum (a) and one to hold the carry (b). In each iteration of the loop:

We calculate the carry bits. A carry is generated only when both corresponding bits in a and b are 1. This is found using the AND operator: a & b. These carries must be shifted one position to the left (<< 1) to be applied to the next bit position.
We calculate the sum of bits without considering the carry. This is achieved using the XOR operator: a ^ b.
We update a to be the sum-without-carry, and b to be the new carry. The loop continues as long as there is a carry to be added (i.e., b is not 0). When the loop finishes, a contains the final sum.

1class Solution {2    public int getSum(int a, int b) {3        while (b != 0) {4            // Calculate carry. We need a temporary variable because we are modifying 'a'.5            int carry = (a & b) << 1;6            7            // 'a' becomes the sum without carry8            a = a ^ b;9            10            // 'b' becomes the carry for the next iteration11            b = carry;12        }13        return a;14    }15}

Complexity

Time

O(1) - The loop runs at most as many times as there are bits in the integer (e.g., 32). This is a constant number, making the time complexity constant.

Space

O(1) - The algorithm uses a fixed amount of extra space (for the `carry` variable), regardless of the input values.

Trade-offs

Pros

Most efficient solution in terms of both time and space.
Avoids recursion overhead, making it slightly faster in practice than the recursive version.
Handles negative numbers correctly due to the properties of two's complement representation.

Cons

The logic can be non-obvious for those unfamiliar with bitwise operations.

Solutions

Solution

1public 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 ); } }

1class Solution { public: int getSum ( int a , int b ) { while ( b ) { unsigned int carry = ( unsigned int ) ( a & b ) << 1 ; a = a ^ b ; b = carry ; } return a ; } };

1''' 0x80000000 Taking the binary of 0x80000000 we get: 1000 0000 0000 0000 0000 0000 0000 0000 equivalent decimal value is 2,147,483,648(1's complement conversion) https://stackoverflow.com/questions/18813875/how-is-0x80000000-equated-to-2147483648-in-java 0xffffffff Taking the binary of 0xffffffff we get: 1111 1111 1111 1111 1111 1111 1111 1111 No sign bit in python 0xFFFFFFFF masking to detect int32 overflow x & 0xFFFFFFFF == x ===> will return True if x doesn't oveflow and x is larger than 0. https://stackoverflow.com/questions/36819849/detect-int32-overflow-using-0xffffffff-masking-in-python >>> bin(0x80000000) '0b10000000000000000000000000000000' >>> bin(0xffffffff) '0b11111111111111111111111111111111' >>> 0x80000000 & 0xffffffff 2147483648 >>> 0x80000000 ^ 0xffffffff 2147483647 ''' ''' >>> 1^1 0 >>> 0^0 0 >>> 1^0 1 >>> 0^1 1 ''' class Solution : def getSum ( self , a : int , b : int ) -> int : mask = 0xFFFFFFFF kMax = 0x80000000 # the result of each step is passed recursively to the getSum function # until there is no carry (b == 0) # at that point, the function returns the final sum. while a : a , b = (( a & b ) << 1 ) & mask , ( a ^ b ) & mask return b if b < kMax else ~ ( b ^ mask ) # ~(b ^ mask) turning it back into a positive number if b was negative class Solution : # also passing OJ by switching a/b def getSum ( self , a : int , b : int ) -> int : mask = 0xFFFFFFFF kMax = 0x80000000 # the result of each step is passed recursively to the getSum function # until there is no carry (b == 0) # at that point, the function returns the final sum. while b : a , b = ( a ^ b ) & mask , (( a & b ) << 1 ) & mask return a if a < kMax else ~ ( a ^ mask ) ############# class Solution : # no mast, no overflow consideration def getSum ( a : int , b : int ) -> int : if b == 0 : return a sum = a ^ b # Step 1: sum without carry carry = ( a & b ) << 1 # Step 2: calculate carry return getSum ( sum , carry )

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.

← Previous

Previous problem

Next problem