题目

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

示例 1:

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

链接：https://leetcode-cn.com/problems/sum-of-two-integers

题解

题目说不能使用运算符+ 和-，那么我们就要使用其他方式来替代这两个运算符的功能。

位运算中的加法
我们先来观察下位运算中的两数加法，其实来来回回就只有下面这四种：

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0（进位 1）

仔细一看，这可不就是相同位为 0，不同位为 1 的异或运算结果嘛~

异或和与运算操作
我们知道，在位运算操作中，异或的一个重要特性是无进位加法。我们来看一个例子：

a = 5 = 0101
b = 4 = 0100

a ^ b 如下：

0 1 0 1
0 1 0 0
-------
0 0 0 1

a ^ b 得到了一个无进位加法结果，如果要得到 a + b 的最终值，我们还要找到进位的数，把这二者相加。在位运算中，我们可以使用与操作获得进位：

a = 5 = 0101
b = 4 = 0100

a & b 如下：

0 1 0 1
0 1 0 0
-------
0 1 0 0

由计算结果可见，0100 并不是我们想要的进位，1 + 1 所获得的进位应该要放置在它的更高位，即左侧位上，因此我们还要把 0100 左移一位，才是我们所要的进位结果。

那么问题就容易了，总结一下：

a + b 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)
无进位加法使用异或运算计算得出
进位结果使用与运算和移位运算计算得出
循环此过程，直到进位为 0

代码实现

	//非递归实现
	public int getSum(int a, int b) {
        int sum = a ^ b; //异或运算，相异为1，得到相加但没有进位的结果
        int carry = (a & b) << 1; //与运算，均为1为1，并且左移一位得到进位的结果
        //a + b 就是 sum + carry，将进位的结果和没进位的结果相加
        while(carry != 0){
            int temp = (sum & carry) << 1; //将进位的结果保存下来
            sum ^= carry;	//得到相加但没进位的结果
            carry = temp;	//保存进位的结果，并再次循环
        }
        return sum;
    }


	//递归实现
	int getSum(int a, int b) 
	{
		int sum, carry; 
        sum = a ^ b;
		carry = (a & b) << 1;

        if(carry != 0){
			return getSum(sum, carry);
		}
		return sum;
	}