SZ 博客

忠于理想 忠于技术

0%

二进制加法

发表于 分类于 阅读次数：

起源于这道题:371.两整数之和复习下二进制加法内容几乎照搬位运算详解

题目说不能使用运算符 + 和 -，那么我们就要使用其他方式来替代这两个运算符的功能。

位运算中的加法

我们先来观察下位运算中的两数加法，其实来来回回就只有下面这四种：

1
2
3
4
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0（进位 1）

仔细一看，这可不就是相同位为 0，不同位为 1 的异或运算结果嘛~

异或和与运算操作

我们知道，在位运算操作中，异或的一个重要特性是无进位加法。我们来看一个例子：

1
2
3
4
5
6
7
8
9
10
a = 5 = 0101
b = 4 = 0100

a ^ b 如下：

0 1 0 1

0 1 0 0
-------
0 0 0 1

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

1
2
3
4
5
6
7
8
9
10
a = 5 = 0101
b = 4 = 0100

a & b 如下：

0 1 0 1

0 1 0 0
-------
0 1 0 0

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

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

a + b 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)
无进位加法使用异或运算计算得出
进位结果使用与运算和移位运算计算得出
循环此过程，直到进位为 0

正数与负数相加验证

在计算机中，负数以原码的补码形式表达。
什么叫补码呢？这得从原码，反码说起。

原码：一个正数，按照绝对值大小转换成的二进制数；一个负数按照绝对值大小转换成的二进制数，然后最高位补1，称为原码。

反码：正数的反码与原码相同，负数的反码为对该数的原码除符号位外各位取反。

补码：正数的补码与原码相同，负数的补码为对该数的原码除符号位外各位取反，然后在最后一位加1.

比如 以32位为例

1
2
3
4
5  的原码 00000000 00000000 00000000 00000101
-5 的原码 10000000 00000000 00000000 00000101
-5 的反码 11111111 11111111 11111111 11111010
-5 的补码 11111111 11111111 11111111 11111011

以 -5 + 4 为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-5 = 11111111 11111111 11111111 11111011
 4 = 00000000 00000000 00000000 00000100

-5与4 的进位结果  -5 & 4 << 1 
---------------------------
00000000 00000000 00000000 00000000

-5与4 的无进位结果 -5 ^ 4 
----------------------------
11111111 11111111 11111111 11111111

进位结果为0

无进位结果： 11111111 11111111 11111111 11111111 为补码

转化为源码
10000000 00000000 00000000 00000001
结果为 -1

-4 + 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
30
31
 5 = 00000000 00000000 00000000 00000101
-4 = 11111111 11111111 11111111 11111100

5与-4 的进位结果  5 & -4 << 1 
---------------------------
00000000 00000000 00000000 00001000

-5与4 的无进位结果 -5 ^ 4 
----------------------------
11111111 11111111 11111111 11111001

进位结果不为 0 继续迭代

第二次迭代结果

进位结果
00000000 00000000 00000000 00010000

无进位结果
11111111 11111111 11111111 11110001

持续迭代..... 最终

进位结果
10000000 00000000 00000000 00000000
无进位结果
00000000 00000000 00000000 00000001

进位结果为0 无进位结果为 1

结果为 1

参考 & 引用

https://leetcode-cn.com/problems/sum-of-two-integers/solution/wei-yun-suan-xiang-jie-yi-ji-zai-python-zhong-xu-y/
https://blog.csdn.net/github_39363510/article/details/77160829