Sum of Two Integers

MEDIUM

Description

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

Checkout 2 different approaches to solve Sum of Two Integers. Click on different approaches to view the approach and algorithm in detail.

Bit Manipulation (Recursive)

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).

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.

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Sum of Two Integers. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Sum of Two Integers

Patterns:

MathBit Manipulation

Companies:

Hulu |