[刷题]剑指offer之不用加减乘除做加法

题目

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

思路

虽然一看就知道是使用位运算做这个题目，但还是没做出来。

先理解一下10进制是如何做加法的。例如5+7=12，分为3步。

1. 先不考虑进位值，5+7得到2.
2. 再计算进位值，个位上5+7的进位为1，所以进位为1*10=10 (要乘以10是因为个位上进一相当于加10).
3. 重复1，2，直到没有进位制产生，就结束了。例如本题就是再次计算2+10，不考虑进位为12，计算进位得到0，所以最终结果为32.

对于10进制，还是用到了加法和乘法运算。

对于2进制的计算也是一样的，由于二进制的特殊，还可以用位运算替代加法运算和乘法运算。

按位异或：1^1=0 0^0=0 1^0=1 0^1=1

按位与 ：1&1=1 0&0=0 1&0=0 0&1=0

所以按位异或等价于不考虑进位的加法，按位与左移1位表示进位值。

同样考虑5+7，注：5=101，7=111，

1. 先不考虑进位值，101^111=010
2. 计算进位值，101&111=101，需要再左移一位，得到1010
3. 重复1，2
   1. 先不考虑进位值,0010^1010=1000
   2. 计算进位值，0010&1010=0010，再左移一位，得到00100
   3. 重复1，2
      1. 先不考虑进位值,01000^00100=01100
      2. 计算进位值，01000&00100=0，左移之后还是0
      3. 因为进位值为0，所以计算可以终止，最终结果为01100，即12

代码

class Solution {
public:
    int Add(int num1, int num2)
    {
        while(num2 != 0){ //没有进位的时候可以停止迭代
            int temp = num1 ^ num2; //不考虑进位的加法
            num2 = (num1 & num2) << 1; //进位值储存在num2中
            num1 = temp;//将不考虑进位的加法储存在num1中，下次再次计算num1+num2
        }
        return num1;
    }
};

总结

• 加法运算可以拆解成不考虑进位的加法和只计算进位值两部分

我的segmentfault链接