【阅读笔记】深入理解计算机系统

2022-01-12

C-C++

/

课程笔记

/

操作系统

计算机系统漫游#

信息的处理及表示#

2.1 信息存储#

练习 2.2
$n$ $2^n$ （十进制） $2^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

$n$	$2^n$ （十进制）	$2^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

十进制	二进制	十六进制
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

	小端法	大端法
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
0   0   3   5   9   1   4   1
00000000001101011001000101000001
           *********************
  01001010010101100100010100000100
     4   A   5   6   4   5   0   4

练习题 2.7

"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

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

练习题 2.10
步骤 *x *y
$a$ $b$
$a$ $a \oplus b$
$b$ $a \oplus b$
$a$

步骤	*x	*y
	$a$	$b$
	$a$	$a \oplus b$
	$b$	$a \oplus b$
		$a$

练习题 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

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

int bool_equal(int x, int y)
{
    return ~((x & ~y) | (~x & y));
}

C 语言中的移位运算#

左移：
x << n 表示二进制位向左移动 $n$ 位，低位补 $0$ 。
右移：
- 逻辑右移：x >> n 表示二进制位向左移动 $n$ 位，高位补 $0$ 。
- 算术右移：x >> n 表示二进制位向左移动 $n$ 位，若 $x$ 最高位是 $0$ ，则高位补 $0$ ；若 $x$ 最高位是 $1$ ，则高位补 $1$ ；。

练习 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

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 整数表示#

无符号数编码#

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

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

补码编码#

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

\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
$\overrightarrow(x)$ $B2U_4(\overrightarrow{x}))$ $B2T_4(\overrightarrow{x})$
十六进制二进制
0xE $1110$ $2^3 + 2^2 + 2^1 = 14$ $-2^3 + 2^2 + 2^1 = -2$
0x0 $0000$ $0$ $0$
0x5 $0101$ $4+1=5$ $4+1=5$
0x8 $1000$ $8$ $-8$
0xD $1101$ $8 + 4 + 1 = 13$ $-8 + 4 + 1 = -3$
0xF $1111$ $8 + 4 + 2 + 1 = 15$ $-8 + 4 + 2 + 1 = -1$

$\overrightarrow(x)$		$B2U_4(\overrightarrow{x}))$	$B2T_4(\overrightarrow{x})$
十六进制	二进制
0xE	$1110$	$2^3 + 2^2 + 2^1 = 14$	$-2^3 + 2^2 + 2^1 = -2$
0x0	$0000$	$0$	$0$
0x5	$0101$	$4+1=5$	$4+1=5$
0x8	$1000$	$8$	$-8$
0xD	$1101$	$8 + 4 + 1 = 13$	$-8 + 4 + 1 = -3$
0xF	$1111$	$8 + 4 + 2 + 1 = 15$	$-8 + 4 + 2 + 1 = -1$

练习题 2.18
十六进制二进制补码
0x2e0 $0000\ 0010\ 1110\ 0000$ ~~ $2^{10} + 2^8 + 2^7 + 2^6~~ $ 2^{9} + 2^7 + 2^6 + 2^5 = 736$
-0x58 $0000\ 0000\ 0101\ 1000$ ~~2^7 + 2^5 + 2^4~~  $-(2^6 + 2^4 + 2^3) = -40$
0x28
0x30
0x78
0x88
0x1f8
0x8
0xc0
0x48

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

T2U_w(x) \doteq B2U_w(T2B_w(x))

练习题 2.19
$x$ $T2U_4(x)$
$-8$ $8$
$-3$ $13$
$-2$ $14$
$-1$ $15$
$0$ $0$
$5$ $5$

$x$	$T2U_4(x)$
$-8$	$8$
$-3$	$13$
$-2$	$14$
$-1$	$15$
$0$	$0$
$5$	$5$

$\forall x, TMin_w \le x \le TMax_w$

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

$\forall u, 0 \le u \le UMax_w$

\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 ``0x8000 == 0x8000 无符号 ~~0~~ 1
有符号 1
无符号 0
有符号 1
无符号 1

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

扩展一个数字的位表示#

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

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

