# 0371. 两整数之和
### 题目地址(371. 两整数之和)
### 题目描述
```
不使用运算符 + 和 - ，计算两整数 a 、b 之和。
示例 1:
输入: a = 1, b = 2
输出: 3
示例 2:
输入: a = -2, b = 3
输出: 1
```
### 前置知识
* [位运算](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/bit)
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 思路
不能使用加减法来求加法。 我们只能朝着位元算的角度来思考了。
由于`异或`是`相同则位0，不同则位1`，因此我们可以把异或看成是一种不进位的加减法。
由于`与`是`全部位1则位1，否则位0`，因此我们可以求与之后左移一位来表示进位。
然后我们对上述两个元算结果递归求解即可。 递归的结束条件就是其中一个为 0，我们直接返回另一个。
### 关键点解析
* 位运算
* 异或是一种不进位的加减法
* 求与之后左移一位来可以表示进位
### 代码
代码支持：JS，C++，Java，Python\
Javascript Code:
```js
/*
* @lc app=leetcode id=371 lang=javascript
*
* [371] Sum of Two Integers
*/
/**
* @param {number} a
* @param {number} b
* @return {number}
*/
var getSum = function (a, b) {
if (a === 0) return b;
if (b === 0) return a;
return getSum(a ^ b, (a & b) << 1);
};
```
C++ Code:
```
class Solution {
public:
int getSum(int a, int b) {
if(a==0) return b;
if(b==0) return a;
while(b!=0)
{
// 防止 AddressSanitizer 对有符号左移的溢出保护处理
auto carry = ((unsigned int ) (a & b))<<1;
// 计算无进位的结果
a = a^b;
//将存在进位的位置置1
b =carry;
}
return a;
}
};
```
Java Code:
```java
class Solution {
public int getSum(int a, int b) {
if(a==0) return b;
if(b==0) return a;
while(b!=0)
{
int carry = a&b;
// 计算无进位的结果
a = a^b;
//将存在进位的位置置1
b =carry<<1;
}
return a;
}
}
```
Python Code:
```python
# python整数类型为Unifying Long Integers, 即无限长整数类型.
# 模拟 32bit 有符号整型加法
class Solution:
def getSum(self, a: int, b: int) -> int:
a &= 0xFFFFFFFF
b &= 0xFFFFFFFF
while b:
carry = a & b
a ^= b
b = ((carry) << 1) & 0xFFFFFFFF
# print((a, b))
return a if a < 0x80000000 else ~(a^0xFFFFFFFF)
```
**复杂度分析**
* 时间复杂度：$O(1)$
* 空间复杂度：$O(1)$
> 由于题目数据规模不会变化，因此其实复杂度分析是没有意义的。
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
