计算机系统漫游

信息的处理及表示

2.1 信息存储

练习 2.2

nn 2n2^n (十进制) 2n2^n (十六进制)
9 512 0x200
19 524288 0x80000
14 16384 0x4000
17 16 131072 65536 0x10000
17 131072 0x10000 0x20000
5 32 0x10
11 2048 0x800

练习 2.3

十进制 二进制 十六进制
0 0000 0000 0x00
167 1010 0111 0xA7
62 0100 0011 0x43
188 1011 1100 0xBC
55 0011 0111 0x37
1000 1000
1111 0011
52 5 ×\times 16 ++ 2 == 82 0101 0010 0x52
0xAC
0xE7

练习 2.4

十六进制加减法,不得使用进制转换。

A. 0x503c + 0x8 = 0x5044

B. 0x503c - 0x40 = 0x499c 0x503c - 0x40 = 0x4ffc

C. 0x503c + 64 = 0x507c

D. 0x50ea - 0x503c = 0xAD 0x50ea - 0x503c = 0xAE

寻址和字节顺序

练习题 2.5

int val = 0x87654321

小端法 大端法
A 21 87
B 21 43 87 65
C 21 43 65 87 65 43
val 21 43 65 87 87 65 43 21

练习题 2.6

0x00359141 = 0000 0000 0011 0101 1001 0001 0100 0001

0x4A564504 = 0100 1010 0101 0110 0100 0101 0000 0100

1
2
3
4
5
0   0   3   5   9   1   4   1
00000000001101011001000101000001
*********************
01001010010101100100010100000100
4 A 5 6 4 5 0 4

练习题 2.7

1
2
"abcdef" -> (ASCII) 65 66 67 68 69 70
-> (printf) 61 62 63 64 65 66

练习题 2.8

运算 结果
a 01101001
b 01010101
~a 10010110
~b 10101010
a & b 01000001
`a b` 01111101
a ^ b 00111100

练习题 2.10

步骤 *x *y
aa bb
aa aba \oplus b
bb aba \oplus b
aa

练习题 2.11

A. first == last == k

B. inplace_swap(&a[k], &a[k]); 第一行等价于 a[k] = a[k] ^ a[k];

C. void inplace_swap(int* x, int* y); 第一行加上 if(*x == *y) return;

line 4 改为 first < last

练习题 2.12

A. x & 0xFF

B. (~x & ~0xFF) | (x & 0xFF)

C. x | 0xFF

练习题 2.13

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int bis(int x, int m);	//x | m;
int bic(int x, int m); //x & ~m;
//~x = 1 & ~m
int bool_or(int x, int y)
{
int result = bis(x, y);
return result;
}

int boo_xor(int x, int y) //x xor y = x & ~y | ~x & y;
{
int result = bis(bic(x, y), bic(y, x));
return result;
}

练习题 2.15

1
2
3
4
int bool_equal(int x, int y)
{
return ~((x & ~y) | (~x & y));
}

C 语言中的移位运算

  • 左移:

    x << n 表示二进制位向左移动 nn 位,低位补 00

  • 右移:

    • 逻辑右移:x >> n 表示二进制位向左移动 nn 位,高位补 00
    • 算术右移:x >> n 表示二进制位向左移动 nn 位,若 xx 最高位是 00 ,则高位补 00 ;若 xx 最高位是 11 ,则高位补 11 ;。

练习 2.16

x x x<<3 x<<3 x>>2(逻辑) x>>2(逻辑) x>>2(算术) x>>2(算术)
十六进制 二进制 二进制 十六进制 二进制 十六进制 二进制 十六进制
0xC3 1100 0011 0001 1000 0011 0000 1111 0000
0x75 0111 0101 1010 1000 0001 1101 1101 1101`` 0001 1101
0x87 1000 0111 0011 1000 0010 0001 1110 0001
0x66 0110 0110 0011 0000 0001 1001 0001 1001

2.2 整数表示

无符号数编码

对向量 x=[xw1,xw2,,x0]\overrightarrow{x} = [x_{w-1}, x_{w-2}, \dots, x_0]

B2Uw(x)i=0w1xi2i(2.1)\tag{2.1} B2U_w(\overrightarrow{x}) \doteq \displaystyle\sum_{i=0}^{w-1} x_i 2^i

补码编码

对向量 x=[xw1,xw2,,x0]\overrightarrow{x} = [x_{w-1}, x_{w-2}, \dots, x_0]

B2Tw(x)xw12w1+i=0w2xi2i(2.3)\tag{2.3} B2T_w( \overrightarrow{x} ) \doteq x_{w-1}2^{w-1} + \displaystyle\sum_{i=0}^{w-2} x_i 2^i

练习题 2.17

(x)\overrightarrow(x) B2U4(x))B2U_4(\overrightarrow{x})) B2T4(x)B2T_4(\overrightarrow{x})
十六进制 二进制
0xE 11101110 23+22+21=142^3 + 2^2 + 2^1 = 14 23+22+21=2-2^3 + 2^2 + 2^1 = -2
0x0 00000000 00 00
0x5 01010101 4+1=54+1=5 4+1=54+1=5
0x8 10001000 88 8-8
0xD 11011101 8+4+1=138 + 4 + 1 = 13 8+4+1=3-8 + 4 + 1 = -3
0xF 11111111 8+4+2+1=158 + 4 + 2 + 1 = 15 8+4+2+1=1-8 + 4 + 2 + 1 = -1

练习题 2.18

十六进制 二进制 补码
0x2e0 0000 0010 1110 00000000\ 0010\ 1110\ 0000 $2^{10} + 2^8 + 2^7 + 2^6
29+27+26+25=7362^{9} + 2^7 + 2^6 + 2^5 = 736
-0x58 0000 0000 0101 10000000\ 0000\ 0101\ 1000 2^7 + 2^5 + 2^4<br>(26+24+23)=40-(2^6 + 2^4 + 2^3) = -40
0x28
0x30
0x78
0x88
0x1f8
0x8
0xc0
0x48

有符号数与无符号数之间的转换

T2Uw(x)B2Uw(T2Bw(x))T2U_w(x) \doteq B2U_w(T2B_w(x))

练习题 2.19

xx T2U4(x)T2U_4(x)
8-8 88
3-3 1313
2-2 1414
1-1 1515
00 00
55 55

x,TMinwxTMaxw\forall x, TMin_w \le x \le TMax_w

