LeetCode 371.Sum of Two Integers 位运算实现加法(减法)

1.原题

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.

2.思路

不允许用+、-操作符，那么暂且只能想到位运算来入手。
1.”&”与操作符, 2 (0010) & 7 (0111) => 2 (0010)
“^” XOR(异或) operation, 2 (0010) ^ 7 (0111) => 5 (0101)
2. a+b 不考虑进位的话则是相当于 a xor b的操作。(0001+0011=0010 不考虑进位)
3. 进位则可以看做 (a & b) << 1.
4. 因此模仿a+b的真实操作则是，(a xor b) + ( (a&b)<<1 )，这时候如果( (a&b)<<1 )进位不为0，那么肯定要继续相加，所以可以递归调用，也可以while循环直到进位为0的时候。

3.AC解

public class Solution {
    public int getSum(int a, int b) {
        if(a==0) return b;
        if(b==0) return a;

        int carry = 0;
        while(b!=0){
            carry = a & b; 
            a = a ^ b;  //xor位相加不进位，并赋给a
            b = carry << 1; //计算进位，并赋给b，然后循环 a+b,直到b为0,无进位
        }
        return a;
    }
}

4.优秀Discuss

// Iterative
public int getSum(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;

    while (b != 0) {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }

    return a;
}

// Iterative减法
public int getSubtract(int a, int b) {
    while (b != 0) {
        int borrow = (~a) & b;
        a = a ^ b;
        b = borrow << 1;
    }

    return a;
}

// Recursive
public int getSum(int a, int b) {
    return (b == 0) ? a : getSum(a ^ b, (a & b) << 1);
}

// Recursive
public int getSubtract(int a, int b) {
    return (b == 0) ? a : getSubtract(a ^ b, (~a & b) << 1);
}

// Get negative number
public int negate(int x) {
    return ~x + 1;
}