题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

题解一

在十进制中，我们使用三步走的方法来做加法（以5和7为例子）：

1. 各位相加而不进位（得到2）。
2. 计算进位值（得到10）。
3. 将前两步得到的结果相加（得到12）。

在二进制中，我们也可以模拟这种方法来做加法（同样以5（101）和7（111）为例子）：

1. 各位相加而不进位（得到sum=010），可用异或操作。
2. 计算进位值（得到carry=1010），可用与操作后左移一位。
3. 将前两步得到的结果相加，即循环前两步（令num1=sum, num2=carry然后循环），当carry=0时终止循环。

下面是参考代码：

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

题解二

使用上面的思路，还可以改为更简洁的递归实现，添加递归出口即可。

下面是参考代码：

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