不用加减乘除做加法

题目

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2

*提示：

• a, b 均可能是负数或 0
• 结果不会溢出 32 位整数

思路分析

分解

对于一个二进制的数a和b，任何一个位置上的二进制位位a(i) 和b(i)，那么对于这个位置上的加法可以有如下的表示：其中c(i)表示进位：

通过上面的表格其实可以看出，对于任何一位上的和的计算都是：两位之和再加上进位，对于表达式可以表示如下：
res = a+b = n + c;
其中n就是a和b的每一位都进行异或：n = a^b; c位每一位与并进行左移一位；这样对于两个数的和就可以表示为不停的看看是否存在进位，每次异或结束以后都要发现是否存在下一个进位；

代码实现

class Solution {
    public int add(int a, int b) {
        while(b !=0){
            int c = (a & b) << 1;
            a = a^b;
            b = c;
        }
        return a;
    }
}