CSAPP3e第二章(整数的表示)

发表于 2025-01-19 更新于 2025-08-19 分类于组成原理阅读次数：

整数的表示(第二章 Part1)

~~博客还没装 Mathjax 插件，所以下面的 $\LaTeX$ 应该都是乱的~~ 已修

整数表示

这一段如果没有目的和顺序地硬看会觉得关系很多很复杂，但其实只要按照一定的目的和顺序结构就会很清晰。

以设计者的视角思考如何设计

如果我们是设计用二进制表示整数的人，我们需要如何表示二进制？

利用 $w$ 位二进制的最高位 $ x_{w-1} $ 为 $1$ 代表这个数是负数，剩下的部分正常用二进制表示即 $\displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i$

但显然光表示是完全不够的，我们还需要运算，而符号位由于不对具体数值做贡献，会导致运算错误。 因此我们需要让符号位也代表数值，用另一种映射方式计算，于是我们令最高位的符号位具有负的权重 $-x_{w-1} \cdot 2^{w-1}$，这样符号位也参与了计算。但是这样数值又对不上了，因此我们需要把后面的位也变一下。由于我们不是真的设计师，所以我们直接看答案：取反后面的每一位后再 +1。例如10010除符号位取反后变为11101， +1后是11110。这样的表示方法计算出的数值是 $-x_{w-1}\cdot2^{w-1}+\displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i$ 如何论证这样的数值是”对”的呢？

我们需要给”对”下一个定义: ALU (CPU 的算术单元) 的运算只是单纯的进行纯粹二进制的加减法(因为存在更好的方案, 所以专门设计表示负数的硬件是不明智的), 这也就提示我们, 无论我们如何设计各种表示方法, 我们必须要保证他们在纯粹二进制 Binary 的计算下维持转换关系. 所以我们需要考虑我们的表示法和纯粹二进制之间的转换关系。那么”对”就意味着:

存在一个某个函数, 能够将一个纯粹二进制映射到一定范围内的所有数值(尤其是负值)

这个函数必须是双射, 也就是任意二进制可以按照规则解释(映射)出值, 任意值可以用二进制表示

这个映射必须保证数值的运算和底层进行二进制运算的结果同步(这一点暂时不懂可以往下读)

我们称10010 11101 11110 这样的二进制形式为位模式或位向量, 也就是 ALU 真正在算的东西。Formally, $w$ 位的位向量 $\vec{x_w}=[x_{w-1}, x_{w-2}, ..., x_1, x_0]$ (其中 $x \in \{0, 1\}, \text{ where } x \in \mathbb{Z}$)。另外，称一开始的符号位不参与计算的位模式为原码，除符号位取反后的位模式为反码，取反后+1的为补码。我们还将以无符号整数形式(即所有位模式都是 $2^{i}$ 的权值)解释位模式所计算出的十进制数值这个过程写作一个函数 $B2U(\vec{x_w})$ 即 Binary to Unsigned，易得$B2U(\vec{x_w}) = \displaystyle\sum_{i=0}^{w-1}x_i\cdot2^i$。类似地，我们有以反码形式解释位模式所计算出的十进制数值 $B2O(\vec{x_w})$ 和以补码形式解释位模式所计算出的十进制数值 $B2T(\vec{x_w})$。对应地，我们也有这些函数的反函数$U2B(x), T2B(x), O2B(x)$。

则我们需要证明的问题以数学语言描述就是，设 $B2T(\vec{x_w}\prime) = -x_{w-1}\prime\cdot2^{w-1}+\displaystyle\sum_{i=0}^{w-2}x_i\prime\cdot2^i$ 那么我们需要表示的数值 $x = -\displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i = B2T(\vec{x_w}\prime)$, 其中 $\vec{x}\prime$ 是 $T2B(x)$ 即原码 $\vec{x_w}$ 取反后 + 1的位模式。(正数的无符号表示、原码、反码、补码都一样，以下只考虑负数)

考虑到 +1 导致的进位影响我们对 $\vec{x_w}\prime$ 的表达，我们借助反码 $\vec{x_w}\prime\prime$，根据定义得知 $B2O(\vec{x_w}\prime\prime) + 1 = B2T(\vec{x_w}\prime)$ 。则 $x_i\prime\prime = (1 - x_i)$一个连等式就能证明全部：

~~(沟槽的 hexo-filter-mathjax 插件有 Bug，我本地 MarkText 的 Mathjax 正常解析多行，这里就变单行了，对付看罢。)~~ 已修 \[ \begin{aligned} x &= -\displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i \\ &= -2^{w-1} + 2^{w-1} - 1 - \displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i + 1 \\ &= -2^{w-1} + \displaystyle\sum_{i=0}^{w-2}2^i - \displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i + 1 \\ &= -2^{w-1} + \displaystyle\sum_{i=0}^{w-2}(1-x_i)\cdot2^i + 1 \end{aligned} \]

