题目描述
Given two integers
aandb, return the sum of the two integers without using the operators+and-.
例子
例子 1
Input:
a = 1, b = 2Output:3
例子 2
Input:
a = 2, b = 3Output:5
Constraints
-1000 <= a, b <= 1000
解题思路
题目要求很简单，在不使用加减操作的情况下求两数之和。因此只能考虑使用位操作来实现，这里参考这篇博客的思路：[LeetCode] 371. Sum of Two Integers 两数之和。方法是将求和转换为两部分：不考虑进位直接相加，以及只考虑进位结果。下面结合几个例子来说明：
10 + 2 = 12- 方便起见只写出后 4 位以及符号位：
8: 0x1010符号位02: 0x0010符号位0- 直接相加不考虑进位的操作可以看作两数按位异或（都是1或者都是0结果都是0，只有一个是1结果才是1）：
0x1010 ^ 0x0010 = 0x1000，符号位：1 - 只考虑进位的操作可以看作两数的与操作（只有都是1才会进位产生1）:
0x1010 & 0x0010 = 0x0010，求与后还要左移一位才能把进位位放在正确的位上得到：0x0100，符号位：0。 - 接下来对两个结果用同样的方法求和即可：
- （直接相加）异或：
0x1000 ^ 0x0100 = 0x1100，符号位：0 - （进位结果）与：
0x1000 & 0x0100 = 0x0000，符号位：0 - 此时进位结果已经是0，所以无须继续进行，
0x1100 = 12即为结果。
10 - 2 = 8- 这里注意一点，计算机表示数字时为了是正负数相加都能通过以上方式实现，因此负数是用补码表示，以下为例子：
10: 0x1010，符号位：0-2: 0x1110，符号为：1- （直接相加）异或：
0x1010 ^ 0x1110 = 0x0100，符号位：1 - （进位）与：
0x1010 & 0x1110 = 0x1010，符号位：0，左移：0x0100，符号位：1 - 第二轮：
0x0100 ^ 0x0100 = 0x0000，符号位：00x0100 & 0x0100 = 0x0100 -> 0x1000，符号位：1 -> 0- 第三轮：
0x0000 ^ 0x1000 = 0x1000，符号位：00x0000 & 0x1000 = 0x0000，符号位：0- 结束，
0x1000 = 8为最后结果
-10 + 2 = -8-10: 0x0110，符号为：12: 0x0010，符号为：00x0110 ^ 0x0010 = 0x0100，符号位：10x0110 & 0x0010 = 0x0010 -> 0x0100，符号位：00x0100 ^ 0x0100 = 0x0000，符号位：10x0100 & 0x0100 = 0x0100 -> 0x1000，符号位：00x0000 ^ 0x1000 = 0x1000，符号位：10x0000 & 0x1000 = 0x0000，符号位：0- 结束：
0x1000，转反码：0x0111，转原码：0x1000，符号位不变，结果为：-8
实现代码如下：
class Solution {
public:
int getSum(int a, int b) {
while (b != 0) {
int carry = (a & b);
a ^= b;
b = (static_cast<unsigned int>(carry) << 1);
}
return a;
}
};
- 时间复杂度:
O(1) - 空间复杂度:
O(1)
GitHub 代码同步地址： 371.SumOfTwoIntegers.cpp
其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions