程序员面试100题之三：不用＋、－、×、÷数字运算符做加法

分析&＃xff1a;这又是一道考察发散思维的很有意思的题目。当我们习以为常的东西被限制使用的时候&＃xff0c;如何突破常规去思考&＃xff0c;就是解决这个问题的关键所在。

看到的这个题目&＃xff0c;我的第一反应是傻眼了&＃xff0c;四则运算都不能用&＃xff0c;那还能用什么啊&＃xff1f;可是问题总是要解决的&＃xff0c;只能打开思路去思考各种可能性。首先我们可以分析人们是如何做十进制的加法的&＃xff0c;比如是如何得出5&＃43;17&＃61;22这个结果的。实际上&＃xff0c;我们可以分成三步的&＃xff1a;第一步只做各位相加不进位&＃xff0c;此时相加的结果是12&＃xff08;个位数5和7相加不要进位是2&＃xff0c;十位数0和1相加结果是1&＃xff09;&＃xff1b;第二步做进位&＃xff0c;5&＃43;7中有进位&＃xff0c;进位的值是10&＃xff1b;第三步把前面两个结果加起来&＃xff0c;12&＃43;10的结果是22&＃xff0c;刚好5&＃43;17&＃61;22。

前面我们就在想&＃xff0c;求两数之和四则运算都不能用&＃xff0c;那还能用什么啊&＃xff1f;对呀&＃xff0c;还能用什么呢&＃xff1f;对数字做运算&＃xff0c;除了四则运算之外&＃xff0c;也就只剩下位运算了。位运算是针对二进制的&＃xff0c;我们也就以二进制再来分析一下前面的三步走策略对二进制是不是也管用。

5的二进制是101&＃xff0c;17的二进制10001。还是试着把计算分成三步&＃xff1a;第一步各位相加但不计进位&＃xff0c;得到的结果是10100&＃xff08;最后一位两个数都是1&＃xff0c;相加的结果是二进制的10。这一步不计进位&＃xff0c;因此结果仍然是0&＃xff09;&＃xff1b;第二步记下进位。在这个例子中只在最后一位相加时产生一个进位&＃xff0c;结果是二进制的10&＃xff1b;第三步把前两步的结果相加&＃xff0c;得到的结果是10110&＃xff0c;正好是22。由此可见三步走的策略对二进制也是管用的。

接下来我们试着把二进制上的加法用位运算来替代。第一步不考虑进位&＃xff0c;对每一位相加。0加0与 1加1的结果都0&＃xff0c;0加1与1加0的结果都是1。我们可以注意到&＃xff0c;这和异或的结果是一样的。对异或而言&＃xff0c;0和0、1和1异或的结果是0&＃xff0c;而0和1、1和0的异或结果是1。接着考虑第二步进位&＃xff0c;对0加0、0加1、1加0而言&＃xff0c;都不会产生进位&＃xff0c;只有1加1时&＃xff0c;会向前产生一个进位。此时我们可以想象成是两个数先做位与运算&＃xff0c;然后再向左移动一位。只有两个数都是1的时候&＃xff0c;位与得到的结果是1&＃xff0c;其余都是0。第三步把前两个步骤的结果相加。如果我们定义一个函数AddWithoutArithmetic&＃xff0c;第三步就相当于输入前两步骤的结果来递归调用自己。

有了这些分析之后&＃xff0c;就不难写出如下的代码了&＃xff1a;

int AddWithoutArithmetic(int num1, int num2)
{if(num2 &＃61;&＃61; 0)return num1;int sum &＃61; num1 ^ num2; //异或运算int carry &＃61; (num1 & num2) <<1; //对0加0、0加1、1加0而言&＃xff0c;都不会产生进位&＃xff0c;只有1加1时&＃xff0c;会向前产生一个进位。因此两个数先做位与运算&＃xff0c;然后再向左移动一位。return AddWithoutArithmetic(sum, carry);
}

转载自zhedahht.blog.163.com