证明（数学归纳法）：

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])

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 ，即无符号数对 $8$ 取模。
fun2 实现将 32 位有符号 int 转换为 8 位有符号 int ，有符号数的二进制表示取低 $8$ 位，然后进行有符号扩展。

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

截断数字#

无符号数截断：
令向量 $\overrightarrow{x} = [x_{w-1}, x_{w-2}, \dots, x_0]$ ， $\overrightarrow{x}' = [x_{k-1}, \dots, x_0]$ 是将 $\overrightarrow{x}$ 截断 $k$ 位的结果。令 $x = B2T_w(\overrightarrow{x})$ ， $x' = B2T_k(\overrightarrow{x}')$ ，则 $x' = x \ mod \ 2^k$
$\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$
有符号数截断：
$\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)$
其中， $B2U_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
都先将二进制表示转换为无符号数，然后对 $2^k$ 取模截断，所得结果视作 $k$ 位有/无符号数。

十六进制		二进制		无符号		补码
原始值	截断值	原始值	截断值	原始值	截断值	原始值	截断值
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

练习题 2.25
传入的 length 为 $0$ 时，length - 1 为无符号数，值为 ~0x0 ，比较 i 与 length - 1 的大小时，i 会被转换为无符号数将其比较，设 length 是一个 k 位无符号数，则 i 若视作无符号数，表示范围为 $[0, 2^k - 1]$ 或 $[0, 2^32 - 1]$ ，总之 a[i] 将出现越界访问，导致内存错误。
解决方法是第 $4$ 行修改为 for(int i=0; i <= (int)length - 1; i++)

练习 2.26
A.
s 比 t 短时，结果不正确。
B.
在 A. 的条件下， strlen(s) - strlen(t) 仍是一个无符号正整数，右边的 0 将被视作无符号数，返回真。
int strLonger(char *s, char *t)
{
        return strlen(s) > strlen(t);
}

2.3 整数的运算#

练习 2.27

int uadd_ok(unsigned x, unsigned y)
{
        return x + y >= x;
}

练习题 2.28
$x$ $-_4^ux$
十六进制十进制十进制十六进制
0 0 16 0 0
5 5 11 B
8 8 8 8
D 13 13 3 D
F 15 1 1

$x$		$-_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
$x$ $y$ $x+y$ $x + _t^5y$ 情况
$[100101]$   $-27$ $[00101]$ 情况3 1
$[110000]$   $-16$ $[10000]$ 情况 2
~~$[011111]$~~ $[111111]$   ~~$31$~~ $-1$ $[11111]$ 情况1 2
$[000111]$   $7$ $[00111]$ 情况 3
$[010000]$   $16$ $[10000]$ 情况 4

$x+y$	$x + _t^5y$	情况
$[100101]$ `<br>` $-27$	$[00101]$	情况3 1
$[110000]$ `<br>` $-16$	$[10000]$	情况 2
~~$[011111]$~~ $[111111]$ `<br>` ~~$31$~~ $-1$	$[11111]$	情况1 2
$[000111]$ `<br>` $7$	$[00111]$	情况 3
$[010000]$ `<br>` $16$	$[10000]$	情况 4

练习题 2.30

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^k ， sum - x = y - 2^k ，在模 $k$ 意义下就是 $y$ ，对 $x$ 同理，所以正溢出时仍然返回真；同理，负溢出也返回真。

练习题 2.32
用 tadd_ok(int x, int y) 来判断 $x - y$ 是否溢出：
int tsub_ok(int x, int y)
{
	return tadd_ok(x, -y);
}
这种写法是在假设：对任意 $x - ^t_wy$ ，若 tsub_ok(x, y) 判断没有溢出，即 $x + ^t_w(-y)$ 由 tadd_ok(x, -y) 判断没有溢出，这要求 $-^t_wy = -y$ ，但其实不然。
$y = TMin_w = -2^{w-1}$ 时， $-^t_wy = TMin_w = y$ ，若 $x < 0$ ，则 $x - y = x + 2^{w-1} \ge 0$ ，没有发生溢出，但是 $x + TMin_w = x - 2^{w-1} < 2^{w-1}$ ，将被 tadd_ok() 判断为负溢出；若 $x > 0$ ， $x - y = x + 2^{w-1} > 2^{w-1} - 1$ ，发生正溢出，而 $x + TMin_w = x - 2^{w-1} > 2^{w-1}$ ，被 tadd_ok() 判断为没有溢出。
解决方法：
int tsub_ok(int x, int y)
{
 if(y == -y) return x < 0;
	else return tadd_ok(x, -y);
}

