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前置知识
公司
阿里
腾讯
百度
字节
思路
不能使用加减法来求加法。 我们只能朝着位元算的角度来思考了。
由于异或是相同则位0，不同则位1，因此我们可以把异或看成是一种不进位的加减法。
由于与是全部位1则位1，否则位0，因此我们可以求与之后左移一位来表示进位。
然后我们对上述两个元算结果递归求解即可。 递归的结束条件就是其中一个为 0，我们直接返回另一个。
关键点解析
位运算
异或是一种不进位的加减法
求与之后左移一位来可以表示进位
代码
代码支持：JS，C++，Java，PythonJavascript Code:
/* * @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:
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整数类型为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 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最后更新于
这有帮助吗？