其中 $(1-x_i) = x_i\prime\prime$ 即对每一位取反, 得到反码的位模式 $\vec{x_w}\prime\prime$，按照我们补码位模式 $x_i\prime$ 的定义 $\vec{x_w}\prime = \vec{x_w}\prime\prime + 1$:

\[ \begin{aligned} x &= -2^{w-1} + \displaystyle\sum_{i=0}^{w-2}(1-x_i)\cdot2^i + 1 \\ &= -2^{w-1} + \displaystyle\sum_{i=0}^{w-2}x_i\prime \cdot 2^i \end{aligned} \]

而由于我们讨论的都是负数, 也就是符号位 $x_{w-1}\prime = 1$, 这样我们证明了补码的数值转换函数$B2T(\vec{x_w}) = -x_{w-1}\cdot2^{w-1}+\displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i$ 的数值表示是正确的(实际上这个函数是一个双射)，而此时符号位也参与了运算，所以这套表示体系也能正常参与运算（后面会更详细地说明运算问题）

事实上，补码也能正常参与运算，只是对 0 的表示有两种 (0000 和 1111) 。

给出补码的数值转换函数 $B2O = -x_{w-1}\cdot(2^{w-1}-1)+\displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i$

如何取负？

创造补码的主要需求就是表示负数。既然我们有了补码的定义，很容易就知道对一个数 $x$ 取相反数就是令 $x$ 的补码 $\vec{x_w}$ 所有位 取反然后再 +1。

Q: 为什么是所有位取反？补码不是除符号位取反再 +1 吗？

A: 取相反数符号位肯定要变化啊。我们是+3 -> -3

注意到这个其实就是 $-x = (2^w - x) \mod 2^w$，注意不到也没关系，~~因为我就没注意到~~, 但是要记住这个式子。

一直说到这, 看起来补码就像是一个美丽的巧合, 我们设计(照书抄的)了一个不错的转换关系, 让补码的运算规则恰好能表示负数值, 同时符号位也参与运算, 也能得出正确的计算结果, 对吧? ….对吗?

环绕, 溢出, 取模, 同余与群

正式的运算规则要到下一篇博客 (Part II) 说, 这里只是借运算来指出补码的设计原理。

首先无论是什么码, ALU 是不会管那么多的, 只会按照 Binary 即纯粹的二进制进行运算, 我们需要保证我们设计的补码能够在纯粹二进制的运算下保证得出的结果仍然符合 $B2T$ 的计算公式. 即 $z = x + y = B2T(\vec{x}\prime) + B2T(\vec{y}\prime) = B2T(\vec{x}\prime)$ (也就是上文说的”数值要和映射函数的运算结果同步”)

乍一看(负数)补码的二进制(或者称作 $T2B$), 最高位符号位导致这个二进制对应的一个非常大的数, 用一个在纯二进制中很大的数来表示一个负数, 这看起来似乎是非常反直觉的, 但是先不要急, 不管表示方式如何, 我们只要理解为什么这样的表示方式能够在运算后(以及多次运算, 交换/结合运算后)仍然符合数值转换规则就可以了, 那要怎么理解呢?

一种方式是暴力拆解上面的公式, 当然这样也能证出来, 但是缺乏直观的原理理解。

另一种方法是, 考虑一个时钟, 现在是 $2$ 点钟, $3$ 小时前是 $2 - 3 = -1$ 点吗? 显然不是, 而是 $11$ 点钟, 是不是很像补码的感觉 “用一个很大的数表示一个负数”? 这样在纯粹的二进制无法直接表示负数的情况下, 把一个负数 $-3$ 变成了一个很大的正数 $9$, 并计算得到 $ 2 - 3 = 2 + 9 = 11$, 这个 $9$ 就是 $ -3 = -3 + 12 = 9$, 用同余的话来说, 因为 $9 \equiv -3 \pmod {12}$

这样我们用一个大数表达了一个负数, 通过加上当前计数系统的最大值 $12$ (或者说通过 $\mod 12$), 通过在计算机中应用类似的技巧, 只是把 $ $ 变为 $ ^w$. 所以就有了上面的式子 $-x = (-x + 2^w) \mod 2^w$.

具体来说, $\mod 2^w$ 的操作是靠 ALU (更准确具体地说是加法器) 天然的溢出性质实现的, $1111_B + 1_B = 0000_B$, 高位的 $1$ 因为溢出被舍掉了, 就相当于截断超出 $w$ 位的位, 也就是对 $2^w$ 取模.

