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