leetcode 371. 两整数之和（优质解法）

链接：371. 两整数之和

代码：

class Solution {
    public int getSum(int a, int b) {

        while(b!=0){
            int num=a^b;    //无进位值
            int bit=(a&b)<<1;   //进位

            a=num;
            b=bit;
        }

        return a;
    }
}

题解：

? ? ? ? 要计算两个数相加并且不能使用 + - 号，一般就要采用位运算来解决该问题。

? ? ? ? ^ 异或被称为无进位相加，我们计算出异或的值再计算出进位的值即可，如 2 + 3，先计算无进位相加得到的值：?0010?^ 0011= 0001。

? ? ? ? 现在来推算一下如何得到 a，b 相加的进位：

a? ? ? ? ? ? ? ? 0? ? ? ? 1? ? ? ? 0? ? ? ? 1

b? ? ? ? ? ? ? ? 0? ? ? ? 0? ? ? ? 1? ? ? ? 1

进位? ? ? ? ? ?0? ? ? ? 0? ? ? ? 0? ? ? ? 1

? ? ? ? 由上面的推算可以看出，进位 = a & b ,所以 2 + 3 的进位为：0010 & 0011 = 0010，但是进位是加到前一位的，所以实际上此时得到的进位还需要 << 1 得到 0100

? ? ? ? 让无进位相加得到的值和进位相加，便得到了结果，但是这里又涉及到了加法，就要用无进位相加得到的值和进位继续做上述的操作，所以这就是一个循环

? ? ? ? 循环结束的条件就是进位变为 0 ，当进位变为 0 以后，就代表得到了最终的值