371. Sum of Two Integers

Posted on Edited on

题目

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

Example:

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

思路

不能用 + 号或者 - 号，那就只能用位操作了。位操作有四种：

& 与操作（AND operation）： 2 (0010) & 7 (0111) => 2 (0010)

| 或操作 （OR operation）： 2 (0010) | 7 (0111) => 7 (0111)

^ 异或操作 （XOR operation）： 2 (0010) ^ 7 (0111) => 5 (0101)

~ 非操作 （NOT operation）： ~2(0010) => -3 (1101) 补码，见文末

其中，最左边一位是符号位，代表正负，比如

1111 代表 -1 （补码）

1110 代表 -2

这题两个位置全为1的地方需要进一位，不全为1的地方直接异或操作就好。于是我们用一个carry来记录进位，每次进位完需要左移一位。

代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//C++
int getSum(int a, int b) {
    if(a==0) {
        return b;
    } 
    if(b==0) {
        return a;
    } 
    while(b!=0) {
        int carry = a & b;
        a = a ^ b;
        b = carry<<1;
    }
    return a;
}

扩展

减法

1
2
3
4
5
6
7
8
9
10
//C++
int getSubtract(int a, int b) {
	while (b != 0) {
		int borrow = (~a) & b;
		a = a ^ b;
		b = borrow << 1;
	}
	
	return a;
}