练习题 2.33
$x$ $-^t_4x$
十六进制十进制十进制十六进制
0 0 0 0
5 5 -5 B
8 8 -8 8 -8 8
D -3 3 3
F -1 1 1

$x$		$-^t_4x$
十六进制	十进制	十进制	十六进制
0	0	0	0
5	5	-5	B
8	8 -8	8 -8	8
D	-3	3	3
F	-1	1	1

无符号乘法#

对满足 $0 \le x,\ y \le UMax_w$ 的 $x$ 和 $y$ ：

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

有符号乘法#

对满足 $TMin_w \le x,\ y \le TMax_w$ 的 $x$ 和 $y$ ：

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

练习题 2.34
模式 $x$ $y$ $x \cdot y$ 截断
$[100]$ $[101]$
无符号 $4$ $5$ $20$   $[010100]$ $[100]$
有符号 $-4$ $-3$ $12$   $[001100]$ $[100]$
$[010]$ $[111]$
有符号 $2$ $7$ $14$   $[001110]$ $[110]$
无符号 $2$ $-1$ $-2$   $111110$ $[110]$
$[110]$ $[110]$
有符号 $6$ $6$ $36$   $[100100]$ $[100]$
无符号 $-2$ $-2$ $4$   $[000100]$ $[100]$

模式	$x$	$y$	$x \cdot y$	截断
	$[100]$	$[101]$
无符号	$4$	$5$	$20$ `<br>` $[010100]$	$[100]$
有符号	$-4$	$-3$	$12$ `<br>` $[001100]$	$[100]$
	$[010]$	$[111]$
有符号	$2$	$7$	$14$ `<br>` $[001110]$	$[110]$
无符号	$2$	$-1$	$-2$ `<br>` $111110$	$[110]$
	$[110]$	$[110]$
有符号	$6$	$6$	$36$ `<br>` $[100100]$	$[100]$
无符号	$-2$	$-2$	$4$ `<br>` $[000100]$	$[100]$

练习题 2.35
由有符号数乘法的定义，设 $z = x \cdot y$ ， $T2B_{w}(z\ mod\ 2^w) = [x_{w-1}, \dots , x_0]$ ，则 $p = (z\ mod\ 2^w) - x_{w-1} 2^{w}$ ，所以 $p + x_{w-1} 2^{w} = z\ mod\ 2^w$ ，即 $x \cdot y = z = k 2^w + p + x_{w-1}2^w = p + t2^w$ 。
若计算溢出，则 $k \neq 0$ ，又 $x_{w-1} \in \{0, 1\}$ ，故 $t = k + x_{w-1} \neq 0$
若 $t = k + w_{w-1} \neq 0$ ，由于 $k \ge 0$ ，且 $x_{w-1} \in \{0, 1\}$ ，有 $k \neq 0$ ，所以 $z \ge 2^w$ ，计算溢出。
若 $p \le x$ ，则令 $q = 1$ ， $\exist\ r = x - p , \ s.t. p = xp + r$ .
若 $p > x$ ，则令 $r = p\ mod\ x$ ， $\exist\ r = x - p , \ s.t. p = xp + r$ .
若 $q = y$ ，则由 $|r| < |x|$ ，且 $|x| < 2^w$ ，所以 $t = 0$ ， $p = x \cdot y$ ， $r = 0$ 。
若 $r = t = 0$ ，则 $p = x \cdot y$ ，易得 $q = y$ 。
综上，若没有溢出，则 $t = 0$ ，此时 $p = x \cdot y$ ，!x || p / x == y 为真。

练习 2.36

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.
if(asize != (unit32_t)asize) return NULL;

乘以常数#

x<<k = x \cdot 2^k

将 $K$ 分解为二进制序列 $[x_{w-1}, \dots, x_0]$ ，则有：

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
可以计算 $a \cdot 2^k$ ， $a \cdot (2^k + 1)$ 等，即 $1, 2, 3, 4, 5, 8, 9$

