LeetCode371 Sum of Two Integers

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

样例

1
Given a = 1 and b = 2, return 3.

思路

在不使用+-的情况下,求a+b。

回顾一下数逻里的加法器

加法器

其中

那么我们只要模拟这个过程就可实现加法运算啦!

a ^ b : 不进位求和

(a & b) << 1 : 把进位通过左移加到高位

递归这一过程,直到没有进位为止。

比如 a = 3, b = 5:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
第一次迭代:
a -> 0000 0000 0000 0011
b -> 0000 0000 0000 0101
a ^ b -> 0000 0000 0000 0110
(a & b) << 1 -> 0000 0000 0000 0010

第二次迭代:
a -> 0000 0000 0000 0110
b -> 0000 0000 0000 0010
a ^ b -> 0000 0000 0000 0100
(a & b) << 1 -> 0000 0000 0000 0100

第三次迭代:
a -> 0000 0000 0000 0100
b -> 0000 0000 0000 0100
a ^ b -> 0000 0000 0000 0000
(a & b) << 1 -> 0000 0000 0000 1000

第四次迭代:
a -> 0000 0000 0000 0000
b -> 0000 0000 0000 1000
a ^ b -> 0000 0000 0000 1000
(a & b) << 1 -> 0000 0000 0000 0000

第五次迭代:
a -> 0000 0000 0000 1000
b -> 0000 0000 0000 0000

此时b为0,返回答案a=8

由于数字在计算机内部以补码形式表示,有 [X+Y]补 = [X]补+[Y]补 ,所以上述思路对于负数也适用。

代码

1
2
3
4
5
6
class Solution {
public:
int getSum(int a, int b) {
return b ? getSum(a ^ b, (a & b) << 1) : a;
}
};
分享到 评论