371. Sum of Two Integers

题目描述：不用+或 - 实现两个 int 数相加

核心思想

不带进位的相加可以用位间的异或 ^ 表示，进位分为两种情况，第一是两位都为1，另一种情况是两位分别为0和1然后进位为1的时候才向前进位，向前用位移操作表示

int getSum(int a, int b) {
    int sum=0,carry=0;
    for(unsigned mask=1;mask!=0;mask<<=1) {
        sum |= (a^b^carry) & mask;
        carry=((a&b) | (a^b)&carry)<<1;
    }
    return sum;
}

递归解法

若a和b为两个二进制数那么则有 a+b = a^b + (a&b)<<1，如果b为0，那么和就为另一个数

int getSum(int a, int b) {
    if (b==0) return a;
    int sum=a^b;
    int carry=(a&b)<<1;
    return getSum(sum, carry);
}

收获

位运算与基础运算之间的联系

#位运算

37. Sudoku Solver 数独解题器 413. Arithmetic Slices 算术切片