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

1. 题目概览

点此直达题目

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

示例:

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

  提示：

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

2. 解题思路

2.1 方法一：位运算模拟全加器

与、或、非、异或真值表：

A	B	&	|	~A	^
0	0	0	0	1	0
0	1	0	1	1	1
1	0	0	1	0	1
1	1	1	1	0	0

1位二进制加法情况：

A	B	进位	A+B
0	0	00	0
0	1	00	1
1	0	00	1
1	1	10	0

2位二进制加法情况：

A	B	进位	A+B
00	00	000	00
00	01	000	01
00	10	000	10
00	11	000	11
01	01	000	10
01	10	000	11
01	11	100	00
10	10	100	00
10	11	100	01
11	11	100	10

我们发现，A+B=A^B，进位=A&B<<1，且最终的和为A^B+(A&B<<1)

由于不允许出现四则运算符号，我们的公式中的+号难以实现。但我们注意到，如果进位为0，那么A^B就是最终答案。因此，A&B << 1 这个进位就成了下一次加法的参数，如果他刚好进位为0，我们就得到了最终答案。

class Solution {
    public int add(int a, int b) {
        int sum = a;
        int next = b;
        // a + 0 = a，此时结束即可
        while(next != 0) {
            // & 获取进位
            int c = (sum & next) << 1;
            // ^ 可以将两个数相加，但会丢失进位
            sum = sum ^ next;
            // 由于丢失了进位，所以要加上，但不能使用+号，所以进行下一轮加法
            next = c;
        }
        return sum;
    }
}