2024-04-29
二进制补码的数学原理
最近在看一些虚拟机相关的，里面状态寄存器的 Overflow 的规则变化看着非常复杂，看完直接注意力涣散 ... 重新想了下应该是对补码相关原理理解不够深刻，这里手写个「补码 demo」来实现完全同步。
备注: 如无特殊说明，本文中出现的整数都是 8 位整数。
# 原码、反码、补码的规则和代数关系 ↵
原码是将数字表示为二进制形式，反码是将其所有二进制位置反, 补码则是在反码的基础上加 1。具体转换可以看下面这个 demo, 在上面输入一个整数，下方会将其转为「原码」「反码」「补码」三种形式
右侧输入:
原码
00011000 ==> 24 (0x18)
反码
11100111 ==> 231 (0xe7) ==> 255 - 24
补码
11101000 ==> 232 (0xe8) ==> 256 - 24
显然上述变换立马就能注意到，任意数值 N 反码后得到的是 255 - N，而补码是在反码基础上加 1，因此总结如下：
- 1.原码: N
- 2.反码: 255 - N
- 3.补码: 255 - N + 1, 即 256 - N
* 其中 255 为 8 位整数的最大数值 (2^n - 1)，对于其他位宽的整数依次类推
# 实现减法 A - B (假设 A >= B) ↵
注意到 N 的补码为 256 - N, 因此:
现在来验证一下 87 - 8 = 79:
当然你可能还会问这不是还有
- 256
么，这个数在二进制上比较特殊，是 0b100000000因此可以考虑
335 & 0b11111111
或者 335 % 256
的方式来求出最终结果# 十进制下的补码推广 ↵
注意到 8 位二进制数 N 的补码是 256 - N，将这个结论推广到十进制则有：4 位十进制数 N 的补码是 1000 - N
对于人脑来说，计算 - 1000 非常容易，因此对于计算机来说计算 - 256 其实也是类似的，很好处理。（甚至都不需要处理，因为前面那个 case 里 335 已经溢出了，剩下的低 8 位就是最终答案了）
# 引入有符号数 ↵
前面讨论的那个 case 是正数减去正数后还是正数的情况，如果要考虑任意加减法的时候就得考虑负数的表达了。
有符号数有两种编码方式，一种是直接用最高位作为符号位的表达，如下左表所示；一种则是「负数用补码、正数用原码」的方式进行编码，如下右表所示：
| 正数 | 十进制 | 负数 | 十进制 |
|---|---|---|---|
| 0000 | 0 | 1000 | -0 |
| 0001 | 1 | 1001 | -1 |
| 0010 | 2 | 1010 | -2 |
| 0011 | 3 | 1011 | -3 |
| 0100 | 4 | 1100 | -4 |
| 0101 | 5 | 1101 | -5 |
| 0110 | 6 | 1110 | -6 |
| 0111 | 7 | 1111 | -7 |
| 原码 | 十进制 | 补码 | 十进制 |
|---|---|---|---|
| 0000 | 0 | 1111 | -1 |
| 0001 | 1 | 1110 | -2 |
| 0010 | 2 | 1101 | -3 |
| 0011 | 3 | 1100 | -4 |
| 0100 | 4 | 1011 | -5 |
| 0101 | 5 | 1010 | -6 |
| 0110 | 6 | 1001 | -7 |
| 0111 | 7 | 1000 | -8 |
进一步，如果我们将「1000」当成「起始点」然后进一步做对比就可以得到下面的这张表。
| 补码有符号数 | 十进制 | 无符号数 | 十进制 | 经典有符号数 | 十进制 |
|---|---|---|---|---|---|
| 1000 | -8 | 1000 | 8 | 1000 | -0 |
| 1001 | -7 | 1001 | 9 | 1001 | -1 |
| 1010 | -6 | 1010 | 10 | 1010 | -2 |
| 1011 | -5 | 1011 | 11 | 1011 | -3 |
| 1100 | -4 | 1100 | 12 | 1100 | -4 |
| 1101 | -3 | 1101 | 13 | 1101 | -5 |
| 1110 | -2 | 1110 | 14 | 1110 | -6 |
| 1111 | -1 | 1111 | 15 | 1111 | -7 |
| 0000 | 0 | 0000 | 0 | 0000 | +0 |
| 0001 | 1 | 0001 | 1 | 0001 | 1 |
| 0010 | 2 | 0010 | 2 | 0010 | 2 |
| 0011 | 3 | 0011 | 3 | 0011 | 3 |
| 0100 | 4 | 0100 | 4 | 0100 | 4 |
| 0101 | 5 | 0101 | 5 | 0101 | 5 |
| 0110 | 6 | 0110 | 6 | 0110 | 6 |
| 0111 | 7 | 0111 | 7 | 0111 | 7 |
可以发现经典有符号数有明显问题：
- 1.+0 和 -0 的问题，重复编码
- 2.做减法不好弄
- 3.随着二进制数的递增，经典有符号数是递减的，而补码有符号数是递增的溢出后刚好是 0, 换言之没有做到「溢出循环」
第三个尤为重要，因为对某个负数 N 做加 10 操作的时候，实际就是加十次 1 也就是顺着这张表走十次，如果跟二进制数的单调性对不上的话就没法做了，而刚好补码对上了这个顺序因此对一个补码的数字 +1 后得到的二进制数依然是对应的补码，比如上表中，-6(1010) 对其进行 +1 得到 1011 而刚好就是 -5(1011)
# 实现任意减法 A - B ↵
前面讨论的 case 是 A >= B 的情况，现在引入了有符号数后我们就能实现任意减法了
右侧输入:
原码
00010001 ==> 17 (0x11)
反码
11101110 ==> 238 (0xee) ==> 255 - 17
补码
11101111 ==> 239 (0xef) ==> 256 - 17
下面是输入 A 和 B 并求出 A + B 和 A - B
A =00000010 ==> 2 (0x2)
B =00001000 ==> 8 (0x8)
A + B =00001010 = 10
A - B = A + 补码(B) - 256 =11111010 - 256 = -6 - 256
# 溢出问题 ↵
也许你已经注意到了，当 A=127 B=1 的时候，此时 A+B 就会出现溢出问题，最终得到了错误的 -128 作为结果。
A =01111111 ==> 127 (0x7f)
B =00000001 ==> 1 (0x1)
A + B =10000000 = -128
A - B = A + 补码(B) - 256 =01111110 - 256 = 126 - 256
为了应对这个问题, CPU 在状态寄存器里用 Overflow Flag 作为有符号数算术运算的溢出指示
以加法为例，可以有枚举出四种 case:
- A 是正数、B 是正数、结果是负数
- A 是正数、B 是负数, 根据结果的正负可细分为两个 case: 8 + (-10) = -2 和 8 + (-7) = 1 因此两者都不会溢出
- A 是负数、B 是正数, 加法满足交换律，跟上面一样
- A 是负数、B 是负数、结果是正数
评估上述最后可以归纳出：当 A 和 B 和结果的符号都不相等的时候就是溢出了:
00function isOverflow(a: number, b: number, result: number) { 01 return !!( 02 (a^result) & (b^result) & 0b10000000 03 ); 04}