面试题65:不用加减乘除做加法

题目

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

解题思路

• 采用位运算

1. 不考虑进位对每一位相加。即0加0、1加1的结果都是0,0加1、1加0的结果都是1。这和异或的结果一样。
2. 考虑第二步进位，对0加0、0加1、1加0而言都不会产生进位，只有1加1时，会向前产生一个进位。可以想象成两个数先做位与运算，然后再向左移动一位。
3. 把前两步结果相加，即重复前两步操作，直到不产生进位为止。

• 位运算的相关操作
  ^异或操作，首先把十进制转化为二进制，然后按照两个相同的数会变成0，反之是1，例如：1&1=0，1&0=1，0&0=0，0&1=1的原则进行操作
  &与操作，首先把十进制转化为二进制，然后按照只有2个都为1，那么结果是1，否则为0的原则进行操作。例如：1&1=1，1&0=0，0&0=0，0&1=0
  <<左移运算符，向左位移，就是把开头两位数去掉，尾数加位数00
  >> ：向右位移，就是把尾数去掉位数，例如：153 >> 2，153的二进制是：10011001，屁股后面去掉 2 位 100110。
  (注意:电脑是64位的，所以按照左右移操作符运算时，不会去掉头尾的位数)

代码

class Solution{
  public:
    int Add(int num1,int num2)
    {
        int sum,carry;
        do{
            sum = num1 ^ num2;
            
            carry = (num1 & num2) << 1;
            
            num1 = sum;
            num2 = carry;
        }
        while(num2 != 0);
        return num1;
    }
};

完整代码见GitHub