# 0371. 两整数之和

### 题目地址(371. 两整数之和)

<https://leetcode-cn.com/problems/sum-of-two-integers/>

### 题目描述

```
不使用运算符 + 和 - ​​​​​​​，计算两整数 ​​​​​​​a 、b ​​​​​​​之和。

示例 1:

输入: a = 1, b = 2
输出: 3
示例 2:

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

```

### 前置知识

* [位运算](/leetcode-solution/thinkings/bit.md)

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

不能使用加减法来求加法。 我们只能朝着位元算的角度来思考了。

由于`异或`是`相同则位0，不同则位1`，因此我们可以把异或看成是一种不进位的加减法。

![371.sum-of-two-integers-1](https://p.ipic.vip/ew4ycn.jpg)

由于`与`是`全部位1则位1，否则位0`，因此我们可以求与之后左移一位来表示进位。

![371.sum-of-two-integers-2](https://p.ipic.vip/oaiu0w.jpg)

然后我们对上述两个元算结果递归求解即可。 递归的结束条件就是其中一个为 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 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/vbjbs5.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/371.sum-of-two-integers.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.