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

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

输入: a = 1, b = 1
输出: 2

提示：

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

解题思路

学过计算机组成原理的都知道, 加法器的构造原理。

如下是一个1位全加器的示意图

根据以上图示可以知道, 无进位的和为 A和B的异或值；进位为A和B的与值。

下面看一下4位累加器的示意图

对于一个四位加法器来讲, 每一个位的的任务都是求来自当前为的SUM和前一位的CARRY的和。而输出的结果是当前为的SUM, 然后将CARRY给下一位作为输入。

其实在本题也, 就是用了这个原理。通过异或, 我们可以求出每一位的SUM, 但是还不够,我还要加上来自前一位的进位值来进行相加。所以一个加法就拆成了异或和与操作。每次输入都是上一次的异或值和与值, 输出也是异或值和与值, 知道不再产生进位为止。

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