[Golang]力扣Leetcode—中级算法—其他—两整数之和（位运算）

题目：给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。

链接： 力扣Leetcode—中级算法—其他—两整数之和.

示例 1：

输入：a = 1, b = 2
输出：3

示例 2：

输入：a = 2, b = 3
输出：5

标签：位运算、数学

思路：题目要求了不能使用运算符 + 和 - ，于是，我们使用位运算来处理这个问题。

位运算中的两数加法，也就下面这四种：

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 (进位)
1
2
3
4

我们来看一个例子：

a = 5 = 0101
b = 4 = 0100
1
2

a ^ b 如下：（异或：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。）

0 1 0 1
0 1 0 0
-------
0 0 0 1
1
2
3
4

a ^ b 得到了一个 无进位加法 结果，如果要得到 a + b 的最终值，我们还要找到 进位 的数，把这二者相加。在位运算中，我们可以使用 与 操作获得进位：

a = 5 = 0101
b = 4 = 0100
1
2

a & b 如下：（与：两位同时为“1”，结果才为“1”，否则为0）

0 1 0 1
0 1 0 0
-------
0 1 0 0
1
2
3
4

由计算结果可见，0100 并不是我们想要的进位，1 + 1 所获得的进位应该要放置在它的更高位，即左侧位上，因此我们还要把 0100 左移一位，才是我们所要的进位结果。

那么问题就容易了，总结一下：

a + b 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)

• 无进位加法使用异或运算 (^) 计算得出
• 进位结果使用与运算 (&) 和移位运算 (<<) 计算得出
• 循环此过程，直到进位为 0

全部Go代码如下：

package main

import "fmt"

func getSum(a int, b int) int {
	//按位取异或
	result := a ^ b
	//判断是否需要进位
	forward := (a & b) << 1
	if forward != 0 {
		//如有进位，则将二进制数左移一位，进行递归
		return getSum(result, forward)
	}
	return result
}

func main() {
	fmt.Println(getSum(2, 3))
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

提交截图：