题目链接：AcWing 85.不用加减乘除做加法

计算机底层加法的实现原理 — 全加器！

一、题解

要求不使用加减乘除实现加法！这样的话，必然就是计算机底层实现加法的原理了！即全加器的实现！

所谓全加器：就是将一个数加另一个数转换为不进位加法与加法的和！

过程如下：

  1. 先通过异或运算得到不进位加法的结果
  2. 再通过与运算得到进位加法的进的位，由于进位是向左边的数进位，因此将结果左移一位即可
  3. 二者相加即为最终结果！

一个问题，上一步要用到加法，题目要求不能使用加法，如何处理？

我们可以将得到的两个结果通过迭代的方式再次进行一次异或和与运算，直到进位结果为0为止！得到的就是最终答案**！**

那么，如何确定该循环一定会结束？

我们会发现每次进行进位运算时，都会左移1，即末尾会至少多个0，每次迭代多一个0，那么最多迭代32次，必然该数为0，退出循环！

时间复杂度：O(1)

空间复杂度：O(1)

二、AC代码

参考如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int add(int num1, int num2){
        while(num2){
            int sum = num1 ^ num2;
            int carry = (num1 & num2) << 1;
            num1 = sum, num2 = carry;
        }
        return num1;
    }
};