CSAPP第二章读书笔记

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

2.2 整数表示

2.2.2 无符号数的编码

考虑一个二进制数值编码 xxww 位组成,则我们可以将其拆为由 ww0011 表示的位向量 x\vec{x}x=[xw1,xw2,,x0],;;xi0,1,;;i[0..w1] \vec{x} = [x_{w-1}, x_{w-2}, \cdots, x_0],;;x_i \in {0,1},;;i\in[0..w-1]

显然地,一个位向量和一个无符号数编码一一对应;定义函数 B2Uw{ {\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} }遍历,对应的整数值也恰好取遍从 遍历,对应的整数值也恰好取遍从 02^w-1的每一个值。因此, 的每一个值。因此,{\rm B2U}_w是一个双射 是一个双射 {0,1}^w \rightarrow {0,\cdots,2^w-1}$。

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

2.2.3 补码编码

无符号数只能表示非负整数。为了表示负数值,我们选择将 ww 位编码的最高位解释为负权(negative weight),称为符号位。并定义:当符号位为 11 时,代表数值为负;当符号位为 00 时,代表数值为 00 或正。我们称这种编码形式为(二)补码(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$,整个数值就一定为负。

由此可以得出 ww 位补码编码的取值范围:当符号位为 11 且低 (w1)(w-1) 位全为 00 ,即编码为 1000undefinedw1,,zeros{\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$。

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

图 2-14

容易注意到以下两点:

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

    TMinw|{\rm TMin}_w| 没有与之对应的正数,这种不对称性是因为符号位设置为 0011ww 位补码的数值表示范围分为两半,其中符号位为 11 时表示的为负数,符号位为 00 时表示的为非负数(包括 00)。00 占去了对应 TMinw|{\rm TMin}_w| 的位置。

  • UMaxw=2TMaxw+1{\rm UMax}_w = 2{\rm TMax}_w + 1

updatedupdated2023-03-112023-03-11