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

面试题65. 不用加减乘除做加法

Description

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“”、“/” 四则运算符号。
难度：简单
示例:
输入: a = 1, b = 1
输出: 2
*提示：

• a, b 均可能是负数或 0
  
• 结果不会溢出 32 位整数
  

  Solution：

  采用位运算来替换加操作，在计算机中，数值是以二进制存储的，Java 也不例外，例如 short、int、long 等基本数据类型，底层都是用二进制存储，所以可以以二进制的方式来操作这些基本数据类型。
  设两数字的二进制形式 a, b ，其求和 s = a + b，a(i) 代表 a 的二进制第 i 位，则分为以下四种情况：
  a(i)、b(i)、无进位和 n(i)、进位 c(i+1)

观察发现，无进位和 与 异或 运算规律相同，进位和 与运算 规律相同（并需左移一位）。因此，无进位和 nn 与进位 cc 的计算公式如下；

（和 S）==（非进位和 n ）+（进位 c ）。即可将 s = a + b 转化为：

循环求 n 和 c ，直至进位 c = 0 ；此时 s = n ，返回 n 即可。
下面以 13 和 7 为例：
13 ：1101
7 : 0111

1. 各位置上相加但不进位 n ： 1101 ^ 0111 = 1010 (10)
   
2. 计算进位 c ： （1101 & 0111）<< 1 = 1010 (10)
   
3. 循环 1 、 2 步骤直到进位 c 为 0
   

每次异或相当于把进位加上去。再计算是否产生进位，有进位继续下一轮循环相加。循环每次到不产生进位。

Q：若数字 aa 和 bb 中有负数，则变成了减法，如何处理？A ： 在计算机系统中，数值一律用 补码 来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法 同时适用于正数和负数的加法 。

示例代码

class Solution {
    public int add(int  a, int b) {
        while(b != 0){
            int temp = a ^ b; // 计算不进位。
            b = (a & b) << 1;  // 计算进位
            a = temp;
        }
        return a;
    }
}

执行结果：通过
显示详情
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.3 MB, 在所有 Java 提交中击败了80.02%的用户

参考链接
面试题65. 不用加减乘除做加法（位运算，清晰图解）