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

A B C S
0 0 0 0
1 0 0 1
0 1 0 1
1 1 1 0

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