题解 | #不用加减乘除做加法#

题解一:自增
主体思路：循环其中一个值，每次自减1，让另外一个值自增
复杂度分析：
时间复杂度:O(n),循环了n次；
空间复杂度:O(1)。
实现如下:

class Solution {
public:
    int Add(int num1, int num2) {
        //通过循环来保证两数相加;
        if(num1>0){//当num1为正数，
            while(num1--!=0)//自减至0
                num2++;//自增；
        }
        else if(num1<0){//当num1为负数
            while(num1++!=0)//自增至0
                num2--;//自减；
        }
        return num2;
    }
};

题解二：采用位运算
主体思路：
面对本题，一般思路
1、在计算机内部的操作都是由门电路实现，加法也一定由位运算实现；
2、不确定使用何种位运算情况，可以进行打表找规律（如下）；

A(i)	B(i)	求和	进位
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

如上图所示，
(1) 当前位的和值等于 A(i)^B(i)
(2) 进位等于 A(i)&B(i),进位需要加在计算位的前一位，所以左移1位，即A(i)&B(i)<<1
所以找出规律 A+B=A^B+(A&B)<<1;
接下来验证规律是否正确

A=8	0	1	0	0
B=11	0	1	1	1
求和(A^B)	0	0	1	1
求进位((A&B)<<1)	1	0	0	0
进位+求和(A+B)	1	0	1	1

8+11=19符合规律

整理完思路，实现代码：
迭代版本：

class Solution {
public:
    int Add(int num1, int num2) {
        //num2可以表示为进位，
        //循环的意义：循环将进位加到num1值上；
        while (num2 != 0) {//进位为0时，跳出循环
        int sum = num1 ^ num2;//非进位求和
        int temp = (unsigned int)(num1&num2) << 1;//计算出进位；
        num1 = sum;//非进位和
        //可以将6、8行写成num1^=num2;
        num2 = temp;//进位；
    }
    return num1;
    }
};

递归版本：

class Solution {
public:
    int Add(int num1, int num2) {
        if(num2 == 0) return num1;//进位为0，结束循环；
        return Add(num1 ^ num2, (unsigned int)(num1 & num2) << 1);
    }
};

Java版本:

public class Solution {
    public int Add(int num1,int num2) {
        while(num2 != 0){//进位为0时，跳出循环
            int sum = num1^num2;//非进位求和
            int temp = (num1&num2)<<1; //计算出进位；
            num1 = sum; //非进位和
            num2 = temp; //进位；
    } 
    return num1;
     } 
}

复杂度分析：
时间复杂度:O(1),因为int类型只有32位，所以最多循环32次；
空间复杂度:O(1)。