CSAPP 第二章笔记

原码、反码、补码

国内的教材在介绍原码、反码、补码相关概念时，只谈算法而不触及其背后的原理。实际上，补码这一概念与数论中的补数密切相关，本节从补数的角度审视补码的概念。

一个例子

稍有良心的国内教材在谈到补码等概念时，一般会以钟表为例子，引出补码这一概念，但是往往不会去深挖其中的细节。 本文仍以钟表为例，把这些缺失的细节挖掘出来。

首先，当我们谈论数的进制，如十进制，“十”并不包含在数位的范围内，而是表示数有多少个基。所以，我们日常所见的钟表，其时刻在数学上应当表述为 $[0, 1, 2, \ldots, 11]$ 。为了与一般的十进制数进行区分，将 $10$ 和 $11$ 分别记作 $A$ 和 $B$ ，则钟表的时刻可以表示为 $[0, 1, 2, \ldots, 9, A, B]$ 。

当我们想把钟表从 $3$ 时刻拨动到 $1$ 时刻时，既可以逆时针地拨动 $2$ 个单位（也可以解释为顺时针拨动 $-2$ 个单位），也可以顺时针地拨动 $10$ 个单位。从数轴上看，后一种方法实际上可分为如下三部：

  • 从 $3$ 时刻顺时针拨动 $B -3 = 8$ 个单位到 $B$ 时刻；
  • 从 $B$ 时刻顺时针拨动 $1$ 个单位到 $0$ 时刻；
  • 从 $0$ 时刻顺时针拨动 $1$ 个单位到 $1$ 时刻。

综上，我们一共需要 $8 + 1 + 1 = 10$ 个单位的拨动。

一般地，在一个具有 $M$ 个刻度的钟表中（即最大刻度为 $M - 1$ ），当我们想从 $y$ 时刻拨动到 $x$ 时刻（其中 $y > x >= 0$ ）时，可以分为如下三部：

  • 从 $x$ 时刻顺时针拨动 $M - 1 - y$ 个单位到 $M - 1$ 时刻；
  • 从 $M - 1$ 时刻顺时针拨动 $1$ 个单位到 $0$ 时刻；
  • 从 $0$ 时刻顺时针拨动 $x$ 个单位到 $x$ 时刻。

因此，我们需要拨动的总单位数为 $M - 1 - y + 1 + x = M - (y - x)$ 。所以，对于一个具有 $M$ 个刻度的钟表，逆时针拨动 $z$ 个单位（ $z > 0$ ），等价于顺时针拨动 $\hat{z} = M - z$ 个单位。

另外，很直观的一个推论是，一个数进行两次求补运算后，所得结果仍为其自身：

$$\hat{\hat{z}} = M - (M - z) = z.$$

“取反加一”的真相

在上述例子中，我们可以看到，逆时针拨动 $z$ 个单位等价于顺时针拨动 $M - z$ 个单位。

对于一个 $N$ 位的二进制数，其能够表示 $2^N$ 个“刻度”，因此，减去 $z$ 个单位等价于加上 $\hat{z} = 2^N - z$ 个单位。

设 $z$ 的二进制表示为 $\boldsymbol{z} = [z_0, z_1, \cdots, z_{w-1}]$ ，则：

$$z = \sum_{i=0}^{w-1} 2^i z_i.$$

记 $\tilde{z}$ 为 $z$ 按位取反，即：

$$\tilde{z} = \sum_{i=0}^{w-1} 2^i {1-z_i} = \sum_{i=0}^{w-1} 2^i -z.$$

因此，在二进制表示下，补码 $\hat{z}$ 与反码 $\tilde{z}$ 之间存在这样的关系：

$$\hat{z} = \tilde{z} + 1.$$

细节问题

需要指出，一个数的补码与补码表示是两个不同的概念。任何有二进制表示的数都有补码，你可以对任何数进行求补运算，即“取反加一”后的结果，但只有非正数才有所谓的补码表示，或者广义地说（这也是绝大部分教材选用的解读方式），正数的补码表示就是其原码。补码（或者更一般的补数）最终是为了将减法转换为加法进行处理，所以从这个视角上看，补码的作用范围仅限于非正数（ $0$ 比较特殊，其补码与其原码相同，这也是补码表示带来的额外好处）。