练习题 2.39
$n$ 为最高位时， ~~x<<(n + 1) = $x \cdot (2^{n + 1}) = x \cdot 2^{n} \cdot x$~~ $n+1 = w-1+1 = w$ ， $x<<(n+1) = x<<w$ ，溢出截断后为 ~~$x$~~ $0$ 本身。故改为 ~~x - (x << m)~~ - (x << m)

练习题 2.40
$K$ 移位加法/减法表达式
(x<<3) - (x<<1)
(x<<5) - x
(x<<1) - (x<<3)
(x<<6) - (x<<3) - x

练习题 2.41
视加减法、移位计算的开销决定，选择综合开销最小的那种。

除以 2 的幂#

若 $x$ 是无符号数：

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

此处使用逻辑右移。

若 $x$ 是有符号数且大于 $0$ ，操作与无符号数相同，但使用算术右移。

若 $x$ 是有符号数且小于 $0$ ，除以 $2^k$ 时，要先加上偏置位 $2^k-1$ ，再算术右移：

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

练习题 2.42

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 最低三位是 111 ，x 是 $32$ 位 int ，x << 29 的最高三位是 111 ，故其小于 $0$
C. $x \cdot x$ 的最高位恒为 $0$ ，因此 x * x >= 0
D. 若 x >= 0 ，则根据有符号数的逆元定义，-x <= 0
E. 若 $x = TMin_w$ ， $-x = TMin_w < 0$ ，故为假
F. $x = y = 2^{31} - 1$ 时，不成立
G. $?$

2.4 浮点数#

二进制小数#

练习题 2.45
小数值二进制十进制
$\frac 1 8$ $0.001$
$\frac 3 4$
$\frac {43} {16}$ $10.1011$ $2.6875$
$1.001$
$\frac {63} 8$ $101.111$ $5.875$
$3.1875$

练习题 2.46
A. 是 0.000000000000000000000[0011]
B. $\frac 3 {15 \cdot 2^{21}}$
C. $0.0171661377s$
D. $34.3322753906m$

浮点数的表示#

$IEEE$ 用 $V = (-1)^s \times M \times 2^E$ 表示一个浮点数。

$s$ 编码符号位， $0$ 为正， $1$ 为负。
$k$ 位阶码，表示一个二进制整数 $e = e_{k-1} \dots e_0$ ，用来编码 $E$
$n$ 位小数字段，表示一个二进制小数 $f = \overline{0.f_{n-1} \dots f_0}$ ，用来编码 $M$

情况 1：规格化的值

$e$ 的所有位不全为 $1$ 或 $0$
$E = e - Bias$ ，其中 $Bias = 2^{k-1} - 1$ ，使得双精度指数范围为 $-1022 \backsim 1023$ ，单精度为 $-126 \backsim 127$
$M = 1+ f = \overline{1.f\_{n-1} \dots f_0}$

情况 2：非规格化的值

阶码字段 $e$ 所有位全为 $0$ ，即 $e = 0$

$E = 1 - Bias$
$M = f = \overline{0.f_{n-1} \dots f_0}$

$M = f = 0$ 时根据 $s$ 的取值决定表示 $+0.0$ 或 $-0.0$ ，二者有时候是不同的。

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

情况 3：特殊值

阶码字段 $e$ 所有位全为 $1$

若 $f = 0$ ，表示 $+\infin$ 或 $-\infin$
$f \neq 0$ 表示 $NaN$ （Not a number）

练习题 2.47
位 $e$ $E$ $2^E$ $f$ $M$ $2^E \times M$ $V$ 十进制
0 00 00 $0$ $-1$ $\frac 1 2$ $\frac 0 4$ $\frac 0 4$ $\frac 0 8$ $0$ $0$
0 00 01 $0$ $-1$ $\frac 1 2$ $\frac 1 4$ $\frac 1 4$ $\frac 1 8$ $\frac 1 8$ $0.125$
0 00 10 $0$ $-1$ $\frac 1 2$ $\frac 2 4$ $\frac 2 4$ $\frac 2 8$ $\frac 1 4$ $0.25$
0 00 11 $0$ $-1$ $\frac 1 2$ $\frac 3 4$ $\frac 3 4$ $\frac 3 8$ $\frac 3 8$ $0.375$
0 01 00 $1$ $0$ $1$ $\frac 0 4$ $\frac 4 4$ $\frac 4 4$ $1$ $1$
0 01 01 $1$ $0$ $1$ $\frac 1 4$ $\frac 5 4$ $\frac 5 4$ $\frac 5 4$ $1.25$
0 01 10 $1$ $0$ $1$ $\frac 2 4$ $\frac 6 4$ $\frac 6 4$ $\frac 3 2$ $1.5$
0 01 11 $1$ $0$ $1$ $\frac 3 4$ $\frac 7 4$ $\frac 7 4$ $\frac 7 4$ $1.75$
0 10 00 $2$ $1$ $2$ $\frac 0 4$ $\frac 4 4$ $\frac 8 2$ $4$ $4$
0 10 01 $2$ $1$ $2$ $\frac 1 4$ $\frac 5 4$ $\frac {10} 2$ $5$ $5$
0 10 10 $2$ $1$ $2$ $\frac 2 4$ $\frac 6 4$ $\frac {12} 2$ $6$ $6$
0 10 11 $2$ $1$ $2$ $\frac 3 4$ $\frac 7 4$ $\frac {14} 2$ $7$ $7$
0 11 00 $-$ $-$ $-$ $-$ $-$ $-$ $-$ $-$
0 11 01 $-$ $-$ $-$ $-$ $-$ $-$ $-$ $-$
0 11 10 $-$ $-$ $-$ $-$ $-$ $-$ $-$ $-$
0 11 11 $-$ $-$ $-$ $-$ $-$ $-$ $-$ $-$

位	$e$	$E$	$2^E$	$f$	$M$	$2^E \times M$	$V$	十进制
`0 00 00`	$0$	$-1$	$\frac 1 2$	$\frac 0 4$	$\frac 0 4$	$\frac 0 8$	$0$	$0$
`0 00 01`	$0$	$-1$	$\frac 1 2$	$\frac 1 4$	$\frac 1 4$	$\frac 1 8$	$\frac 1 8$	$0.125$
`0 00 10`	$0$	$-1$	$\frac 1 2$	$\frac 2 4$	$\frac 2 4$	$\frac 2 8$	$\frac 1 4$	$0.25$
`0 00 11`	$0$	$-1$	$\frac 1 2$	$\frac 3 4$	$\frac 3 4$	$\frac 3 8$	$\frac 3 8$	$0.375$
`0 01 00`	$1$	$0$	$1$	$\frac 0 4$	$\frac 4 4$	$\frac 4 4$	$1$	$1$
`0 01 01`	$1$	$0$	$1$	$\frac 1 4$	$\frac 5 4$	$\frac 5 4$	$\frac 5 4$	$1.25$
`0 01 10`	$1$	$0$	$1$	$\frac 2 4$	$\frac 6 4$	$\frac 6 4$	$\frac 3 2$	$1.5$
`0 01 11`	$1$	$0$	$1$	$\frac 3 4$	$\frac 7 4$	$\frac 7 4$	$\frac 7 4$	$1.75$
`0 10 00`	$2$	$1$	$2$	$\frac 0 4$	$\frac 4 4$	$\frac 8 2$	$4$	$4$
`0 10 01`	$2$	$1$	$2$	$\frac 1 4$	$\frac 5 4$	$\frac {10} 2$	$5$	$5$
`0 10 10`	$2$	$1$	$2$	$\frac 2 4$	$\frac 6 4$	$\frac {12} 2$	$6$	$6$
`0 10 11`	$2$	$1$	$2$	$\frac 3 4$	$\frac 7 4$	$\frac {14} 2$	$7$	$7$
`0 11 00`	$-$	$-$	$-$	$-$	$-$	$-$	$-$	$-$
`0 11 01`	$-$	$-$	$-$	$-$	$-$	$-$	$-$	$-$
`0 11 10`	$-$	$-$	$-$	$-$	$-$	$-$	$-$	$-$
`0 11 11`	$-$	$-$	$-$	$-$	$-$	$-$	$-$	$-$

练习题 2.49
A. $2^{n+1} + 1$
B. $2^{24} + 1$

