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.

不让用加法和减法，一看就是位运算的题目。

  1. a ^ b相当于没有进位的加法。因为(1 ^ 1 = 0, 0 ^ 0 = 0, 1 ^ 0 = 1)
  2. a & b相当于获得当前位的进位。因为(1 & 1 = 1, 0 & 0 = 0, 1 & 0 = 0)

所以 a + b = a ^ b + (a & b) << 1, 我们可以反复做这个运算, 直到a & b == 0为止

代码如下:

1
2
3
4
5
6
7
8
9
10
public int getSum(int a, int b) {
    while (b != 0) {
        int sum = a ^ b;
        int carry = (a & b) << 1;
        a = sum;
        b = carry;
    }
    return a;
}

当然还可以写成递归的形式

1
2
3
4
5
6
7
8
9
10
11
public int getSum(int a, int b) {
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    int sum = a ^ b;
    int carry = (a & b) << 1;
    return getSum(sum, carry);
}