CSAPP第二章读书笔记

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

2.2 整数表示

2.2.2 无符号数的编码

考虑一个二进制数值编码 xxww 位组成,则我们可以将其拆为由 ww0011 表示的位向量 x\vec{x}

x=[xw1,xw2,,x0],    xi{0,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},它将位向量转换成对应的无符号数编码:

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

考虑 ww 位无符号数编码的取值范围:当 ww 位全为 00 时,编码取得最小值 UMinw=0{\rm UMin}_w=0;当 ww 位全为 11 时,编码取得最大值,为 UMaxw=2w1{\rm UMax}_w = 2^w-1

考虑函数 B2Uw{\rm B2U}_w 显然是双射,因此随着 ww 位无符号数编码按字典序从 0000wzeros\underbrace{\tt 000\cdots0}_{w\,\,{\rm zeros} }1111wones\underbrace{\tt 111\cdots1}_{w\,\,{\rm ones} } 遍历,对应的整数值也恰好取遍从 002w12^w-1 的每一个值。因此,B2Uw{\rm B2U}_w 是一个双射 {0,1}w{0,,2w1}\{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)。相应地,我们定义函数 B2Tw{\rm B2T}_w,它将位向量转换成对应的补码编码:

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

从定义中我们可以看到:在补码编码中,低 (w1)(w - 1) 位代表的数值仍大于等于 00,而整个数值的负号来源是最高位代表的数值 2w1-2^{w-1};这是由于最高位的权重最大,对最高位和低 (w1)(w - 1) 位总有 2w1>i=0w212i=2w11i=0w2xi2i|-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,因此只要符号位设为 11,整个数值就一定为负。

由此可以得出 ww 位补码编码的取值范围:当符号位为 11 且低 (w1)(w-1) 位全为 00 ,即编码为 1000w1zeros{\tt 1}\underbrace{\tt 00\cdots0}_{w-1\,\,{\rm zeros} } 时,代表的数值最小,为 TMinw=2w1{\rm TMin}_w = -2^{w-1};当负权被设为 00,低 (w1)(w-1) 位全为 11,即编码为 0111w1ones{\tt 0}\underbrace{\tt 11\cdots1}_{w-1\,\,{\rm ones} } 时,代表的数值最大,为 TMaxw=2w11{\rm TMax}_w = 2^{w-1}-1

同样易知 B2Tw{\rm B2T}_w 是双射 {0,1}w{2w1,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

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

评论

You forgot to set the shortname for Disqus. Please set it in _config.yml.