0371. Sum of Two Integers¶
题目信息¶
- 题号:
0371
- 难度:
Medium
- 主题:
有符号整数、算术和、运算符限制、位级语义
- 原题:
- 重点:
返回两个整数的算术和、实现中不能使用
+或-、输入可以为负数或零
题目重述¶
给定两个整数 a 和 b,返回它们的算术和。实现过程中不能使用加法运算符 + 或减法运算符 -。
a 和 b 均位于 [-1000, 1000],结果能够由常见的 32 位有符号整数表示。输入可能同号、异号或包含零;题目只要求返回最终整数结果。
自建示例¶
正负数相加:
输入:a = 12,b = -5
输出:7
解释:两个整数的算术和为 7,虽然实现不能直接使用加减运算符。
两个负数相加:
输入:a = -8,b = -9
输出:-17
解释:结果仍按有符号整数语义计算,负号不代表可以忽略进位或符号位。
异或保留无进位结果,与运算生成进位¶
对两个二进制数,a ^ b 在每一位上给出不考虑进位的和;a & b 找出同时为 1 的位,左移一位后就是需要加到更高位的进位。先把 a、b 更新为“无进位和”和“进位”,再重复同样过程,直到没有进位。
把整数视为固定宽度的二进制补码时,异或和移位对负数同样成立;使用无符号临时变量进行左移,避免对有符号位移的实现细节产生依赖。
C++ 实现¶
class Solution {
public:
int getSum(int a, int b) {
unsigned int first = static_cast<unsigned int>(a);
unsigned int second = static_cast<unsigned int>(b);
while (second != 0) {
unsigned int carry = (first & second) << 1;
first ^= second;
second = carry;
}
return static_cast<int>(first);
}
};
代码分析¶
每轮都把至少一位进位向更高位移动,固定宽度整数下有限轮后进位消失;此时 first 就是完整补码和。实现正文没有使用 + 或 -,时间复杂度为 O(w),其中 w 是整数位宽,额外空间为 O(1)。