Given two integers a and b, calculate and return their sum 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

Approach

#

First, let us explain what an adder is.

An adder, as its name suggests, is a tool for performing addition. A two-input binary adder should have two outputs: one is the sum bit, and the other is the carry.

Here is the corresponding table:

From the table above, we can see that the final result consists of the sum bit and the carry.

For binary numbers, the sum-bit operation is clearly an XOR operation, while the carry operation is an AND operation. Therefore, we obtain the equation:

• a + b = a ^ b + (a & b) * 2
• That is,
• a + b = a ^ b + (a & b) « 1

We have changed one plus sign into another plus sign, which does not seem very useful.

In this situation, however, we can consider whether recursion is possible. Notice that a & b is guaranteed to become smaller and smaller, eventually approaching 0. Once b approaches 0, the answer is a, which gives us the base case for recursion.

Rust Code

#

# struct Solution;
impl Solution {
    pub fn get_sum(a: i32, b: i32) -> i32 {
        if b == 0 {
            a
        } else {
            Solution::get_sum(a ^ b, (a & b) << 1)
        }
    }
}

C++ Code

#

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