剑指offer-不用加减乘除做加法

本文为剑指 offer 系列第四十五篇。
主要知识点为位运算，思路非常神奇，可以打破我们的思维定势。

题目描述

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

解题思路

当我们计算两个数字之和的时候，实际上一方面我们计算两个数当前位的加法运算，另一方面是计算当前位的进位运算，本题目我们采用同样的思路来对二进制进行计算，当前位的计算用位的异或操作，具体操作为

1^1 = 0; 1^0 = 1; 0^1 = 1; 0^0 = 0;

而进位运算通过位的与运算来进行计算，具体操作为

1&1 = 1; 1&0 = 0; 0&1 = 0; 0&0 = 0;

下面我们举例来进行说明：
比如2+4变成二进制为010和100，
这样直接通过位的异或计算当前位就是110，而进位计算010&100 = 0，
所以最终计算结果的二进制就是110，也就是6；

比如2+6，它们的二进制分别为010和110，
计算当前位为010^110= 100,计算进位010&110=010。
由于是进的位，所以在进行下一步计算的时候，进位结果要左移一位之后再来和之前的计算结果进行计算，
所以当前位运算结果变为100^100 = 000,进位结果变为100&100 = 100，
进位结果继续左移1位得到1000，和原来当前位数字000进行异或计算得到0000^1000=1000，而进位0000&1000 = 0，运算结束。
所以最后结果就是1000也就是8。

解题代码

class Solution {
public:
    int Add(int num1, int num2)
    {
        //return num1+num2;
        int temp = 0;
        while(num2 != 0){
            temp = num1^num2;
            num2 = (num1&num2)<<1;
            num1 = temp;
        }
        return num1;
    }
};

时间复杂度为O(n),空间复杂度为O(1)

以上，本题结束！