不用加减乘除做加法

## 1 题目

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

**示例:**

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

**提示：**

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

## 2 问题分析

1. **设两数字的二进制形式 $a, b$**，**其求和 $s = a + b$**，$a_i$**代表 $a$ 的二进制第 $i$ 位**，则**分为以下四种情况**：

| $a_i$ | $b_i$ | 无进位和$n_i$ | 进位$c_{i + 1}$ |
   | ------- | ------- | --------------- | ----------------- |
   | 0       | 0       | 0               | 0                 |
   | 0       | 1       | 1               | 0                 |
   | 1       | 0       | 1               | 0                 |
   | 1       | 1       | 0               | 1                 |
2. 观察发现，**无进位和与异或运算规律相同**，**进位和与运算规律相同**（**并需左移一位**），因此，**无进位和 $n$ 与进位 $c$ 的计算公式如下**：

$$
   \left\{\begin{array}{l}n=a\oplus b\;\;\;\;\;\;\;\;\mathrm{非进位和}：\mathrm{异或运算}\\c=a\&b<<1\;\;\mathrm{进位}：\mathrm{与运算}+\mathrm{左移一位}\end{array}\right.
   $$
3. 此时，**两数字之和 $s$ 即可转化为**

$$
   s = a + b = 非进位和 + 进位 = n + c
   $$
4. **循环求 $n$ 和 $c$**，**直至进位 $c = 0$**，**此时 $s = n$**，**返回 $n$ 即可**。

![Picture1.png](/media/202202/2022-02-12_1942570.5515300761805315.png)

## 3 参考代码

```java
/**
 * 剑指 Offer 65. 不用加减乘除做加法
 * @param a 第一个整数
 * @param b 第二个整数
 * @return  两个整数之和
 */
public int add(int a, int b) {
    int n = -1, c = -1;
    while (n != 0) {
        //  当进位为 0 时跳出
        //  进位
        n = (a & b) << 1;
        //  非进位和
        c = a ^ b;
        //  令 a 等于非进位和
        a = c;
        //  令 b 等于进位
        b = n;
    }
    //  返回非进位和
    return a;
}
```

## 参考文献

1. [剑指 Offer 65. 不用加减乘除做加法](https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof)。
2. [ 面试题 65. 不用加减乘除做加法（位运算，清晰图解）](https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7)。