Sum of Two Integers

问题描述

这个题是学弟跟我说的一道Hulu的面试题，感觉还是挺意思的，所以记录一下。问题如下：

求两个数a、b的和，不使用加法。（当然乘除法减法也是不能使用的）。

---

思路

这题第一眼看的话，应该是通过位操作来实现。我最初的想法是一位一位进行操作。对于每一位，具体操作如下：

• 和的该位的值 = a的当前位 异或 b的当前位 异或 进位
• 下一个进位：a的当前位、b的当前位、进位。三者有两个为1即为1，否则为0。

---

我发现首先，获得 下一个进位 是不好描述的，而且对于单个位的操作，以及最后汇总成和也是很麻烦的。所以单个位的操作也就没什么意义了，思路转为对a、b两个数做整体操作。

我们平时做加法的时候也是同位置的两个数相加，然后再加上从前面进上来的位，即可得到当前位的数。我们分开看：

• 两个数相加，先得到当前位的数。显然是 a^b（a异或b）。

• 当前位产生的进位是，a&b（a与b），因为只有a的位是1，b也是1才能向前产生进位。

• 问题转换为，a^b的值与 (a&b)<<1 的值相加（左移一位使进位加到正确的位上）。这就变成了一个子问题，即可用递归求解。递归的返回条件显而易见，就是当进位是0时，返回结果。

---

Code

代码很短就两行

int twoSum(int a, int b){
    if (b == 0) return a; //将b理解为进位
    else return twoSum(a^b, (a&b)<<1 );
}