0%

深入补码

补码(2’s complement)是计算机用于表示诸如 +20,-17 这样有符号整数的方式。如在 C 语言中(或者许多其他的静态类型语言),整形数据类型 int 代表长度为 4-Bytes (32-bits) 的有符号数,可表示的范围为 $[-2^{31}, 2^{31} - 1]$,这个范围里的数字有正有负,都是有符号数,而他们在计算机中就是通过补码来表示的。在这些有符号数里正数的补码与我们的直觉相同,但负数的补码形式需要一些转换,本文介绍如何得到一个数的补码,如何读懂补码以及补码内在的原理。

得到补码

-30 在计算机中是如何表示的呢?首先我们认为它是一个有符号整数,那么在计算机中就是用补码表示的,如何得到它对应的补码形式?首先给出结论:按位取反再加一,下面以 8-bits ,即八位二进制位为例,计算-30 的补码:

先写出 30 的二进制形式

0 0 0 1 1 1 1 0

按位取反

1 1 1 0 0 0 0 1

再加一

1 1 1 0 0 0 1 0

这就是 -30 的补码

30 与我们的直觉相同,就是 30 的二进制形式 0 0 0 1 1 1 1 0

读懂补码

如果给我们一个补码,例如上文得到的 -30 的补码,我们如何能知道这个补码表示的数是多少呢,同样,这里先给出结论:若补码最高位为 0,则代表是正数,可直接按照正常步骤转化为十进制,就像上文得到的 30 的补码就是 30 的二进制形式一样,若最高位为 1,则代表是负数,要知道负数的补码形式代表的数字,可以先想办法翻转补码的符号,这样就得到的其正数表示,而正数的补码形式又可以直接转化为 10 进制,最后就可知道它代表的是哪个负数了!而翻转符号的方法也是,按位取反再加一

有如下最高位为 1 的补码

1 1 1 0 0 0 1 0

按位取反

0 0 0 1 1 1 0 1

再加一

0 0 0 1 1 1 1 0

这是二进制形式的 30,于是 1 1 1 0 0 0 1 0 代表的是 -30。

int 的范围

在介绍部分说到在 C 语言中,数据类型 int 代表长度为 4-Bytes (32-bits) 的有符号数,可表示的范围为 $[-2^{31}, 2^{31} - 1]$,这是如何得到的呢?

最小整数

观察下面这个 32-bits 的数

1000 0000 0000 0000 0000 0000 0000 0000

最高位为 1,代表是负数,对他进行符号翻转,按位取反再加一,得到

1000 0000 0000 0000 0000 0000 0000 0000

这是二进制形式的 $2^{31}$,可知 $-2^{31}$ 是 int 能表示的最小整数

最大整数

观察下面这个 32-bits 的数

0111 1111 1111 1111 1111 1111 1111 1111

最高位为 0,代表是正数

这是二进制形式的 $2^{31} - 1$,可知 $2^{31} - 1$ 是 int 能表示的最大整数

为什么选择补码

补码有简化计算机内部算术单元电路的优势,若采用补码,加减法的电路可以统一,请看下面的例子:

计算 16 + 30

  0 0 0 1 0 0 0 0 (16)

- 0 0 0 1 1 1 1 0 (30)
——————————————————————
0 0 1 0 1 1 1 0 (46)

计算 16 - 30

也即 16 + (-30)

  0 0 0 1 0 0 0 0 (16)

- 1 1 1 0 0 0 1 0 (-30)
———————————————————————
1 1 1 1 0 0 1 0 (-14)

对于结果 1 1 1 1 0 0 1 0,对其进行符号翻转 (按位取反再加一) 后得到

0 0 0 0 1 1 1 0

这是二进制形式的 14,与预期相符。

从上面两个例子可以看出,补码加减法的算法是统一的,这也统一了计算机内部算术单元的电路逻辑。

为什么是 “按位取反再加一”

如果你不满足于只知道方法,而想知道为什么 “按位取反再加一” 能够奏效,那你可以继续看下去,或者直接跳过这部分。

要想把正数的符号翻转,可以通过 0 减去这个正数,就得到了他对应的负数,就像正数 30,用 0 减去它就得到 -30。下面看看如何得到二进制形式 30 对应的负数:

  0 0 0 0 0 0 0 0 (0)

- 0 0 0 1 1 1 1 0 (30)
——————————————————————
1 1 1 0 0 0 1 0 (-30)

可以看到高位一直在出现 1,因为我们一直在向高位借一,虽然还可以继续减下去,但由于我们限制在 8 位,因此计算机不会继续计算了。

发现了吗,得到的结果其实就是 -30 的补码形式。在计算过程中,我们一直在向高位借一,那为什么不在被减数 0 的最高位之前再加上一个 1 来满足这无休止的借位呢?

因此对于一个 n 位的二进制数,要得到与之符号相反的数,可以用 $2^n$ 减去它。例如此处 n = 8(数字上也就代表一个 1 后跟了 8 个 0),要得到与 30 符号相反的数,可以用 $2^8$ 减去,即下面这个算式:

  1 0 0 0 0 0 0 0 0 (2^8)

- 0 0 0 1 1 1 1 0 (30)
————————————————————————
0 1 1 1 0 0 0 1 0 (-30)

1 0 0 0 0 0 0 0 0 (2^8) 等于 $(2^8 - 1) + 1$,即 8 个 1 再加 1:1 1 1 1 1 1 1 + 1,而用其中的 1 1 1 1 1 1 1 1 减去一个数就相当于对这个数按位取反,另一部分 + 1 就是加一。

总结起来就是按位取反再加一

参考

Two’s Complement By Cornell
关于 2 的补码 By 阮一峰

奥里给,老铁们,干了!