【前言】

今天是力扣打卡第15天！

天天做递归做烦了，换换脑子，嘿嘿。

原题： 不用加减乘除做加法

题目描述：

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

示例：

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

题解：

如果是十进制的话，我们如何完成加法计算呢？

比如99 + 111 = ？

第一步：计算进位的数字：

1 + 9 = 10;

10 + 90 = 100;

得到进位结果：110

第二步：个、十、百位 的数字分别相加先不管进位的问题：

个位：9 + 1 = 0

十位：9 + 1 = 0

百位：0 + 1 = 1

得到临时结果：100

第三步：相加得到结果：

100 + 110 = 210

如何用二进制完成以上的步骤呢？

问题1： 二进制的加法利用以上的步骤可以得到正确的结果吗？

12 二进制：1100

15 二进制：1111

第一步：计算进位的数字：

0100 + 0100 = 1000

1000 + 1000= 10000

得到进位结果：11000

第二步：做不进位加法

1100 + 1111 = 0011

得到临时二进制结果：0011

第三步：将第一步和第二步结果相加得到答案

0011 + 11000 = 11011（十进制：27）

就目前来看，是可以的。

问题2：第一步骤不用加法如何得到相同结果？相与并且左移一位

如果相&能得到1 ，那么表示，对应位置上的数字都是1，然后再往左移动一位，就是步骤一 进位得到的结果

(1100 & 1111) << 1 = 11000

问题3：第二步骤不用加法如何得到相同结果？异或（俗称不进位加法）

异或：相同为0，相异为1

1100 ^ 1111 = 0011

问题4：第三步骤不用加法如何得到相同结果？其实这是个套娃

第三步不用加法实现最难，因为第三步是前两步的和，还是个加法；如果不用加法，就只能不断调用前两步的步骤。

但是这里难想的是什么时候停下来呢？

当不再需要进位就代表停止了，即进位的结果是0的时候停止

代码执行：

int add(int a, int b){
    //因为不允许用+号，所以求出异或部分和进位部分依然不能用+号，所以只能循环到没有进位为止   
    while(b){
        //保存进位值，下次循环用
        int c = (a & b) << 1;
        //保存不进位值，下次循环用
        a = a ^ b;
        b = c;
    }
    //如果还有进位，再循环，如果没有，则直接输出没有进位部分即可
    return a;
}

Q ： 若数字 a 和 b 中有负数，则变成了减法，如何处理？

A ： 在计算机系统中，数值一律用 补码 来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法 同时适用于正数和负数的加法

结语

今天是力扣打卡第15天！

我想吐槽一下，这道题在力扣上面显示的是“简单”，但是我硬生生没想出来怎么做，呜呜呜，多亏力扣上面的大佬们，抱拳了。