371. Sum of Two Integers

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

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = -2, b = 3
Output: 1

每個carry的部分要強制讓第一個bit不為1，這樣才能left shift。

// Iteration
int getSum(int a, int b) { // time: O(1); space: O(1)
    while (b) {
        int carry = ((a & b) & 0x7fffffff) << 1;
        a = a ^ b; // the first bit cannot be 1; otherwise, it cannot be left-shifted
        b = carry;
    }
    return a;
}

// Recursion
int getSum(int a, int b) { // time: O(1); space: O(1)
    return b == 0 ? a : getSum(a ^ b, ((a & b) & 0x7fffffff) << 1);
}