371. Sum of Two Integers

這種bitwise的操作, 估計hardware的人應該都很熟

相加的話, 可以拆成, 進位與不進位的部分

一般人很難理解是因為從國小的教學就是每次相加就近位

寫一個大家國小的教法

但如果我們把進位的部分保留下來, 234 + 789

會是 913 與 110的相加

110就是我們的carry

那問題來了234 + 789要怎麼變成 913 呢

上面是十進位的部分

二進位的情況下, 不進位的話0+0=0, 0+1=1, 1+0=1, 1+1=0, 用的是xor

進位的話 就是 0+0=0, 0+1=0, 1+0=0, 1+1=1 用的是&

可以簡單用4 + 8 去推看看

然後我們就一路到b為0(carry為0)

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

但上面的code會被測資擋掉, 因為對負數進行左移, 導致超出int的範圍, 忽略的話其實應該是可以讓編譯器去處理的, 但這邊我們就強制他的signed bit為0(最終都要left shift, 所以先把最左邊給清零沒差)

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