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$。

图 2-14

容易注意到以下两点:

  • $|{\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$。

updatedupdated2022-05-212022-05-21