舍入#

练习题 2.50
A. $10.0_2$
B. ~~$10.0_2$~~ $10.1_2$
C. ~~$11.00_2$~~ $11.0_2$
D. $11.0_2$

练习题 2.51
A. $0.00011001100110011001100[1100]_2$ 精确到小数点右边 $23$ 位，使用舍入到偶数方法得 $0.0.00011001100110011001101$
B. $x' - 0.1 = 0.00000000000000000000000[0011] = 0.1 \cdot 2^{-22}$
C. $60 \cdot 60 \cdot 100 \cdot 10 0.2 \cdot 2^{-22} = 0.086$
D. $0.086 \cdot 2000 = 171.67$

练习题 2.52
格式 A 格式 B
位值位值
011 0000 $1$ 0111 000 $1$
101 1110 $2^{2} \times 1.1110_2$ 1001 111 $2^2 \times 1.111_2$
010 1001 $2^{-1} \times 1.1001_2$ 0110 100 $2^{-1} \times 1.100_2$
110 1111 $2^3 \times 1.1111_2$ 1011 000 $2^{4} \times 1.000_2$
000 0001 $2^{-2} \times 0.0001$ 0001 000 $2^{-6} \times 1.000_2$

格式 A		格式 B
位	值	位	值
`011 0000`	$1$	`0111 000`	$1$
`101 1110`	$2^{2} \times 1.1110_2$	`1001 111`	$2^2 \times 1.111_2$
`010 1001`	$2^{-1} \times 1.1001_2$	`0110 100`	$2^{-1} \times 1.100_2$
`110 1111`	$2^3 \times 1.1111_2$	`1011 000`	$2^{4} \times 1.000_2$
`000 0001`	$2^{-2} \times 0.0001$	`0001 000`	$2^{-6} \times 1.000_2$

练习题 2.53

#define POS_INFINITY 0x7FF0000000000000
#define NEG_INFINITY 0xFFF0000000000000
#define NEG_ZERO 0x8000000000000000

练习题 2.54
A. int 转 double 没有精度丢失，再转回来也没事
B. x = 0x7fffffff 时，转成 float 会舍入，精度下降，甚至比 x 大的值，再转回 int 会溢出
C. double 转 float 精度会丢失
D. float 转 double 精度不会丢失
E. 浮点数取加法逆元只需要把符号位取反即可，取两次加法逆元符号不变
F. 两侧都会变成 double/double ，且 int 转 double 精度不丢失，所以值相等
G. 浮点数取平方，一定为正数，且大于等于 $0$
H. 若 f + d 溢出 double 最大规格化数值成 inf ，则 f + d - f 为 inf

第 3 章程序的机器级表示#

3.4 访问信息#

x86_64 寄存器：

格式为 $Immm(r_b, r_i, 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

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

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

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

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

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

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. $T_{mp} = 2 \times (T_{ran} - T_{ok}) , \ T_{ok} = 16, \ T_{ran} = 31 \to T_{mp} = 30$

B. $30 + 16 = 46$

练习题 3.20

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

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;
    }
}

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.

%rax -> x
%rcx -> y
%rdx -> n

B.

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

C.

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

long loop_while(long a, long b)
{
    long result = 1;
    while(a > b)
    {
        result *= a + b;
        a++;
    }
    return result;
}

练习题 3.25

long loop_while2(long a, long b)
{
    long result = b;
    while(b > 0)
    {
        result *= a;
        b -= a;
    }
    return result;
}

练习题 3.26

long fun_a(unsigned long x)
{
    long val = 0;
    while(x != 0)
    {
        val ^= x;
        x >>= 1;
    }
    return val & 0x1;
}

练习题 3.27

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

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.

long sum = 0;
long i = 0;
while(i < 10)
{
    if(i & 1) continue;
    sum += i;
    i++;
}

B.

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.

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

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. 因为被调用者保存寄存器总共只有 $6$ 个

练习题 3.35

A. 是参数 x

B.

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

数组	元素大小	整个数组的大小	起始地址	元素 $i$
`s`	$2$	$14$	$x_s$	$x_s + 2i$
`T`	$8$	$24$	$x_T$	$x_T + 8i$
`U`	$8$	$48$	$x_U$	$x_U + 8i$
`V`	$4$	$32$	$x_V$	$x_v+4i$
`w`	$8$	$32$	$x_w$	$x_w+8i$

