题目描述
这是 LeetCode 上的 371. 两整数之和 ，难度为 中等。
Tag : 「位运算」
给你两个整数 a 和 b ，不使用 运算符 + 和 -，计算并返回两整数之和。
示例 1：
输入：a = 1, b = 2 输出：3 复制代码
示例 2：
输入：a = 2, b = 3 输出：5 复制代码
提示：
- -1000 <= a, b <= 1000
位运算
一个朴素的做法是使用「位运算」，利用二进制的「逢二进一」和「int 二进制表示长度为 3232」，我们可以从低位往高位进行处理，处理过程中使用变量 tt 记录进位信息。
然后对两数当前位进行分情况讨论：
- 两个当前位均为 11：此时当前位是什么取决于前一位的进位情况，即有
ans |= (t << i)，同时进位 t = 1t=1； - 两个当前位只有一位是11：此时当前位是什么取决于前一位的进位情况（整理后可统一为
ans |= ((1 ^ t） << i)：
- 前一进位若为 11，结合该位为 11，则有当前位为 00，进位不变 t = 1t=1；
- 前一进位若为 00，结合该位为 11，则有当前位为 11，进位不变 t = 0t=0；
- 两个当前位为 00：此时当前位是什么取决于前一位的进位情况，则有
ans |= (t << i)，同时进位 t = 0t=0。
代码：
class Solution { public int getSum(int a, int b) { int ans = 0; for (int i = 0, t = 0; i < 32; i++) { int u1 = (a >> i) & 1, u2 = (b >> i) & 1; if (u1 == 1 && u2 == 1) { ans |= (t << i); t = 1; } else if (u1 == 1 || u2 == 1) { ans |= ((1 ^ t) << i); } else { ans |= (t << i); t = 0; } } return ans; } } 复制代码
- 时间复杂度：O(C)O(C)，CC 为常数，固定为 3232
- 空间复杂度：O(1)O(1)
递归
在彻底理解「解法一」后，不难发现「解法一」中本质是分别对两数的当前位进行“拆分”求解。
先计算原始的 aa 的和原始 bb 在不考虑进位的情况下的结果，结果为 a ^ b，然后在此基础上，考虑将进位累加进来，累加操作可以递归使用 getSum 来处理。
问题转化为如何求得 aa 和 bb 的进位值。
不难发现，当且仅当 aa 和 bb 的当前位均为 11，该位才存在进位，同时进位回应用到当前位的下一位（左边的一边，高一位），因此最终的进位结果为 (a & b) << 1。
因此，递归调用 getSum(a ^ b, (a & b) << 1) 我们可以得到最终答案。
最后还要考虑，该拆分过程何时结束。
由于在进位结果 (a & b) << 1 中存在左移操作，因此最多执行 3232 次的递归操作之后，该值会变为 00，而 00 与任何值 xx 相加结果均为 xx。
代码：
class Solution { public int getSum(int a, int b) { return b == 0 ? a : getSum(a ^ b, (a & b) << 1); } } 复制代码
- 时间复杂度：令 CC 为常数，固定为 3232，最多执行 CC 次的
(a & b) << 1，递归过程结束。复杂度为 O(C)O(C) - 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.371 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
