LeetCode-371-两整数之和

1. 题目：

两整数之和

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

示例 1:

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

示例 2:

1 2	输入: a = -2, b = 3 输出: 1

2. 解题：

使用二进制加法，也就是位运算。二进制加法有四种组合：1 + 1 = 10, 1 + 0 =1, 0 + 1 = 1, 0 + 0 = 0，我们发现只有一种情况是需要进位的，而且是都为1时。

我们使用&运算来找出发生进位的位，并且将结果左移一位就可以得到进位carry。

我们使用^异或运算来找出不发生进位保留下的位sum。

将sum和carry“相加”。

我们会发现依然可能会出现“进位现象”，因此递归调用getSum()，直到carry = 0时返回sum。

代码：

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