Sum of Two Integers without Arithmetic Operators

Add two integers without using arithmetic operators.

Example 1

Input: a = 1, b = 5
Output: 6

Solution 1: Bit Manipulation

Intuition

Let us consider, addition between two bits $A$ and $B$ (carry is represented as $C$ and sum is represented as $S$).

From the truth table clearly, carry, $C = A \& B$ and sum, $S = A \oplus B$.

This is the concept behind half-adder.

Implementation

int getSum(int a, int b) {
    // iterate as long as there is carry
    while (b != 0) {
        // carry: AND operation
        int carry = a & b;
        // sum: XOR operation
        a = a ^ b;
        // left shift carry so as to use in
        // the next step
        b = (unsigned)carry << 1;
    }
    return a;
}

Solution 2: Bit Manipulation (Recursion)

Implementation

We can also implement the above solution using recursion.

int getSum(int a, int b) {
    // recurse as long as there is carry
    if (b != 0) {
        // carry: AND operation
        int carry = a & b;
        // sum: XOR operation
        return getSum(a ^ b, (unsigned)carry << 1);
    }
    return a;
}

Complexity Analysis

• Time Complexity: $O(1)$
• Space Complexity: $O(1)$

Credits

The half adder image is taken from WikiMedia Commons (Author: inductiveload, available in public domain).