0%

[Leetcode]371. Sum of Two Integers(C++)

题目描述

题目链接:371. Sum of Two Integers

Given two integers a and b, return the sum of the two integers without using the operators + and -.

例子

例子 1

Input:a = 1, b = 2
Output:3

例子 2

Input:a = 2, b = 3
Output:5

Constraints

  • -1000 <= a, b <= 1000

解题思路

题目要求很简单,在不使用加减操作的情况下求两数之和。因此只能考虑使用位操作来实现,这里参考这篇博客的思路:[LeetCode] 371. Sum of Two Integers 两数之和。方法是将求和转换为两部分:不考虑进位直接相加,以及只考虑进位结果。下面结合几个例子来说明:

  • 10 + 2 = 12
    • 方便起见只写出后 4 位以及符号位:
    • 8: 0x1010 符号位 0
    • 2: 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,符号位:0
    • 0x0100 & 0x0100 = 0x0100 -> 0x1000,符号位:1 -> 0
    • 第三轮:
    • 0x0000 ^ 0x1000 = 0x1000,符号位:0
    • 0x0000 & 0x1000 = 0x0000,符号位:0
    • 结束,0x1000 = 8 为最后结果
  • -10 + 2 = -8
    • -10: 0x0110,符号为:1
    • 2: 0x0010,符号为:0
    • 0x0110 ^ 0x0010 = 0x0100,符号位:1
    • 0x0110 & 0x0010 = 0x0010 -> 0x0100,符号位:0
    • 0x0100 ^ 0x0100 = 0x0000,符号位:1
    • 0x0100 & 0x0100 = 0x0100 -> 0x1000,符号位:0
    • 0x0000 ^ 0x1000 = 0x1000,符号位:1
    • 0x0000 & 0x1000 = 0x0000,符号位:0
    • 结束:0x1000,转反码:0x0111,转原码:0x1000,符号位不变,结果为:-8

实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
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