练习题 3.37


`short*`	$x_s+2$	`leal 2(%rdx), %rax`
`short`	$M[x_s+6]$	`mov 6(%rdx), %al`
`short*`	$x_s+2i$	`leal (%rdx, %rcx, 2), %rax`
`short`	$M[x_s+8i+2]$	`mov 2(%rdx, %rcx, 8), %al`
`short*`	$x_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

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.

void sp_init(struct prob *sp)
{
    sp->s.x = sp->s.y;
    sp->p = &(sp->s.x);
    sp->next = sp;
}

练习题 3.42

A.

long fun(struct ELE *ptr)
{
    int result = 0;
    while(ptr != NULL)
    {
        result += ptr->v;
        prt = ptr->p;
    }
    return result;
}

B.

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

练习题 3.43

$expr$	$type$	代码

	`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.

0	4	8	12
i	c	j	d

B.

0	4	5	8
i	c	d	j

C.

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

D.

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.

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

练习题 3.45

A.

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.

$52$

C.

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

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

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

练习题 3.46

A.

00 00 00 00 00 40 00 76		返回地址
01 23 45 67 89 AB CD EF		%rbx
							
							<- buf = %rsp

B.

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. 大约 $2^{13}$ 个

B. 128 字节即 $2^7$ ，使得只需要 $2^6 = 64$ 次尝试。

练习题 3.48

A.

不带保护：

buf 在 %rsp ，v 在 %rsp+24

带保护：

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

B.

v 比 buf 更靠近栈顶，使得溢出更不容易影响到 buf

练习题 3.49

A.

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

B.

先将 %rsp 加 $7$ ，而后除以 $8$ 再乘以 $8$ ，可向上舍入到最近的 $8$ 的倍数，得到 p 的值。

C.

对应最大化与最小化 $e_1$ $e_2$ 的情况。

D.

实现 $s_2$ 的 $16$ 字节对齐， $p$ 的 $8$ 字节对齐。

第 4 章处理器的体系结构#

4.1 Y86-64 指令集体系结构#

练习题 4.1

0x100: 30f30f00000000000000
0x10a: 2031
0x10c: 4013fdffffffffffffff
0x116: 6231
0x118: 70c010000000000000

练习题 4.2

A.

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

B.

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

练习题 4.4

.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

.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

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

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

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

练习题 4.10

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

练习题 4.11

word Min3 = [
    A <= B && A <= C: A;
    B <= C : B;
    1 : C;
]

练习题 4.12

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

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

练习题 4.20

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

练习题 4.22

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

练习题 4.24

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. C 与 D 之间，延迟为 $380ns$ ，一个时钟周期为 $190ns$

B.

练习题 4.29

A.

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

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

B.

$1 / 20 * 10^9 = 50\ GIPS$

4.5 Y86-64 d的流水线实现#

第 5 章优化程序性能#

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

练习题 5.1

若 xp 和 yp 在同一个位置。

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	$1$	$91$	$90$	$90$
B	$91$	$1$	$90$	$90$
C	$1$	$1$	$90$	$90$

练习题 5.4

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

B. 与 combine3 行为相同。

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

练习题 5.5

A.

加法： $n$ 次

乘法： $2n$ 次

B.

乘法： $n$ 次

5.9 提高并行性#

**练习题 5.8 ? **

A1: $15.0$

A2: $10.0$

A3: $5.0$

A4: $5.0$

A5: $10.0$

5.11 一些限制因素#

练习题 5.9

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

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

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

$r$	$c$	$b_r$	$b_c$	`max(b_r, b_c)`
$4$	$4$	$2$	$2$	$2$
$4$	$4$	$2$	$2$	$2$
$16$	$8$	$4$	$3$	$4$
$32$	$16$	$5$	$4$	$5$
$32$	$32$	$5$	$5$	$5$

练习题 6.2

$512 \times 400 \times 10000 \times 2 \times 2 = 8.192GB$

练习题 6.3

平均旋转延迟： $1/2 \times (60/15000) \times 1000ms = 2ms$

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

总时间： $8 + 2 + 0.008 = 10ms$

练习题 6.4

A.

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

旋转一圈时间： $60 / 10000 \times 1000ms = 6ms$

总时间： $5 + 6/2 + 2 \times 6 = 20ms$

B.

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

共 $8 \times 2000 = 16000ms$

练习题 6.5

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

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

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

练习题 6.6

$1PB = 10^6GB$

每 GB 价格 $500 / 10^6$

大约 $2025$ 年可以实现。

6.2 局部性#

练习题 6.7

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

练习题 6.8

设 $N = 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

地址	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

地址	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

地址	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 以步长为 $3$ 转跳，clear3 以步长为 $6$ 转跳。

6.4 高速缓存存储器#

练习题 6.9

高速缓存	$S$	$t$	$s$	$b$
1.	$256$	$22$	$8$	$2$
2.	$64$	$23$	$5$	$3$
3.	$1$	$27$	$0$	$5$

练习题 6.10

由于消除了抖动，下列标记为 $1$ 的是命中的， $0$ 为不命中。

	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\%$

练习题 6.11

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

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

练习题 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

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. $512$

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

C. $50\%$

练习题 6.20

A. $512$

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

C. $50\%$

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

练习题 6.21

A. $512$

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

C. $25\%$

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

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

练习题 6.21

由图可知， $L1$ 峰值为 $12000MB/s$ ，每秒读 $12000 / 8$ 次，每秒周期数 $2100M$ ，得 $21000 / 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.

gcc p.o libx.a

B.

gcc p.o lilbx.a liby.a

C.

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

bacc 或 abcc 或 acbc

练习题 8.4

A. $6$ 行

B.

设子进程id为123

Hello
0
Bye
1
2
Bye

练习题 8.5

#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

#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

#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

第 9 章虚拟内存#

9.2 地址空间#

练习题 9.1

虚拟地址位数	虚拟地址数	最大可能虚拟地址数
	$2^8 = 256$	$255$
$16$		$2^{16} - 1$
$32$	$2^{32} = 4G$
$48$		$2^{48} - 1$
$64$	$2^{64} = 16E$	$2^{64} - 1$

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

练习题 9.2

$n$	$P = 2^p$	PTE数量
		16
		32
		$2^{20}$
		$2^{19}$

9.6 地址翻译#

练习题 9.3

$VPN$ 位数	$VPO$ 位数	$PPN$ 位数	$PPO$ 位数
$22$	$10$	$14$	$10$
$21$	$11$	$13$	$11$
$20$	$12$	$12$	$12$
$19$	$13$	$11$	$13$

练习题 9.4

A.

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

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

计算机系统漫游#

信息的处理及表示#

2.1 信息存储#

寻址和字节顺序#

C 语言中的移位运算#

2.2 整数表示#

无符号数编码#

补码编码#

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

扩展一个数字的位表示#

截断数字#

2.3 整数的运算#

无符号乘法#

有符号乘法#

乘以常数#

除以 2 的幂#

2.4 浮点数#

二进制小数#

浮点数的表示#

舍入#

第 3 章 程序的机器级表示#

3.4 访问信息#

3.7 过程#

3.8 数组#

3.9 异质的数据结构#

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

第 4 章 处理器的体系结构#

4.1 Y86-64 指令集体系结构#

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

4.3 Y86-64 的顺序实现#

4.4 流水线的通用原理#

4.5 Y86-64 d的流水线实现#

第 5 章 优化程序性能#

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

5.4 消除循环的低效率#

5.9 提高并行性#

5.11 一些限制因素#

第 6 章 存储器层次结构#

6.1 存储技术#

6.2 局部性#

6.4 高速缓存存储器#

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

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

第 7 章 链接#

7.5 符号和符号表#

7.6 符号解析#

第 8 章 异常控制流#

8.2 进程#

8.4 进程控制#

第 9 章 虚拟内存#

9.2 地址空间#

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

9.6 地址翻译#

9.8 内存映射#

附录#

第 3 章程序的机器级表示#

第 4 章处理器的体系结构#

第 5 章优化程序性能#

第 6 章存储器层次结构#

第 7 章链接#

第 8 章异常控制流#

第 9 章虚拟内存#