LeetCode 题解工作台
两整数之和
给你两个整数 a 和 b ， 不使用 运算符 + 和 - ，计算并返回两整数之和。 示例 1： 输入： a = 1, b = 2 输出： 3 示例 2： 输入： a = 2, b = 3 输出： 5 提示： -1000
2
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数学·位运算
答案摘要
两数字的二进制形式 a,b ，求和 s = a + b ，a(i)、b(i) 分别表示 a、b 的第 i 个二进制位。一共有 4 种情况： | a(i) | b(i) | 不进位的和 | 进位 |
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·位运算 题型思路
题目描述
给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。
示例 1：
输入：a = 1, b = 2 输出：3
示例 2：
输入：a = 2, b = 3 输出：5
提示：
-1000 <= a, b <= 1000
解题思路
方法一：位运算
两数字的二进制形式 a,b ，求和 s = a + b ，a(i)、b(i) 分别表示 a、b 的第 i 个二进制位。一共有 4 种情况：
| a(i) | b(i) | 不进位的和 | 进位 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
观察可以发现，“不进位的和”与“异或运算”有相同规律，而进位则与“与”运算规律相同，并且需要左移一位。
- 对两数进行按位
^异或运算，得到不进位的和； - 对两数进行按位
&与运算，然后左移一位，得到进位； - 问题转换为求：“不进位的数 + 进位” 之和；
- 循环，直至进位为 0，返回不进位的数即可（也可以用递归实现）。
时间复杂度 。
class Solution:
def getSum(self, a: int, b: int) -> int:
a, b = a & 0xFFFFFFFF, b & 0xFFFFFFFF
while b:
carry = ((a & b) << 1) & 0xFFFFFFFF
a, b = a ^ b, carry
return a if a < 0x80000000 else ~(a ^ 0xFFFFFFFF)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a clear understanding of bitwise operations and how they apply to addition.
- question_mark
Evaluate if the candidate can explain the iterative nature of the algorithm and its relation to the binary representation of integers.
- question_mark
Check if the candidate can identify the edge cases, such as when no carry is present or when both integers are zero.
常见陷阱
外企场景- error
Not correctly handling the case when there is no carry, leading to infinite loops or incorrect results.
- error
Failing to explain the shift operation and why it is necessary to propagate the carry bit.
- error
Overcomplicating the solution or using additional data structures when bitwise operations alone suffice.
进阶变体
外企场景- arrow_right_alt
The problem can be extended to work with multiple integers, where you need to find the sum of an arbitrary number of integers.
- arrow_right_alt
An alternative version could ask you to perform subtraction using bitwise operations, leading to a similar but inverted process.
- arrow_right_alt
You could be asked to find the difference between two integers without using the subtraction operator, relying on bitwise operations.