371. Sum of Two Integers

O(32) time
把两个数相加的结果拆成两部分 一部分是每个bit的无进位和 一部分是进位 不考虑进位的话每一bit的和就是异或的结果 每一个进位就是两个数相与再左移一位即可
必须用unsigned因为runtime error: left shift of negative value -2147483648，对INT_MIN左移位。不能对负数进行左移，就是说最高位符号位必须要为0，才能左移
因为左移以后要补0 所以最多32个iteration

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

class Solution {
public:
    int getSum(int a, int b) {
        int res = 0;
        int c = 0;
        for (int i = 0; i < 32 && (a || b || c); ++i, a >>= 1, b >>= 1) {
            int a_bit = (a & 1);
            int b_bit = (b & 1);
            int sum_bit = a_bit ^ b_bit ^ c;
            c = (a_bit & b_bit) | (b_bit & c) | (a_bit & c);
            res |= (sum_bit << i);
        }
        return res;
    }
};