类比时钟来说, 我们的映射关系 $B2T(\vec{x_w}) = -x_{w-1}\cdot2^{w-1}+\displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i$ 就相当于把时钟中的 $11$ 减去 $12$ 得到 $-1$, 而维持这个映射关系的运算结果和数值的运算结果同步(以下简称”性质”)的原理就是往回拨弄时钟.

那有没有更 formal 的表达呢? 有的兄弟有的:

$11$ 和 $-1$ 关于 $12$ 同余, ALU 的溢出截断产生的实际上就是与未截断的原数同余的数值。
而补码所对应的二进制数值实际上就是原负数模 $2^w$ 的同余等价类。

从数学推理的角度思考, 我们要做的是:

为了能用二进制表示负数, 需要找一个无符号大数 $x$ 作为负数 $-v$ 的代理人
为了维持性质, 结合 ALU 溢出的同余性质, 需要找这个代理人满足对任意数 $a$ 满足 $a + x \equiv a - v \pmod {2^w}$

根据同余的性质, 得到 $x \equiv -v \pmod {2^w}$, 即 补码所对应的二进制数值实际上就是原负数模 $2^w$ 的同余群。

补码的不对称性

想一想，设 $\mathrm{TMin}$ 为 $w$ 位补码表示的最小数值，那么：
$\mathrm{TMin}$ 的补码位模式(即 $T2B(\mathrm{TMin})$ ) 是多少？
  int custom_abs(signed int x) {
      if(x < 0) return -x;
      return x;
  }
这段代码有什么问题？

根据上面的问题，我们发现 custom_abs(TMin) 返回的还是 TMin.

在补码语境下，由于符号位是 1 表示的都是正数，符号位是 0 的表示的都是非负数，这两者表示的数字个数相等，而 0 不是正数也不是负数，但它是非负数，所以表示的正数比负数少一个，所以 $\mathrm{TMax + 1 = abs(TMin)}$ , 例如对 4 字节正数，最大值是 $2^{31} - 1 = 2147483647$, 而最小值是 $-2^{31} = -2147483648$。

在 C 和 C++ 语言中，unsigned修饰的无符号数以无符号形式解释，即我们的 $B2U$，其他的则以补码解释。

Java 以补码解释。Rust i32 i64 等以补码表示，u32 等以无符号数形式解释。

C 和 C++ 的 unsigned 溢出是行为良好的，上下溢出都是循环，但有符号正数的溢出是未定义行为。注意浮点数的溢出也是行为良好的，因为 IEEE 754 规定了溢出产生正负无穷。

Java 的溢出是行为良好的，按照补码规则循环环绕到最小值

Rust 的溢出取决于编译模式，Debug 模式会触发panic ，Release 模式类似 Java。

Python 不太清楚具体怎么表示的，理论上只要内存够应该不存在溢出的情况？我还在学 py。

无符号数解释和补码解释的关系

对于一个位模式 $\vec{x_w}$ 以无符号数解释的数值 $B2U(\vec{x_w})$ 和以补码解释的数值 $B2T(\vec{x_w})$ 有什么关系？考虑这两者的公式（设 $x_{w-1} = 1$ )：

$B2U(\vec{x_w}) = \displaystyle\sum_{i=0}^{w-1}x_i\cdot2^i = x_{w-1}\cdot2^{w-1}+\displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i$

$B2T(\vec{x_w}) = -x_{w-1}\cdot2^{w-1}+\displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i$

发现只有最高为的权重正负不同，即两者只差 $2 \times 2^{w-1} = 2^w$

当然如果是正数，$x_{w-1} = 0$ 则二者相等。

故：$B2U(\vec{x_w}) - 2^w = B2T(\vec{x_w})$

(当然, 从补码的同余原理上我们也能得出这一结论)

于是就有了这个经典的图：

取相反数的证明

我们上面说了取相反数就是 $-x = (2^w - x) \mod 2^w$ .下面来证明一下。

Formaly, 我们需要证明 $U2B(2^w - b) = T2B(-b)$ ,急症 $B2T(U2B(2^w - b)) = -b $

由上面说到的 $B2U(\vec{x_w}) - 2^w = B2T(\vec{x_w})$ ，令 $x = U2B(2^w - b)$

得 $B2T(U2B(2^w - b)) = B2U(U2B(2^w - b)) - 2^2 = 2^w - b - 2^w = -b$

得证。

举个例子:

$T2B(-3) = U2B(2^w - 3) = T2B(-3)$

扩展和截断

无符号数扩展直接补 $0$ 在前面, 补码扩展在前面补 $1$ (之所以上面说”同余等价类”就是这个原因), 可以证明是正确的。

截断无符号数相当于对 $2^k$ 取模(前面也说了), 截断补码相当于位模式下截断无符号数再转换为补码表示。

换句话说就是：无符号数和补码的操作在位级表示上是相同的, 这一点会在后面大量用到。