LeetCode (Others) Sum of Two Integers

Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

Credits:
Special thanks to @fujiaozhu for adding this problem and creating all test cases.

思路：不用加法实现两数之和。想到了位运算，加法的位运算由两部分构成，一部分是异或，一部分是与+移位。

首先，不考虑进位的话每一位的加法运算规律如下：1+1=0， 0+0=0, 0+1=1, 1+0=1。我们可以观察到，这是一个异或的规律，但是考虑进位的时候，我们需要将同一个位置为1的位置0，并且向高位进1，进位操作只有两个数都为1时成立，所以我们考虑让两个数相与，按位与之后，只有1和1能留下来，也就是我们可以知道这个时候是存在进位的，向高位进1，我们采用左移一位的方法。重复以上步骤，直到没有进位为止，返回计算得到的结果就是两数之和。

代码如下：

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