为什么补码长成这个样

课本上没有的知识。

为什么使用补码 #

即答:想用加法的逻辑处理减法。

加法器的逻辑门电路易于设计、效率高。如果能把减法转换为加法,那么加减法就都能通过加法器进行,不需要额外设计减法器,能进一步简化芯片的设计。

具体怎么转换呢?

info

减去一个数,等于加上这个数的相反数。

$$a-b=a+(-b)$$

这句废话文学是补码的根本原理。

补码是如何形成的 #

补码充分体现了什么叫作「bug 用得好就是特性」。

溢出 #

计算机中,储存数据的容器有一个重要的特性:溢出。

这是一个四位二进制数的容器,每格只能存 $0$ 或 $1$,最多只能存到 $(15)_{10}=(1111)_2$。

$$\boxed{1} \ \boxed{1} \ \boxed{1} \ \boxed{1}$$

当把 $(10010)_2$ 存入该容器时,最高位的 $1$ 会被扔掉,储存的结果变成了 $(10)_2$,相当于减少了 $\color{red}(10000)_2$。

$$ \cancel 1 \ \boxed{0} \ \boxed{0} \ \boxed{1} \ \boxed{0} \ \color{transparent}{\cancel 1}$$

这导致,在长度为 $4$ 的容器中,$(10001)_2\Longrightarrow(1)_2$,$(10010)_2\Longrightarrow(10)_2$,$\cdots$

越加越小 #

在固定长度的容器中作加法,常常会因为 溢出 而出现「越加越小」的情况。

还是拿长度 $4$ 的容器举例:

$$(1001)_2+{\color{green}(1110)_2}=(10111)_2\Longrightarrow (111)_2$$

而我们又知道 $$(1001)_2+{\color{blue}(-110)_2}=(111)_2\color{transparent}\Longrightarrow (10111)_2$$

容易看出,在该容器中,加负数 ${\color{blue}(-110)_2}$ 跟加正数 ${\color{green}(1110)_2}$ 是一回事。可以认为 ${\color{blue}(-110)_2}$ 和 ${\color{green}(1110)_2}$ 等价。

有没有一种系统的方法,给出负数,就能算出等价的正数?

note

设与负数 $-x$ 等价的正数为 $y$,参与加法的另一个常数为 $C$,则

$$C+(-x)=C+y\color{red}-(10000)_2$$

解得 $y={\color{red}(10000)_2}-x$

info

等式的右边的 $\color{red}-(10000)_2$,是在用数学方法模拟 href="#%e6%ba%a2%e5%87%ba"

溢出 的情况。

检验:把 $x={\color{blue}(110)_2}$ 代入,解得 $y={\color{green}(1110)_2}$。

进一步说,对于长度为 $m$ 的容器,有

$$y=(1\underset{m \times 0}{\underbrace{00\cdots0}})_2-x$$

还是减法? #

尴尬的地方来了:计算 $x$ 所用的还是减法

不过仔细一看,被减数都是 $(100\cdots0)_2$ 这样的。这类减法其实也就是找找规律的事。

容易发现,对一个四位二进制数 $x$,其各位取反的结果记为 $\sim x$,则

$$x+\sim x=(1111)_2$$

例如 $$(0110)_2+(1001)_2=(1111)_2$$

这 $(1111)_2$,再加上 $1$,恰好就等于 $(10000)_2$。也就是说

$$x+\sim x+1=(10000)_2$$

因此 $$y=(10000)_2-x=\sim x+1$$

进一步说,对任意定长的容器而言,都有 $y=\sim x+1$

符号问题 #

实际上,我们往往会用容器的第一个格子表示符号,$0$ 表示正数,$1$ 表示负数,例如

$${\color{red}\boxed{1}} \ \boxed{1} \ \boxed{0} \ \boxed{1} \ \boxed{0}$$

表示 $(-1010)_2$。

因此上述的取反操作显然不能把符号位涵盖进去。

结论 #

到此为止,我们终于可以流畅爽滑地定义所谓「补码」:

info

  1. 正数的补码就是其本身。
  2. 负数的补码为对该数除符号位外各位取反,然后在最后一位加 $1$。

计算 $a-b$ 时,直接把 $a$ 和 $-b$ 的补码相加即可。