剑指 Offer 65. 不用加减乘除做加法

位运算实现加法主要是处理好进位问题

我们知道 , 在计算机中 , 任何数据都是二进制的 , 数字更不例外

我们在十进制算两数的加法时 , 主要的步骤就是先算出不考虑进位时的和 sum

然后再将进的位加上即可

例如 :

---

此步骤在二进制中同样有效

那么两个数不考虑进位可以通过 ^ (异或) 来实现

• 相同为 0 , 不同为 1 , 计算并保留不需要进位的位置 , 需要进位的位置置换为 0

只考虑进位可以通过先 & (与) , 然后左移一位实现

• 只有两数同位置都为 1 , 结果为 1 , 表示该位置和为 2 ,要向前进 1 , 故左移一位

那么 a 为被加数 , b 为加数

现将 a , b 算出 sum 和 carry

之后可以把 sum 看成被加数 , carry 看成加数

循环计算 , 直到 carry 进位/被加数为 0 为止

---

Java 代码

public int add(int a, int b) {
    int sum = a ^ b;
    int carry = (a & b) << 1;
    while (carry != 0) {
        int i = sum;
        int j = carry;
        sum = i ^ j;
        carry = (i & j) << 1;
    }
    return sum;
}