T2Uw(x)={x+2wif x<0xif x0(2.5)\tag{2.5} T2U_w(x) = \begin{cases} x + 2^w &\text{if } x < 0 \\ x &\text{if } x \ge 0 \end{cases}

u,0uUMaxw\forall u, 0 \le u \le UMax_w

U2Tw(x)={u2wif u>UMaxwuif uUMaxw(2.7)\tag{2.7} U2T_w(x) = \begin{cases} u - 2^w &\text{if } u > UMax_w \\ u &\text{if } u \le UMax_w \end{cases}

练习题 2.21

表达式 类型 求值
-2147483647-1 == 2147483648U<br>``0x8000 == 0x8000 无符号 0 1
有符号 1
无符号 0
有符号 1
无符号 1

扩展一个数字的位表示

无符号数转换为一个更大的数据类型:零扩展

补码数数转换为一个更大的数据类型:高位使用 xw1x_{w-1} 填充

证明(数学归纳法):

B2Tw+1([xw1,xw1,,w1,w0])=B2Tw([xw1,xw2,,w1,w0])B2T_{w+1}([x_{w-1}, x_{w-1}, \dots, w_1, w_0]) = B2T_w([x_{w-1}, x_{w-2}, \dots, w_1, w_0])

1
2
short x = -12345;
unsigned y = x; // -> y = (unsigned) (int) x;

练习题 2.23

A.

w fun1(w) fun2(w)
0x00000076 0x00000076 0X00000076
0x87654321 0x00000021 0x00000021
0x000000C9 0x000000C9 0xFFFFFFC9
0xEDCBA987 0x00000087 0xFFFFFF87

B.

fun1 实现将 32 位无符号 int 转换为 8 位无符号 int ,即无符号数对 88 取模。

fun2 实现将 32 位有符号 int 转换为 8 位有符号 int ,有符号数的二进制表示取低 88 位,然后进行有符号扩展。

截断数字

  • 无符号数截断:

    令向量 x=[xw1,xw2,,x0]\overrightarrow{x} = [x_{w-1}, x_{w-2}, \dots, x_0]x=[xk1,,x0]\overrightarrow{x}' = [x_{k-1}, \dots, x_0] 是将 x\overrightarrow{x} 截断 kk 位的结果。令 x=B2Tw(x)x = B2T_w(\overrightarrow{x})x=B2Tk(x)x' = B2T_k(\overrightarrow{x}') ,则 x=x mod 2kx' = x \ mod \ 2^k

    B2Tk([xk1,xk2,,x0])=B2Uw([xw1,xw2,,x0]) mod 2k(2.9)\tag{2.9} B2T_k([x_{k-1}, x_{k-2}, \dots, x_0]) = B2U_w([x_{w-1}, x_{w-2}, \dots, x_0]) \ mod \ 2^k

  • 有符号数截断:

    B2Tk([xk1,xk2,,x0])=U2Tk(B2Uw([xw1,xw2,,x0]) mod 2k)(2.10)\tag{2.10} B2T_k([x_{k-1}, x_{k-2}, \dots, x_0]) = U2T_k(B2U_w([x_{w-1}, x_{w-2}, \dots, x_0]) \ mod \ 2^k)

    其中, B2Uw([xw1,xw2,,x0]) mod 2kB2U_w([x_{w-1}, x_{w-2}, \dots, x_0]) \ mod \ 2^k 先将有符号数转换成无符号数并用无符号方法截断,然后把无符号数转换成有符号数。

练习题 2.24

十六进制 二进制 无符号 补码
原始值 截断值 原始值 截断值 原始值 截断值 原始值 截断值
0 0 0000 000 0 0 0 0
2 2 0010 010 2 2 2 2
9 1 1001 001 9 1 -7 1
B 3 1011 011 11 3 -5 3
F 7 1111 111 15 7 -1 -1

都先将二进制表示转换为无符号数,然后对 2k2^k 取模截断,所得结果视作 kk 位有/无符号数。

练习题 2.25

传入的 length00 时,length - 1 为无符号数,值为 ~0x0 ,比较 ilength - 1 的大小时,i 会被转换为无符号数将其比较,设 length 是一个 k 位无符号数,则 i 若视作无符号数,表示范围为 [0,2k1][0, 2^k - 1][0,2321][0, 2^32 - 1] ,总之 a[i] 将出现越界访问,导致内存错误。

解决方法是第 44 行修改为 for(int i=0; i <= (int)length - 1; i++)

练习 2.26

A.

st 短时,结果不正确。

B.

在 A. 的条件下, strlen(s) - strlen(t) 仍是一个无符号正整数 ,右边的 0 将被视作无符号数,返回真。

1
2
3
4
int strLonger(char *s, char *t)
{
return strlen(s) > strlen(t);
}

2.3 整数的运算

练习 2.27

1
2
3
4
int uadd_ok(unsigned x, unsigned y)
{
return x + y >= x;
}

练习题 2.28

xx 4ux-_4^ux
十六进制 十进制 十进制 十六进制
0 0 16 0 0
5 5 11 B
8 8 8 8
D 13 13 3 D
F 15 1 1

练习题 2.29

xx yy x+yx+y x+t5yx + _t^5y 情况
[100101][100101]<br>27-27 [00101][00101] 情况3 1
[110000][110000]<br>16-16 [10000][10000] 情况 2
[011111][011111] [111111][111111]<br>3131 1-1 [11111][11111] 情况1 2
[000111][000111]<br>77 [00111][00111] 情况 3
[010000][010000]<br>1616 [10000][10000] 情况 4

练习题 2.30

1
2
3
4
int tadd_ok(int x, int y)
{
return !((x > 0 && y > 0 && x + y < 0) || (x < 0 && y < 0 && x + y > 0))
}

练习题 2.31

假设发生正溢出,则 sum = x + y - 2^ksum - x = y - 2^k ,在模 kk 意义下就是 yy ,对 xx 同理,所以正溢出时仍然返回真;同理,负溢出也返回真。

练习题 2.32

tadd_ok(int x, int y) 来判断 xyx - y 是否溢出:

1
2
3
4
int tsub_ok(int x, int y)
{
return tadd_ok(x, -y);
}

这种写法是在假设:对任意 xwtyx - ^t_wy ,若 tsub_ok(x, y) 判断没有溢出,即 x+wt(y)x + ^t_w(-y)tadd_ok(x, -y) 判断没有溢出,这要求 wty=y-^t_wy = -y ,但其实不然。

y=TMinw=2w1y = TMin_w = -2^{w-1} 时, wty=TMinw=y-^t_wy = TMin_w = y ,若 x<0x < 0 ,则 xy=x+2w10x - y = x + 2^{w-1} \ge 0 ,没有发生溢出,但是 x+TMinw=x2w1<2w1x + TMin_w = x - 2^{w-1} < 2^{w-1} ,将被 tadd_ok() 判断为负溢出;若 x>0x > 0xy=x+2w1>2w11x - y = x + 2^{w-1} > 2^{w-1} - 1 ,发生正溢出,而 x+TMinw=x2w1>2w1x + TMin_w = x - 2^{w-1} > 2^{w-1} ,被 tadd_ok() 判断为没有溢出。

解决方法:

1
2
3
4
5
int tsub_ok(int x, int y)
{
if(y == -y) return x < 0;
else return tadd_ok(x, -y);
}

练习题 2.33

xx 4tx-^t_4x
十六进制 十进制 十进制 十六进制
0 0 0 0
5 5 -5 B
8 8 -8 8 -8 8
D -3 3 3
F -1 1 1

无符号乘法

对满足 0x, yUMaxw0 \le x,\ y \le UMax_wxxyy

xwuy=(xy) mod 2w(2.16)\tag{2.16} x * ^u_wy = (x \cdot y)\ mod\ 2^w

有符号乘法

对满足 TMinwx, yTMaxwTMin_w \le x,\ y \le TMax_wxxyy

xwty=U2Tw((xy) mod 2w)(2.17)\tag{2.17} x * ^t_wy = U2T_w ((x \cdot y)\ mod\ 2^w )

练习题 2.34

模式 xx yy xyx \cdot y 截断
[100][100] [101][101]
无符号 44 55 2020<br>[010100][010100] [100][100]
有符号 4-4 3-3 1212<br>[001100][001100] [100][100]
[010][010] [111][111]
有符号 22 77 1414<br>[001110][001110] [110][110]
无符号 22 1-1 2-2<br>111110111110 [110][110]
[110][110] [110][110]
有符号 66 66 3636<br>[100100][100100] [100][100]
无符号 2-2 2-2 44<br>[000100][000100] [100][100]

练习题 2.35

  1. 由有符号数乘法的定义,设 z=xyz = x \cdot yT2Bw(z mod 2w)=[xw1,,x0]T2B_{w}(z\ mod\ 2^w) = [x_{w-1}, \dots , x_0] ,则 p=(z mod 2w)xw12wp = (z\ mod\ 2^w) - x_{w-1} 2^{w} ,所以 p+xw12w=z mod 2wp + x_{w-1} 2^{w} = z\ mod\ 2^w ,即 xy=z=k2w+p+xw12w=p+t2wx \cdot y = z = k 2^w + p + x_{w-1}2^w = p + t2^w

若计算溢出,则 k0k \neq 0 ,又 xw1{0,1}x_{w-1} \in \{0, 1\} ,故 t=k+xw10t = k + x_{w-1} \neq 0

t=k+ww10t = k + w_{w-1} \neq 0 ,由于 k0k \ge 0 ,且 xw1{0,1}x_{w-1} \in \{0, 1\} ,有 k0k \neq 0 ,所以 z2wz \ge 2^w ,计算溢出。

  1. pxp \le x ,则令 q=1q = 1 r=xp, s.t.p=xp+r\exist\ r = x - p , \ s.t. p = xp + r .

    p>xp > x ,则令 r=p mod xr = p\ mod\ x r=xp, s.t.p=xp+r\exist\ r = x - p , \ s.t. p = xp + r .

  2. q=yq = y ,则由 r<x|r| < |x| ,且 x<2w|x| < 2^w ,所以 t=0t = 0p=xyp = x \cdot yr=0r = 0

    r=t=0r = t = 0 ,则 p=xyp = x \cdot y ,易得 q=yq = y

综上,若没有溢出,则 t=0t = 0 ,此时 p=xyp = x \cdot y!x || p / x == y 为真。

练习 2.36

1
2
3
4
5
int tmult_ok(int x, int y)
{
int64_t p = x * y;
return p == (int) p;
}

练习 2.37

使用 uint64_t 保存 ele_cnt * ele_size 的结果,防止溢出导致分配的空间过小,进而防止循环复制时超出缓冲区界限。

A. 这个改动没有帮助,因为 malloc 只能接收 int32_t 作为参数,仍然可能溢出。

B.

1
if(asize != (unit32_t)asize) return NULL;

乘以常数

x<<k=x2kx<<k = x \cdot 2^k

KK 分解为二进制序列 [xw1,,x0][x_{w-1}, \dots, x_0] ,则有:

xK=xi=0w1xi2i=i=0w1x<<(xii)x \cdot K = x * \displaystyle\sum_{i=0}^{w-1}x_{i} \cdot 2^i = \displaystyle\sum_{i=0}^{w-1}x<<(x_i \cdot i)

练习题 2.38

可以计算 a2ka \cdot 2^ka(2k+1)a \cdot (2^k + 1) 等,即 1,2,3,4,5,8,91, 2, 3, 4, 5, 8, 9

练习题 2.39

nn 为最高位时, x<<(n + 1) = x(2n+1)=x2nxx \cdot (2^{n + 1}) = x \cdot 2^{n} \cdot x n+1=w1+1=wn+1 = w-1+1 = wx<<(n+1)=x<<wx<<(n+1) = x<<w ,溢出截断后为 xx 00 本身。故改为 x - (x << m) - (x << m)

练习题 2.40

KK 移位 加法/减法 表达式
(x<<3) - (x<<1)
(x<<5) - x
(x<<1) - (x<<3)
(x<<6) - (x<<3) - x

练习题 2.41

视加减法、移位计算的开销决定,选择综合开销最小的那种。

除以 2 的幂

xx 是无符号数:

x>>k=x/2kx>>k = \lfloor x / 2^k \rfloor

此处使用逻辑右移。

xx 是有符号数且大于 00 ,操作与无符号数相同,但使用算术右移。

xx 是有符号数且小于 00 ,除以 2k2^k 时,要先加上偏置位 2k12^k-1,再算术右移:

(x+(1<<k)1)>>k=x/2k(x+(1<<k)-1)>>k = \lceil x/2^k \rceil

练习题 2.42

1
2
3
4
int div16(int x)
{
return !(x & (1 << 31)) * (x >> 4) + (x & (1 << 31)) * ((x + (1 << 4) - 1) >> 4);
}

练习题 2.43

x * M = x * (2^5 - 1)

y = (y < 0 ? (y + (1 << 3) - 1) : y) >> 3 = y / 3

所以 M = 31, N = 2^3 = 8

练习 2.44

A. 若 x > 0 == true ,则为 true

x > 0 == false ,则 x <= 0 ,即 ((x - 1) < 0) == true

B. 若 (x & 7) ==7 ,则 x 最低三位是 111x3232intx << 29 的最高三位是 111 ,故其小于 00

C. xxx \cdot x 的最高位恒为 00 ,因此 x * x >= 0

D. 若 x >= 0 ,则根据有符号数的逆元定义,-x <= 0

E. 若 x=TMinwx = TMin_wx=TMinw<0-x = TMin_w < 0 ,故为假

F. x=y=2311x = y = 2^{31} - 1 时,不成立

G. ??

2.4 浮点数

二进制小数

练习题 2.45

小数值 二进制 十进制
18\frac 1 8 0.0010.001
34\frac 3 4
4316\frac {43} {16} 10.101110.1011 2.68752.6875
1.0011.001
638\frac {63} 8 101.111101.111 5.8755.875
3.18753.1875

练习题 2.46

A. 是 0.000000000000000000000[0011]

B. 315221\frac 3 {15 \cdot 2^{21}}

C. 0.0171661377s0.0171661377s

D. 34.3322753906m34.3322753906m

浮点数的表示

IEEEIEEEV=(1)s×M×2EV = (-1)^s \times M \times 2^E 表示一个浮点数。

  • ss 编码符号位, 00 为正, 11 为负。
  • kk 位阶码,表示一个二进制整数 e=ek1e0e = e_{k-1} \dots e_0 ,用来编码 EE
  • nn 位小数字段,表示一个二进制小数 f=0.fn1f0f = \overline{0.f_{n-1} \dots f_0} ,用来编码 MM

情况 1:规格化的值

  • ee 的所有位不全为 1100
  • E=eBiasE = e - Bias , 其中 Bias=2k11Bias = 2^{k-1} - 1 ,使得双精度指数范围为 10221023-1022 \backsim 1023 ,单精度为 126127-126 \backsim 127
  • M=1+f=1.f_n1f0M = 1+ f = \overline{1.f\_{n-1} \dots f_0}

情况 2:非规格化的值

  • 阶码字段 ee 所有位全为 00 ,即 e=0e = 0
  • E=1BiasE = 1 - Bias
  • M=f=0.fn1f0M = f = \overline{0.f_{n-1} \dots f_0}

M=f=0M = f = 0 时根据 ss 的取值决定表示 +0.0+0.00.0-0.0 ,二者有时候是不同的。

M=f0M = f \neq 0 时用来表示非常接近 00 的数。

情况 3:特殊值

  • 阶码字段 ee 所有位全为 11
  • f=0f = 0 ,表示 ++\infin-\infin
  • f0f \neq 0 表示 NaNNaN (Not a number)

练习题 2.47

ee EE 2E2^E ff MM 2E×M2^E \times M VV 十进制
0 00 00 00 1-1 12\frac 1 2 04\frac 0 4 04\frac 0 4 08\frac 0 8 00 00
0 00 01 00 1-1 12\frac 1 2 14\frac 1 4 14\frac 1 4 18\frac 1 8 18\frac 1 8 0.1250.125
0 00 10 00 1-1 12\frac 1 2 24\frac 2 4 24\frac 2 4 28\frac 2 8 14\frac 1 4 0.250.25
0 00 11 00 1-1 12\frac 1 2 34\frac 3 4 34\frac 3 4 38\frac 3 8 38\frac 3 8 0.3750.375
0 01 00 11 00 11 04\frac 0 4 44\frac 4 4 44\frac 4 4 11 11
0 01 01 11 00 11 14\frac 1 4 54\frac 5 4 54\frac 5 4 54\frac 5 4 1.251.25
0 01 10 11 00 11 24\frac 2 4 64\frac 6 4 64\frac 6 4 32\frac 3 2 1.51.5
0 01 11 11 00 11 34\frac 3 4 74\frac 7 4 74\frac 7 4 74\frac 7 4 1.751.75
0 10 00 22 11 22 04\frac 0 4 44\frac 4 4 82\frac 8 2 44 44
0 10 01 22 11 22 14\frac 1 4 54\frac 5 4 102\frac {10} 2 55 55
0 10 10 22 11 22 24\frac 2 4 64\frac 6 4 122\frac {12} 2 66 66
0 10 11 22 11 22 34\frac 3 4 74\frac 7 4 142\frac {14} 2 77 77
0 11 00 - - - - - - - -
0 11 01 - - - - - - - -
0 11 10 - - - - - - - -
0 11 11 - - - - - - - -

练习题 2.49

A. 2n+1+12^{n+1} + 1

B. 224+12^{24} + 1

舍入

练习题 2.50

A. 10.0210.0_2

B. 10.0210.0_2 10.1210.1_2

C. 11.00211.00_2 11.0211.0_2

D. 11.0211.0_2

练习题 2.51

A. 0.00011001100110011001100[1100]20.00011001100110011001100[1100]_2 精确到小数点右边 2323 位,使用舍入到偶数方法得 0.0.000110011001100110011010.0.00011001100110011001101

B. x0.1=0.00000000000000000000000[0011]=0.1222x' - 0.1 = 0.00000000000000000000000[0011] = 0.1 \cdot 2^{-22}

C. 6060100100.2222=0.08660 \cdot 60 \cdot 100 \cdot 10 0.2 \cdot 2^{-22} = 0.086

D. 0.0862000=171.670.086 \cdot 2000 = 171.67

练习题 2.52

格式 A 格式 B
011 0000 11 0111 000 11
101 1110 22×1.111022^{2} \times 1.1110_2 1001 111 22×1.11122^2 \times 1.111_2
010 1001 21×1.100122^{-1} \times 1.1001_2 0110 100 21×1.10022^{-1} \times 1.100_2
110 1111 23×1.111122^3 \times 1.1111_2 1011 000 24×1.00022^{4} \times 1.000_2
000 0001 22×0.00012^{-2} \times 0.0001 0001 000 26×1.00022^{-6} \times 1.000_2

练习题 2.53

1
2
3
#define POS_INFINITY 0x7FF0000000000000
#define NEG_INFINITY 0xFFF0000000000000
#define NEG_ZERO 0x8000000000000000

练习题 2.54

A. intdouble 没有精度丢失,再转回来也没事

B. x = 0x7fffffff 时,转成 float 会舍入,精度下降,甚至比 x 大的值,再转回 int 会溢出

C. doublefloat 精度会丢失

D. floatdouble 精度不会丢失

E. 浮点数取加法逆元只需要把符号位取反即可,取两次加法逆元符号不变

F. 两侧都会变成 double/double ,且 intdouble 精度不丢失,所以值相等

G. 浮点数取平方,一定为正数,且大于等于 00

H. 若 f + d 溢出 double 最大规格化数值成 inf ,则 f + d - finf

第 3 章 程序的机器级表示

3.4 访问信息

x86_64 寄存器:

格式为 Immm(rb,ri,s)Immm(r_b, r_i, s) 的操作数格式表示的操作数为 M[Imm+R[rb]+R[ri]s]M[Imm + R[r_b] + R[r_i] \cdot s]

练习题 3.1

操作数
%rax 0x100
0x104 0xAB
0x108 0x13
(%rax) 0xFF
4(%rax) 0xAB
9(%rax, %rdx) 0x11
260(%rcx, %rdx) 0x13
0xFC(, %rcx, 4) 0xFF
(%rax, %rdx, 4) 0x11

练习题 3.2

movl %eax, (%rsp)

movw (%rax), %dx

movb $0xFF, %bl

movb (%rsp, %rdx, 4), %dl

movq (%rdx), %rax

movw %dx, (%rax)

练习题 3.3

movb $0xF, (%ebx)%ebx 不可以作为内存引用

movl %rax, (%rsp)%rax 是四字,应该用 movq

movw (%rax), 4(%rsp) :两个操作数都指向内存

movb %al, %sl :似乎不存在 %sl 寄存器

movq %rax, $0x123 :目的操作数不能是立即数

movl %eax, %rdx目的寄存器大小应该和 %rax 保持一致,即 edx

movb %si, 8(%rbp)%si 是双字,应该用 movw

练习题 3.4

movzbl (%rdi), %eax

movb %eax, (%rsi)

movzbl (%rdi), %eax movsbl (%rdi), %eax

movb %eax, (%rsi)

movzbq (%rdi), %rax

mob %rax, (%rsi)

movl (%rdi), %eax

movb %al, (%rsi)

movl (%rdi), %eax

movb %al, (%rsi)

movzbw (%rdi), %ax

movw %ax, (%rsi)

练习题 3.5

1
2
3
4
5
6
7
8
9
void decode1(long *xp, long *yp, long *zp)
{
long *ap = *xp;
long *bp = *yp;
long *cp = *zp;
yp = ap;
zp = bp;
xp = cp;
}

练习题 3.6

6 + (x mod 2^16)

x + y

x + 4y

7 + 9x

0xA + 4y

9 + x + 2y

练习题 3.7

5x + 2y + 8z

练习题 3.8

0x100 0x11

0x108 0xA8

0x118 0x110

0x110 0x14

%rcx 0x0

%rax 0xFD

练习题 3.9

movl %rdi, %rax

salq $4, %rax

movb (%rsi), %cl movq (%esi), %rcx

sarq %cl, %rax

练习题 3.10

1
2
3
4
long t1 = x | y;
long t2 = t1 >> 3;
long t3 = ~t2;
long t4 = z - t3;

练习题 3.11

A. 将 %rdx 所有位置 0

B. movq $0, %rdx

C.

练习题 3.12

1
2
3
4
5
6
7
8
urerndiv:
movq %rdx, %r8
movq $rdi, %rax
movq $0, %rdx
divq %rsi
movq %rax, (%r8)
movq %rad, (%rcx)
ret

练习题 3.13

A. int <

B. short >=

C. unsigned char <=

D. long long !=

练习题 3.14

A. long long >=

B. short/unsigned short ==

C. unsign char <=

D. int !=

练习题 3.15

A. 0x4003fe

B. 0x400521

C. 0x400543 0x400545

D. 0x400560

练习题 3.16

1
2
3
4
5
6
7
8
9
void cond_goto(long a, long *p)
{
if(!p) goto p_nq_zero;
if(!(a > *p)) goto a_g_p;
*p = a;
p_nq_zero:
a_g_p:
return;
}

该判断条件由两个子条件构成,任意一个条件不满足函数都将返回,因此需要两个分支语句。

练习题 3.17

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long gotodiff_se2(long x, long y)
{
long result;
if(x >= y) goto _true;
else goto _false;
_true:
lt_cnt++;
result = y - x;
goto: end_if
_false:
ge_cnt++;
result = x - y;
end_if:
return result;
}

选用本例中的方法代码更加清晰易读,但是可能产生额外的转跳。

练习题 3.18

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long test(long x, long y, long z)
{
long val = x + y + z;
if(x < -3)
{
if(y < z)
val = x * y;
else
val = y * z;
}
else if(x > 2)
val = x * z;
return val;
}

练习题 3.19

A. Tmp=2×(TranTok), Tok=16, Tran=31Tmp=30T_{mp} = 2 \times (T_{ran} - T_{ok}) , \ T_{ok} = 16, \ T_{ran} = 31 \to T_{mp} = 30

B. 30+16=4630 + 16 = 46

练习题 3.20

1
2
3
4
5
6
7
8
9
10
11
12
long arith(long x)
{
long v = x + 7;
if(x) v = x;
v >>= 3;
return v;
}
// =>
long arith(long x)
{
return (x < 0 ? x + 7 : x) / 8;
}

OP 表示除法 /

练习题 3.21

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
long test(long x, long y)
{
long val = 8x;
long val2 = y - x;
long val3 = x & y;
long val4 = x + y;
if(y <= 0)
{
if(y <= -2) val = val4;
}
else
{
val = val2;
if(x - y >= 0) val = val3;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
long test(long x, long y)
{
long val = 8x;
long val2 = y - x;
long val3 = x & y;
long val4 = x + y;
if(y > 0)
{
if(x - y >= 0) val = x & y;
else val = y - x;
}
else if(y <= -2) val = x + y;
return val;
}

练习题 3.23

A.

1
2
3
%rax -> x
%rcx -> y
%rdx -> n

B.

(*p)++ 表示令 x+=1 ,则在第 7 行与 x += y 一起计算.

C.

1
2
3
4
5
6
7
8
9
10
11
dw_loop:
movq %rdi, %rax
movq %rdi, %rcx
imulq %rdi, %rcx // y = x * x
leaq (%rdi,%rdi), %rdx // n = 2 * x
.L2:
leaq 1(%rcx,%rax), %rax // x += y; (*p)++
subq $1, %rdx // n--;
testq %rdx, %rdx //if(n > 0) goto dw_loop:
jg .L2
rep; ret // return x;

练习题 3.24

1
2
3
4
5
6
7
8
9
10
long loop_while(long a, long b)
{
long result = 1;
while(a > b)
{
result *= a + b;
a++;
}
return result;
}

练习题 3.25

1
2
3
4
5
6
7
8
9
10
long loop_while2(long a, long b)
{
long result = b;
while(b > 0)
{
result *= a;
b -= a;
}
return result;
}

练习题 3.26

1
2
3
4
5
6
7
8
9
10
long fun_a(unsigned long x)
{
long val = 0;
while(x != 0)
{
val ^= x;
x >>= 1;
}
return val & 0x1;
}

练习题 3.27

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
long fact_for(long n)
{
long i;
long result = 1;
for(i = 2; i <= n; i++)
{
result += i;
}
return result;
}

long fact_for_while(long n)
{
long result = 1;
long i = 2;
while(i <= n)
{
result += i;
i++;
}
return result;
}

long fact_for_while_guarded_do(long n)
{
long i = 2;
long result = 1;
if(i > n) goto done;
loop:
result *= i;
i++;
if(i <= n) goto loop:
done:
return result;
}


练习题 3.28

1
2
3
4
5
6
7
8
9
10
11
12
long fun_b(unsigned long x)
{
long val = 0;
long i;
for(i = 64; i > 0; i--)
{
val *= 2;
val |= x & 1;
x >>= 1;
}
return val;
}

练习题 3.29

A.

1
2
3
4
5
6
7
8
9
10
long sum = 0;
long i = 0;
while(i < 10)
{
if(i & 1) continue;
sum += i;
i++;
}


B.

1
2
3
4
5
6
7
8
9
10
long sum = 0;
long i = 0;
if(i >= 10) goto done;
loop:
if((i & 1) && (i<10)) goto update;
sum += i;
update:
i++;
if(i < 10) goto loop;
done:

练习题 3.30

A.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void switch2(long x, long *dest)
{
long val = 0;
switch(x) {
case -1:
goto L9;
break;
case 0:
case 7:
goto L5;
break;
case 1:
goto L6;
break;
case 2:
case 4:
goto L7;
break;
case 3:
case 6:
goto L2;
break;
case 5:
goto L8;
break;
default:
goto L2;
break;
}
}

B. L5 L7 L2 均有多个标号。

练习题 3.31

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void switcher(long a, long b, long c, long *dest)
{
long val;
switch(a)
{
case 5:
c = b ^ 15;
case 0:
val = 112 + c;
break;
case 2:
case 7:
val = (b + c) << 2;
break;
case 4:
val = a;
break;
default:
val = b;
}
*dest = val;
}

3.7 过程

练习题 3.32

指令 状态值 (指令 执行 前)
标号 PC 指令 %rdi %rsi %rax %rsp *%rsp 描述
M1 0X400560 callq 10 -- -- 0x7fffffffe820 -- 调用first(10)
F1 0x400548 lea 10 -- -- 0x7fffffffe828 0x400565 调用lea
F2 0x40054c sub 10 11 -- 0x7fffffffe828 0x400565
F3 0x400550 callq 9 11 -- 0x7fffffffe828 0x400565
L1 0x400540 mov 9 11 -- 0x7fffffffe830 0x400555
L2 0x400543 imul 9 11 11 0x7fffffffe830 0x400555
L3 0x400547 retq 9 11 99 0x7fffffffe830 0x400555
F4 0x400555 repz 9 11 99 0x7fffffffe828 0x400565
M2 0x400565 mov 9 11 99 0x7fffffffe820 --

练习题 3.33

(int a, short b, long long *u, char*v)

(int b, short b, long long *v, char*u)

练习题 3.34

A. a0 ... a5 存储在被调用者保存及寻求

B. a6, a7 存储在栈上

C. 因为被调用者保存寄存器总共只有 66

练习题 3.35

A. 是参数 x

B.

1
2
3
4
5
6
7
8
long rfun(unsigned long x)
{
if(x == 0)
return 0;
unsigned long nx = x;
long rv = rfun(nx);
return nx * rv;
}

3.8 数组

练习 3.36

数组 元素大小 整个数组的大小 起始地址 元素 ii
s 22 1414 xsx_s xs+2ix_s + 2i
T 88 2424 xTx_T xT+8ix_T + 8i
U 88 4848 xUx_U xU+8ix_U + 8i
V 44 3232 xVx_V xv+4ix_v+4i
w 88 3232 xwx_w xw+8ix_w+8i

练习题 3.37

short* xs+2x_s+2 leal 2(%rdx), %rax
short M[xs+6]M[x_s+6] mov 6(%rdx), %al
short* xs+2ix_s+2i leal (%rdx, %rcx, 2), %rax
short M[xs+8i+2]M[x_s+8i+2] mov 2(%rdx, %rcx, 8), %al
short* xs+2i10x_s+2i-10 leal -10(%rdx, %rcx, 2), %rax

练习题 3.38

M(P + 8(7i + 5j)) + M(Q + 8(i + 5j))

N = 7 M = 1

练习题 3.39

T D[R][C]\to D[i][j] = *(D + L(C * i + j))

&A[i][0] = A + 4 * (16 * i) = 64i

&B[0][k] = B + 4 * (k) = B + 4k

&B[N][k] = B + 4 * (N * 16 + k) = B + 4k + 1024

练习题 3.40

1
2
3
4
5
6
7
8
9
void fix_set_diag_opt(fix_matrix A, int val, int N)
{
int *Aend = A + N * (N + 1);
do
{
*A = val;
A += N + 1;
} while(A != Aend);
}

3.9 异质的数据结构

练习题 3.41

A.

p: 0

s.x: 8

s.y: 12

next: 16

B.

24

C.

1
2
3
4
5
6
void sp_init(struct prob *sp)
{
sp->s.x = sp->s.y;
sp->p = &(sp->s.x);
sp->next = sp;
}

练习题 3.42

A.

1
2
3
4
5
6
7
8
9
10
long fun(struct ELE *ptr)
{
int result = 0;
while(ptr != NULL)
{
result += ptr->v;
prt = ptr->p;
}
return result;
}

B.

遍历以 ELE 为头节点的链表,求 v 的和。

练习题 3.43

exprexpr typetype 代码
short movw 8(%rdi), %ax
movw %ax, (%si)
char* addq \$10, %rdi
movq %rdi, (%rsi)
int* movq %rdi, (%rsi)
int movq (%rdi), %rax
movl (%rdi, %rax, 4), %eax
movl %eax, (%rsi)
char movq 8(%rdi), %rax
movb (%rax), %al
movb %al, (%rsi)

练习题 3.44

A.

1
2
0	4	8	12
i c j d

B.

1
2
0	4	5	8
i c d j

C.

1
2
0		2		4		6		7		8
w[0] w[1] w[2] c[0] c[1] c[2]

D.

1
2
0		2		4		6		8		16		24		32
w[0] w[1] w[2] w[3] w[4] c[0] c[1] c[2]

E.

1
2
0		10		24
a[0] a[1] t

练习题 3.45

A.

1
2
3
a	b	c	d	e	f	g	h
8 2 8 1 4 1 8 4
0 8 16 24 28 32 40 48

B.

5252

C.

1
2
3
a	c	g	e	h	b	d	f
8 8 8 4 4 2 1 1
0 8 16 24 28 32 34 35

优化后需要填充至 4040 确保下一个实例内存对齐,故大小为 4040

3.10 在机器级程序中将控制与数据结合起来

练习题 3.46

A.

1
2
3
4
00 00 00 00 00 40 00 76		返回地址
01 23 45 67 89 AB CD EF %rbx

<- buf = %rsp

B.

1
2
3
4
00 00 00 00 00 40 00 34		返回地址
33 32 31 30 39 38 37 36 %rbx
35 34 33 32 31 30 39 38
37 36 35 34 33 32 31 30 <- buf = %rsp

C.

返回到 0x00 40 00 34

D.

%rbx 被破坏了,它的值会被加载为 0x33 32 31 30 39 38 37 36

E.

malloc函数调用时应该分配 len(buf)+1 长度的内存来容纳字符串结尾的 \0 ,同时还应该检查 result 是否为 NULL

练习题 3.47

A. 大约 2132^{13}

B. 128 字节即 272^7 ,使得只需要 26=642^6 = 64 次尝试。

练习题 3.48

A.

不带保护:

buf%rspv%rsp+24

带保护:

buf%rsp+16v%rsp+8 ,金丝雀值在 %rsp+40

B.

vbuf 更靠近栈顶,使得溢出更不容易影响到 buf

练习题 3.49

A.

首先将 %rax 设为 8n+228n+22 ,接着让它 & -16 ,等价于让其向下舍入到最接近的 16 的倍数,保证内存对齐。得到 s2s_2 的值

B.

先将 %rsp77 ,而后除以 88 再乘以 88 ,可向上舍入到最近的 88 的倍数,得到 p 的值。

C.

对应最大化与最小化 e1e_1 e2e_2 的情况。

D.

实现 s2s_21616 字节对齐,pp88 字节对齐。

第 4 章 处理器的体系结构

4.1 Y86-64 指令集体系结构

练习题 4.1

1
2
3
4
5
0x100: 30f30f00000000000000
0x10a: 2031
0x10c: 4013fdffffffffffffff
0x116: 6231
0x118: 70c010000000000000

练习题 4.2

A.

1
2
3
0x100: 30f3fcffffffffffffff	irmovq $-4, %rbx
0x10c: 40630008000000000000 rmmovq %rsi, 0x800(%rbx)
0x114: 00 halt

B.

1
2
3
4
5
6
0x200: a06f					push %rsi
0x202: 800c0200000000000000 call proc
0x20b: 00 halt
0x20c: proc.
0x20c: 30f3a000000000000000 irmovq $10, %rbx
0x216: 90 ret

练习题 4.4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
.x86-64
rsum(long*, long):
push rbp
mov rbp, rsp
push rbx
sub rsp, 24
mov QWORD PTR [rbp-24], rdi
mov QWORD PTR [rbp-32], rsi
cmp QWORD PTR [rbp-32], 0
jg .L2
mov eax, 0
jmp .L3
.L2:
mov rax, QWORD PTR [rbp-24]
mov rbx, QWORD PTR [rax]
mov rax, QWORD PTR [rbp-32]
lea rdx, [rax-1]
mov rax, QWORD PTR [rbp-24]
add rax, 8
mov rsi, rdx
mov rdi, rax
call rsum(long*, long)
add rax, rbx
.L3:
mov rbx, QWORD PTR [rbp-8]
leave
ret
1
2
3
4
5
6
7
8
9
10
11
12
13
14
.y86
pushq %rsp
rrmovq %rsp, %rbp
pushq %rbx
irmovq $24, %r8
subq %r8, %rsp
mrmovq -24(%rbp), %r8
mrmovq (%r8), %rdi
mrmovq -32(%rbp), %r8
mrmovq (%r8), %rsi
andq %rsi, %rsi
jg .L2
.L2:
...

练习题 4.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
sum:
irmovq $8, %r8
irmovq $1, %r9
xorq %rax, %rax
andq %rsi, %rsi
jmp test
loop:
mrmovq (%rdi), %r10
irmovq $0, %r11
subq %r10, %r11
andq %r10, %r10
jg endif
rrmovq %r11, %r10
endif:
addq %r10, %rax
addq %r8, %rdi
subq %r9, %rsi
test:
jne loop
ret

练习题 4.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
sum:
irmovq $8, %r8
irmovq $1, %r9
xorq %rax, %rax
andq %rsi, %rsi
jmp test
loop:
mrmovq (%rdi), %r10
irmovq $0, %r11
subq %r10, %r11
andq %r10, %r10
cmovl %r11, %r10
addq %r10, %rax
addq %r8, %rdi
subq %r9, %rsi
test:
jne loop
ret

4.2 逻辑设计和硬件语言控制 HCL

练习题 4.9

1
2
bool xor = (!a && b) || (a && !b);
// eq == (xor == 0)

练习题 4.10

按位 xor ,将所有结果取 and,再取 not .

练习题 4.11

1
2
3
4
5
word Min3 = [
A <= B && A <= C: A;
B <= C : B;
1 : C;
]

练习题 4.12

1
2
3
4
5
word Mid3 = [
(A <= B && B <= C) || (C <= B && B <= A) : B;
(A <= C && C <= B) || (B <= C && C <= A) : C;
(B <= A && A <= C) || (C <= A && A <= B) : A;
]

4.3 Y86-64 的顺序实现

练习题 4.13

阶段 通用 具体
irmoq V, rB irmovq $128, %rsp
取指 icode:ifun <- M_1[0x016] = 3:0
rA:rB <- M_1[0x017] = f:4
valC <- M_8[0x018] = 128
valP <- 0x020
译码
执行 valE <- 128
访存
写回 R[rB] <- 128
更新 PC PC <= 0x020

练习题 4.14

0x02c: b00f

%rsp = 0x120

阶段 通用 具体
popq rA popq %rax
取指 icode:ifun <- M_1[0x02c] = b:0
rA:rB <- m_1[0x02d] = 0:f
valP <- 0x02e
译码 valA <- R[%rsp] = 0x120
valB <- R[5rsp] = 0x120
执行 valE <- valB + 8 = 0x128
访存 valM <- M_8[0x120] = 9
写回 R[%rsp] <- valE = 0x128
R[rA] <- valM = 9
更新 PC PC <- valP = 0x02e

练习题 4.15

%rsp 变更前 %rsp 的值写入%rsp 变更后指向的栈顶内存中

练习题 4.16

%rsp 变更前栈顶的值写入 %rsp

练习题 4.17

阶段 cmovXX rA, rB
取指 icode:ifun <- M_1p[PC]
rA:rB <- M-1[PC+1]
valP <- PC + 2
译码 valA <- R[rA]
执行 valE <- 0 + valA
Cnd <- Cond(CC, ifun)
写回 R[rB] <- valE
更新 PC PC <- valP

练习题 4.18

0x037: 804100000000000000

阶段 通用 具体
call Dest call 0x041
取指 icode:ifun <- M_1[0x037] = 8:0
valC <- 0x041
valP <- 0x037+9 = 0x040
译码 valB <- R[%rsp] = 0x128
执行 valE <- valB + (-8) = 0x120
访存 M_8[valE] <- valP = 0x040
写回 R[%rsp] <- valE = 0x120
更新 PC PC <- valC = 0x041

练习题 4.19

1
bool need_valC = icode in {IIRMIVQ, IRMMOVQ, IMRMOVQ, ICALL, IJXX}

练习题 4.20

1
2
3
4
5
word srcB = [
icode in { IOPQ, IRMMOVQ, IMRMOVQ} : rB;
icode in { IPUSHQ, ICALL, IPOPQ, IRET} : RRSP;
1 : RNONE;
]

练习题 4.22

练习题 4.8popq %rsp 最终将写入内存的值,因此 M 口的优先级应该更高.

练习题 4.24

1
2
3
4
5
6
word dstE = [
icode in { IRRMOVQ } && cnd : rB;
icode in { IRMMOVQ, IPOPQ } : rB;
icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
1 : RNONE;
];

4.4 流水线的通用原理

练习题 4.28

A. CD 之间,延迟为 380ns380ns ,一个时钟周期为 190ns190ns

B.

练习题 4.29

A.

Y(k)=300+20k(ns)Y(k) = 300 + 20k (ns)

T(k)=1s/(300/k+20)nsT(k) = 1s / (300 / k + 20)ns

B.

1/20109=50 GIPS1 / 20 * 10^9 = 50\ GIPS

4.5 Y86-64 d的流水线实现

第 5 章 优化程序性能

5.1 优化编译器的能力和局限性

练习题 5.1

xpyp 在同一个位置。

1
2
3
4
5
6
7
void swap(long *xp, long *xp)
{
*xp = *xp + *xp; // 2 * *xp;
*xp = *xp - *xp; // 0
*xp = *xp - *xp; // 0

}

5.4 消除循环的低效率

练习题 5.3

代码 min max incr square
A 11 9191 9090 9090
B 9191 11 9090 9090
C 11 11 9090 9090

练习题 5.4

A. 在第一个循环中 %xmm0 是临时值,被初始化为 %rbx 的值,每次循环结束后写回 %rbx ,第二个循环中 %xmm0 是累计值。

B. 与 combine3 行为相同。

C. 因为除了每次循环开头没有 将 %rbx 指向内存传给 %xmm0 ,其他都一样,而 %xmm0 本身就是累计值,在循环开始前就初始化为 IDENT 了。

练习题 5.5

A.

加法:nn

乘法: 2n2n

B.

乘法: nn

5.9 提高并行性

**练习题 5.8 ? **

A1: 15.015.0

A2: 10.010.0

A3: 5.05.0

A4: 5.05.0

A5: 10.010.0

5.11 一些限制因素

练习题 5.9

1
2
3
4
int take = src1[i1] < src2[i1];
dest[id++] = src1[i1] < src2[i1] ? src1[i1] : src2[i2];
i1 += take;
i2 += 1 - take;

练习题 5.10

A.

将数组变为: 2, ..., 1000

B.

将数组变为: 1, ..., 1

C.

A 情况中所有循环不想关,可以独立执行; B 情况中,前后迭代存在读/写相关,将导致性能下降。

D.

与情况 A 相同,因为相邻迭代不存在数据相关。

练习题 5.11

相邻的迭代存在数据相关,因此形成了 “存储——加载——加法” 的关键路径,导致性能下降。

练习题 5.12

1
2
3
4
5
6
7
8
9
void psumv(float *a, int len, float *p)
{
float acc = 0;
for(int i=0; i<len; i++)
{
acc += a[i];
p[i] = acc;
}
}

第 6 章 存储器层次结构

6.1 存储技术

练习题 6.1

越接近正方形需要的地址位越少。

组织 rr cc brb_r bcb_c max(b_r, b_c)
44 44 22 22 22
44 44 22 22 22
1616 88 44 33 44
3232 1616 55 44 55
3232 3232 55 55 55

练习题 6.2

512×400×10000×2×2=8.192GB512 \times 400 \times 10000 \times 2 \times 2 = 8.192GB

练习题 6.3

平均旋转延迟: 1/2×(60/15000)×1000ms=2ms1/2 \times (60/15000) \times 1000ms = 2ms

平均传送时间:(60/15000)/500×1000ms=0.008ms(60/15000) / 500 \times 1000ms = 0.008ms

总时间: 8+2+0.008=10ms8 + 2 + 0.008 = 10ms

练习题 6.4

A.

1×1024×1024/512=20481 \times 1024 \times 1024 / 512 = 2048 个逻辑块,这也是扇区数,最优情况是寻到后立刻开始读取数据,且数据在同一个柱面上,需要旋转两圈来读取所有数据。

旋转一圈时间: 60/10000×1000ms=6ms60 / 10000 \times 1000ms = 6ms

总时间:5+6/2+2×6=20ms5 + 6/2 + 2 \times 6 = 20ms

B.

每个块都随机分布在磁盘上,每次都要 5+3=8ms5 + 3 = 8ms

8×2000=16000ms8 \times 2000 = 16000ms

练习题 6.5

A. (109×128)×(1/470)×(1/(86400×365))=8years(10^9 \times 128) \times (1 / 470) \times (1 / (86400 \times 365)) = 8 years

B. (109×128)×(1/330)×(1/(86400×365))=13years(10^9 \times 128) \times (1 / 330) \times (1 / (86400 \times 365)) = 13 years

C. (109×128)×(1/20000)×(1/365)=17.535years(10^9 \times 128) \times (1 / 20000) \times (1/365) = 17.535 years

练习题 6.6

1PB=106GB1PB = 10^6GB

每 GB 价格 500/106500 / 10^6

大约 20252025 年可以实现。

6.2 局部性

练习题 6.7

1
sum += a[i][j][k]

练习题 6.8

N=2N = 2

数据布局为:

1
2
地址	0	4	8	12	16	20	24	28	32	36	40	44
元素 v0 v1 v2 a0 a1 a2 v0 v1 v2 a0 a1 a2

clear1

1
2
3
地址	0	4	8	12	16	20	24	28	32	36	40	44
元素 v0 v1 v2 a0 a1 a2 v0 v1 v2 a0 a1 a2
访问 1 2 3 4 5 6 7 8 9 10 11 12

clear2

1
2
3
地址	0	4	8	12	16	20	24	28	32	36	40	44
元素 v0 v1 v2 a0 a1 a2 v0 v1 v2 a0 a1 a2
访问 1 3 5 2 4 6 7 9 11 8 10 12

clear3

1
2
3
地址	0	4	8	12	16	20	24	28	32	36	40	44
元素 v0 v1 v2 a0 a1 a2 v0 v1 v2 a0 a1 a2
访问 1 5 9 3 7 11 2 6 10 4 8 12

空间局部性从好到差:clear1 clear2 clear3

clear1 顺序访问,clear2 以步长为 33 转跳,clear3 以步长为 66 转跳。

6.4 高速缓存存储器

练习题 6.9

高速缓存 mm CC BB EE SS tt ss bb
1. 256256 2222 88 22
2. 6464 2323 55 33
3. 11 2727 00 55

练习题 6.10

由于消除了抖动,下列标记为 11 的是命中的,00 为不命中。

1
2
3
	0	1	2	3	4	5	6	7
x 0 1 1 1 0 1 1 1
y 0 1 1 1 0 1 1 1

因此命中率为 75%75\%

练习题 6.11

A. 相同组索引的块被映射到同一个高速缓存,缓存内每个块的标记位有 tt 位,因此一个 chunk 有 2t2^t 个块。

B. S=512B=32S = 512, B = 32 ,因此 s=9b=5s = 9, b = 5 ,当使用高 ss 位来作为组索引时,数组中所有块都会被映射到组 00 ,任意时刻缓存中数组的块数都是 11

练习题 6.12

12 11 10 9 8 7 6 5 4 3 2 1 0
CT CT CT CT CT CT CT CT CI CI CI CO CO

练习题 6.13

A.

12 11 10 9 8 7 6 5 4 3 2 1 0
0 1 1 1 0 0 0 1 1 0 1 0 0

B.

参数
CO 0x0
CI 0x5
CT 0x71
命中?
返回字节 0xB

练习题 6.14

A.

12 11 10 9 8 7 6 5 4 3 2 1 0
0 1 1 0 1 1 1 0 1 0 1 0 1

B.

参数
CO 0x1
CI 0x5
CT 0x6E
命中?
返回字节 --

练习题 6.15

A.

12 11 10 9 8 7 6 5 4 3 2 1 0
1 1 1 1 1 1 1 1 0 0 1 0 0

B.

参数
CO 0x0
CI 0x1
CT 0xFF
命中?
返回字节 --

练习题 6.16

1
2
3
4
0000 0110 0100 1100	0x064C
0000 0110 0100 1101 0x064D
0000 0110 0100 1102 0X064E
0000 0110 0100 1103 0X064F

6.5 编写高速缓存友好的代码

练习题 6.27

A.

dst

0 1
0 m m
1 m m

src

0 1
0 m m
1 m h

B.

dst

0 1
0 m h
1 m h

src

0 1
0 m h
1 m h

练习题 6.19

A. 512512

B. 缓存一行能存储两个元素,每隔两次读就会出现一次缓存不命中,共 256256 次。

C. 50%50\%

练习题 6.20

A. 512512

B. 读取每一个 grid[j][i].x 都会缓存不命中,读取 grid[j][i].y 缓存会命中,共不命中 256256 次。

C. 50%50\%

D. 能存下整个数组,只存在冷不命中,不命中率为 25%25\%

练习题 6.21

A. 512512

B. 每两次读取 grid[i][j].x 会出现一次缓存不命中,而读取所有的 grid[i][j].y 缓存命中,不命中 128128 次。

C. 25%25\%

D. 能存下整个数组,只存在冷不命中,不命中率为 25%25\%

6.6 综合:高速缓存对程序性能的影响

练习题 6.21

由图可知, L1L1 峰值为 12000MB/s12000MB/s ,每秒读 12000/812000 / 8 次,每秒周期数 2100M2100M ,得 21000/120008=1.421000 / 12000 * 8 = 1.4

第 7 章 链接

7.5 符号和符号表

练习题 7.1

外部 m.c .data
全局 swap.c .data
全局 swap.c COMMON
全局 swap.c .text
-- -- --

7.6 符号解析

练习题 7.2

A.

(a) -> DEF(main.1)

(b) -> DEF(main.1)

B.

a -> DEF(错误)

(b) -> DEF(错误)

C.

(a) -> DEF(x.2)

(b) -> DEF(x.2)

练习题 7.3

A.

1
gcc p.o libx.a

B.

1
gcc p.o lilbx.a liby.a

C.

1
gcc p.o libx.a liby.a libx.a

练习题 7.4

A. 0x4004e8

B. 0x5

练习题 7.5

refaddr = ADDR(.text) + r.offset = 0x4004da

*refptr = (unsigned)ADDR(swap) + r.addend - refaddr = 0x400e8 - 4 - 0x4004da = 0xa

重定位的值为 4004d9 e8 0a 00 00 00 callq 4004e8 <swap>

第 8 章 异常控制流

8.2 进程

练习题 8.1

8.4 进程控制

练习题 8.2

A

p1: x = 2

p1 x = 1

B

p2: x = 0

练习题 8.3

baccabccacbc

练习题 8.4

A. 66

B.

设子进程id123

1
2
3
4
5
6
Hello
0
Bye
1
2
Bye

练习题 8.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <unistd.h>
#include <stdio.h>

unsigned int snooze(unsigned int secs)
{
int snoozeTime = sleep(secs);
printf("Slept for %d of %d secs\n", secs - snoozeTime, secs);
return snoozeTime;
}

int main()
{
snooze(5);
}

练习题 8.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>

int main(int argc, char *argv[], char *envp[])
{

for (int i = 0; argv[i] != NULL; i++)
{
printf("argv[ %d]: %s\n", i, argv[i]);
}

for (int i = 0; envp[i] != NULL; i++)
{
printf("envp[ %d]: %s\n", i, envp[i]);
}

return 0;
}

练习题 8.7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include "../lib/csapp.h"

unsigned int snooze(unsigned int secs)
{
int snoozeTime = sleep(secs);
printf("Slept for %d of %d secs\n", secs - snoozeTime, secs);
return snoozeTime;
}

void handler(int sig)
{
return;
}

int main(int argc, char *argv[])
{
if (signal(SIGINT, handler) == SIG_ERR)
unix_error("signal error");

snooze(atoi(argv[1]));

return 0;
}

练习题8.8

1
213

第 9 章 虚拟内存

9.2 地址空间

练习题 9.1

虚拟地址位数 虚拟地址数 最大可能虚拟地址数
28=2562^8 = 256 255255
1616 21612^{16} - 1
3232 232=4G2^{32} = 4G
4848 24812^{48} - 1
6464 264=16E2^{64} = 16E 26412^{64} - 1

9.3 虚拟内存作为缓存的工具

练习题 9.2

nn P=2pP = 2^p PTE数量
16
32
2202^{20}
2192^{19}

9.6 地址翻译

练习题 9.3

PP VPNVPN 位数 VPOVPO 位数 PPNPPN 位数 PPOPPO 位数
2222 1010 1414 1010
2121 1111 1313 1111
2020 1212 1212 1212
1919 1313 1111 1313

练习题 9.4

A.

1
2
3
13	12	11	10	9	8	7	6	5	4	3	2	1	0
0 0 0 0 1 1 1 1 0 1 0 1 1 1
| VPN | VPO |

B.

参数
VPN 0xf
0X03
0X03
0x0D
0x357

C

1
2
11	10	9	8	7	6	5	4	3	2	1	0
0 0 1 1 0 1 0 1 0 1 1 1

D

参数
0x11
0x5
0xD
0x1D

9.8 内存映射

练习题 9.5

附录

x86寄存器对照表

63 31 15 7
%rax %eax %ax %al 返回值
%rbx %ebx %bx %bl 被调用者保存
%rcx %ecx %cx %cl 第4个参数
%rdx %edx %dx %dl 第3个参数
%rsi %esi %si %sil 第2个参数
%rdi %edi %di %dil 第1个参数
%rbp %ebp %bp %bpl 被调用者保存
%rsp %esp %sp %spl 栈指针
%r8 %r8d %r8w %r8b 第5个参数
%r9 %r9d %r9w %r9b 第6个参数
%r10 %r10d %r10w %r10b 调用者保存
%r11 %r11d %r11w %r11b 调用者保存
%r12 %r12d %r12w %r12b 被调用者保存
%r13 %r13d %r13w %r13b 被调用者保存
%r14 %r14d %r14w %r14b 被调用者保存
%r15 %r15d %r15w %r15b 被调用者保存

二进制、十进制、十六进制对照表

二进制 十进制 十六进制 二进制 十进制 十六进制
0000 0 0 1000 8 8
0001 1 1 1001 9 9
0010 2 2 1010 10 A
0011 3 3 1011 11 B
0100 4 4 1100 12 C
0101 5 5 1101 13 D
0110 6 6 1110 14 E
0111 7 7 1111 15 F