No.371 两整数之和

给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2
输出：3

示例 2：

输入：a = 2, b = 3
输出：5

提示：

• -1000 <= a, b <= 1000

思路分析

先给大家讲一下什么是加法器。 加法器，顾名思义，就是做加法运算的工具。一个二输入的二进制加法器，应该有两个输出，一个是原原，一个是进位。 下面给大家打个表看看。

观察上表，我们不难看出，由原位和进位组成了最终的答案。 而原位操作对于二进制来说就是一个很明显的异或(XOR)操作，而进位操作也就是与(AND)操作。那么我们可以得到一个等式：

• a + b = a ^ b + (a & b) * 2
• 也就是
• a + b = a ^ b + (a & b) << 1

从一个加号变成了另一个加号！好像没啥用。 但遇到这种情况，我们可以考虑，是否可以递归。 观察可得，a & b一定是一个越来越小的数字，它最后一定会趋向于0。一旦b趋向于0，那么答案就是a，我们就有了递归的基础。

Rust代码

#![allow(unused)]
fn main() {
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++代码

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