LeetCode 371. Sum of Two Integers

題目

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

翻譯

計算a,b的加總，但是不能用+-符號。

思路

不用加減改用位元做運算，其實我也不會阿，而且直接回傳a+b還是會通過的，如果你被這題卡住，建議先跳過。以下單純學習分享。

1. 假設輸入的數字為a=3(0011), b=9(1001)
2. 相加不考慮進位 a = a^b = (0011)^(1001) = 1010
3. 相加只考慮進位 carry =a&b = (0011)^(1001) = 0001 進位值
4. b = 0001 << 1 = 0010 進位
5. 第一輪後 a= 10(1010), b = 2(0010)
6. 相加不考慮進位 a = a^b = (1010)^(0010) = 1000
7. 相加只考慮進位 carry =a&b = (1010)^(0010) = 0010 進位值
8. b = 0001 << 1 = 0100 進位
9. 第二輪後 a= 8(1000), b = 4(0010)
10. 相加不考慮進位 a = a^b = (1000)^(0100) = 1100
11. 相加只考慮進位 carry =a&b = (1010)^(0010) = 0000 進位值
12. b = 0000 << 1 = 0
13. b=0，相加完成， a = 1100 = 12

解題

var getSum = function(a, b) {
    if(b==0){return a};
    if(a==0){return b};  

    while(b!=0){
        var carry = a&b; //進位值

        a = a^b;         //相加

        b = carry << 1;  //進位
    }
    return a;
};