题目

剑指 Offer 65. 不用加减乘除做加法【中等】

题解

不能用加减乘除的题，要考虑位运算。

设两数字的二进制形式a，b，s=a+b，a(i)代表a的二进制的第i位，则分为以下四种情况：

观察发现，无进位和==异或运算 规律，进位==与运算 规律（需左移一位），因此 n 和 c 的计算公式如下：

n = a ⊕ b n=a \oplus b n=a⊕b，非进位和：异或运算
c = a & b < < 1 c=a \& b<<1 c=a&b<<1，进位：与运算+左移一位

由于 和s=非进位和n + 进位和c，即s=a+b=>s=n+c

循环求n和c，直到进位c=0；此时s=n，返回n即可。举例20+17如下：

Q：如果a或者b是负数，怎么办？
A：计算机系统中，数值一律用补码来表示和存储
补码的优势：加法、减法可以统一处理（CPU只有加法器）
因此，以上方法同时适用于正数和负数的加法。

class Solution {
    public int add(int a, int b) {
        while(b!=0){
            int c=(a&b)<<1;//进位c
            a^=b;//非进位和a
            b=c;//进位b
        }
        return a;
    }
}

时间复杂度： O ( 1 ) O(1) O(1)

空间复杂度： O ( 1 ) O(1) O(1)