【LeetCode】【剑指offer】【不用加减乘除做加法】

​​​​​​​​​​​​​​剑指 Offer 65. 不用加减乘除做加法

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

示例:

输入: a = 1, b = 1
输出: 2
 

提示：

a, b 均可能是负数或 0
结果不会溢出 32 位整数

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题其实官方并没有对加减做检测

class Solution {
public:
    int add(int a, int b) {
        return a+b;
    }
};

 

那么我们符合题目要求的做法应该是什么呢？ 

对于数字7与3相加，我们可以先看7和3的二进制表示

7：111

3：011

10：1010

这里的10中的两个1全部都是由进位造成的。

首先我们将7按位与3，得到011，也就是说初始情况下，其个位和十位都有进位

7&3=011

我们将其左移一位，表示进位之后的数据110

011<<1=110

对于我们的异或运算，我们知道如果对应的二进制位是不同的话就是1，相同的话就是0，这和我们的相加的思路非常像，也就是说0+1=1，而0^1=1，而1+1=10，而1^1=0也就是说使用异或可以保持进位前的结果

7^3=100

上面7^3的结果为100，也就是说我们的个位和十位上的进位没有计算前的结果。但是我们上面7&3<<1得到的110是进位的数据，所以我们再将这两个数按照上面的方法相加即可

这里我们让110按位与100得到100，也就是我们的百位上有一个进位

110&100=100

我们将其左移一位，让其进位进到具体的位置上，也就是1000

100<<1=1000

同样我们再让110异或100，保存这里百位没有进位的结果

110^100=010

然后我们想让我们的进位和没有进位的数据相加，我们再次使用上面的方法，将1000与0010按位与，得到0，也就是没有进位

1000&0001=0

我们在让1000与0001进行异或操作

1000^0010=1010

这里我们也就得到了我们的结果1010（因为没有进位，所以我们没有进位的计算得出的结果就是我们的最终结果），转换成十进制就是10

class Solution {
public:
    int add(int a, int b) {
        while(b)
        {
            //保存进位值
            //注意测试用例中有-1和2相加的，如果是负数的话没办法用移位运算，所以要强制转换成无符号的
            int c=(unsigned int)(a&b)<<1;
            //保存没有进位的结果
            a^=b;
            //如果还有进位，再循环，让b=c形成循环迭代
            b=c;
        }
        return a;
    }
};