算法1

(全加器)

不能使用加减乘除，那么考虑使用位运算。最直接的是想到用全加器实现，即对于两个数字的每一位以及上一位的进位Cin，进行异或^操作得到该位的输出值S，进行与&操作得到进位Cout，再把Cout传递到下一位作为下一位的Cin。

时间复杂度分析：由于num1和num2都是int型，因此一共32位，对32位依次进行操作即可。

C++ 代码

class Solution {
public:
    int add(int num1, int num2){
        int res = 0;
        int Cin = 0;
        int tmp = 1;
        for(int i = 0;i<32;i++){
            int a = num1 & tmp;//取得num1和num2的第i位的值
            int b = num2 & tmp;
            int S = (a^b)^Cin;//异或得到第i位的输出值
            int Cout = (a&b)|(a&Cin)|(b&Cin);//与操作得到进位
            Cin = Cout << 1;//传递到下一位的进位输入
            tmp <<= 1;
            res += S;//将第i位的输出值S加到res中
        }
        return res;
    }
};

算法2

很容易想到通过位运算来解决问题。

以5+17=22为例，参考十进制加法：1、只做各位相加不进位运算，即得到12,；2、做进位运算，即得到10,；3、把前面两个结果先相加，即得到22；

同样二进制加法也一样：

1、两个整数做异或^，得到各位相加不进位的运算结果；

2、两个整数做与&，然后再左移一位，即得到进位的运算结果；

3、将上面两个结果相加，即重复步骤1,2，直至进位的运算结果为0；

时间复杂度分析：$O(logN)$

C++ 代码

class Solution {
public:
    int add(int num1, int num2){
        while(num2!=0){
            int sum = num1 ^ num2;//不进位的加法
            int carry = (num1 & num2)<<1;//进位
            num1 = sum;
            num2 = carry;
        }
        return num1;
    }
};