Leetcode——两整数之和

1. 两整数之和

（1）位运算

对于二进制的加法运算，若不考虑进位，与异或运算类似

• 1+1=0
• 1+0=1
• 0+1=1
• 0+0=0

再来考虑进位，不难发现，此方法与异或运算&类似，所以加法可用异或来实现，然后考虑进位

• 0+0 进位为 0
• 1+0 进位为 1
• 0+1 进位为 0
• 1+1 进位为 1

加法运算可以这样实现：

• 异或替代不进位加法
• 如果进位不为0, 说明有进位 , 结果 = 异或的结果 + 进位
• 在异或前收集进位, 异或后判断是否要加进位

先来看一个例子 7 + 1的过程：

【输入】a= 7(111) b= 1(001)
【执行】int carry = (a & b) << 1
【结果】carry = 2(010)

【执行】a = a ^ b;
【结果】a = 6(110)

【执行】b = carry;
【结果】b = 2(10)

【执行】while (b != 0) 从头开始
【输入】a= 6(110) b= 2(10)

【执行】int carry = (a & b) << 1
【结果】carry = 4(100)

【执行】a = a ^ b;
【结果】a = 4(100)

【执行】b = carry;
【结果】b = 4(100)

【执行】while (b != 0) 从头开始
【输入】a= 4(100) b= 4(100)

【执行】int carry = (a & b) << 1
【结果】carry = 8(1000)

【执行】a = a ^ b;
【结果】a = 0(0)

【执行】b = carry;
【结果】b = 8(1000)

【执行】while (b != 0) 从头开始
【输入】a= 0(0) b= 8(1000)

【执行】int carry = (a & b) << 1
【结果】carry = 0(0)

【执行】a = a ^ b;
【结果】a = 8(1000)

【执行】b = carry;
【结果】b = 0(0)

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

看看代码，逐位相加：

class Solution {
 	public int getSum(int a, int b) {
		do {
			int carry = (a & b) << 1;
			a = a ^ b;
			b = carry;
		} while (b != 0);
		return a;
	}
}

1
2
3
4
5
6
7
8
9
10
11

（2）递归实现

思路其实一致：

• 先不考虑进位，按位计算各位累加（用异或实现），得到值a；
• 然后在考虑进位，并将进位的值左移，得值b，若b为0，则a就是加法运算的结果，若b不为0，则a+b即得结果（递归调用该函数

class Solution {
 	public int getSum(int a, int b) {
		if (b == 0)
			return a;
		//先不考虑进位，按位计算各位累加（用异或实现），得到值a；
		int sum = a ^ b;

		//然后在考虑进位，并将进位的值左移，得值b，若b为0，则a就是加法运算的结果，若b不为0，则a+b即得结果（递归调用该函数	
		int carry = (a & b) << 1;	
		return getSum(sum, carry);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12