CSAPP第二章读书笔记

CSAPP 第二章主要讲述了整数和浮点数在计算机中的存储与运算方式，及计算机内部表示信息的方式。

2.2 整数表示

2.2.2 无符号数的编码

考虑一个二进制数值编码 $x$ 由 $w$ 位组成，则我们可以将其拆为由 $w$ 位 $0$ 或 $1$ 表示的位向量 $\vec{x}$：

$\vec{x} = [x_{w-1}, x_{w-2}, \cdots, x_0],\;\;x_i \in \{0,1\},\;\;i\in[0..w-1]$

显然地，一个位向量和一个无符号数编码一一对应；定义函数 ${ {\rm B2U}_w}$，它将位向量转换成对应的无符号数编码：

${\rm B2U}_w(\vec{x}) = \sum_{i=0}^{w-1}x_i2^i$

考虑 $w$ 位无符号数编码的取值范围：当 $w$ 位全为 $0$ 时，编码取得最小值 ${\rm UMin}_w=0$；当 $w$ 位全为 $1$ 时，编码取得最大值，为 ${\rm UMax}_w = 2^w-1$。

考虑函数 ${\rm B2U}_w$ 显然是双射，因此随着 $w$ 位无符号数编码按字典序从 $\underbrace{\tt 000\cdots0}_{w\,\,{\rm zeros} }$ 向 $\underbrace{\tt 111\cdots1}_{w\,\,{\rm ones} }$ 遍历，对应的整数值也恰好取遍从 $0$ 到 $2^w-1$ 的每一个值。因此，${\rm B2U}_w$ 是一个双射 $\{0,1\}^w \rightarrow \{0,\cdots,2^w-1\}$。

相应地，我们也可定义 ${\rm B2U}_w$ 的反函数 ${\rm U2B}_w$：它将一个 $w$ 位无符号数编码映射成对应的位向量。

2.2.3 补码编码

无符号数只能表示非负整数。为了表示负数值，我们选择将 $w$ 位编码的最高位解释为负权（negative weight），称为符号位。并定义：当符号位为 $1$ 时，代表数值为负；当符号位为 $0$ 时，代表数值为 $0$ 或正。我们称这种编码形式为（二）补码（two’s-complement）。相应地，我们定义函数 ${\rm B2T}_w$，它将位向量转换成对应的补码编码：

${\rm B2T}_w(\vec{x}) = -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2}x_i2^i$

从定义中我们可以看到：在补码编码中，低 $(w - 1)$ 位代表的数值仍大于等于 $0$，而整个数值的负号来源是最高位代表的数值 $-2^{w-1}$；这是由于最高位的权重最大，对最高位和低 $(w - 1)$ 位总有 $|-2^{w-1}| > \sum\limits_{i=0}^{w-2}1 \cdot 2^i = 2^{w-1}-1 \geq \sum\limits_{i=0}^{w-2}x_i2^i$，因此只要符号位设为 $1$，整个数值就一定为负。

由此可以得出 $w$ 位补码编码的取值范围：当符号位为 $1$ 且低 $(w-1)$ 位全为 $0$ ，即编码为 ${\tt 1}\underbrace{\tt 00\cdots0}_{w-1\,\,{\rm zeros} }$ 时，代表的数值最小，为 ${\rm TMin}_w = -2^{w-1}$；当负权被设为 $0$，低 $(w-1)$ 位全为 $1$，即编码为 ${\tt 0}\underbrace{\tt 11\cdots1}_{w-1\,\,{\rm ones} }$ 时，代表的数值最大，为 ${\rm TMax}_w = 2^{w-1}-1$。

同样易知 ${\rm B2T}_w$ 是双射 $\{0,1\}_w \rightarrow \{-2^{w-1},-2^{w-1}+1, \cdots, 2^{w-1}-1 \}$，因此可以定义 ${\rm B2T}_w$ 的反函数 ${\rm T2B}_w$。

容易注意到以下两点：

• $|{\rm TMin}_w| = |{\rm TMax}_w| + 1$

  $|{\rm TMin}_w|$ 没有与之对应的正数，这种不对称性是因为符号位设置为 $0$ 或 $1$ 将 $w$ 位补码的数值表示范围分为两半，其中符号位为 $1$ 时表示的为负数，符号位为 $0$ 时表示的为非负数（包括 $0$）。$0$ 占去了对应 $|{\rm TMin}_w|$ 的位置。

• ${\rm UMax}_w = 2{\rm TMax}_w + 1$。