65.不用加减乘除做加法.md

65.不使用加减乘除实现加法

题目描述

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

示例1

输入

1,2

返回值

3

思路 & 解答

这道题不让使用加减乘除，那么我们只能考虑其他的方向，比如位运算， 位运算可以巧妙的实现加和的操作。

首先让我们来了解一下位运算，

操作数1	操作数2	&运算结果	|运算结果	^运算
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

而如果两个数相加，肯定是两个数的二进制相加，再来说说补码的概念，计算机存储的时候，存储的是补码。

• 正数的原码=反码=补码
• 负数的补码=反码+1

假设现在想要计算a和b的和，那么a的二进制表示的第i位，假设为a(i),同样b的是b(i)。

二进制的每一位相加，无非两种结果，一种是进位，一种是没有进位。

a(i)	b(i)	没有进位的结果	进位
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

从上面的结果可以看出，a+b的每一位相加，如果不进位的话，其结果是异或操作的值，那么如果是有进位呢？

可以发现无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）

而每一位的值，都等于无进位的结果+进位结果（移动一位）的结果。 我们可以先用nums1&nums求解出每个都是1的位，也就是求解出进位，每次进位向左边移动一位，接着求解num1^num2，也就是两个数不进位相加的结果，赋值给num1，进位的结果赋值给nums2；循环计算，直到进位为0；

Java实现如下：

public class Solution {
    public int Add(int num1,int num2) {
      while (num2 != 0) {
            int c = (num1 & num2) << 1;
            num1 = num1^num2;
            num2 = c;
        }
        return num1;
    }
}

C++ 实现如下：

public class Solution {
    int Add(int num1,int num2) {
      while (num2 != 0) {
            int c = (num1 & num2) << 1;
            num1 = num1^num2;
            num2 = c;
        }
        return num1;
    }
}

时间复杂度为O(n)，遍历完所有的进位即可。