当前位置：首页 > article >正文

SCAU期末笔记 - 计算机系统基础考纲习题

article 2025/1/4 10:30:16

写在前面：说是考试范围不超过考纲知识点，但我觉得考纲里面画出来的题目至少也得抽几道原题吧。就算抽不到的话那这些学会肯定没啥坏处，所以这就是我们CSAPP的第一篇（也可能是最后一篇）复习笔记。

第二章信息的表示和处理

掌握不同进制数之间的转换

练习题2.4

练习题2.4
A. 先算c+8，c就是12，所以c+8就是20，满16进位，所以答案是0x5044。
B. 从低位开始算，不够就借1变16，算出来是0x4ffc。
C. 注意这个64是十进制，转成16进制就是0x40，算得答案是0x507c。
D. 同上，算得答案0x00ae。

掌握布尔运算，C语言中的位级运算、逻辑运算和移位运算

练习题2.8

练习题2.8
做算法题最讨厌的按位运算，其中
~是按位取反，也就是1变0,0变1；
&是按位与，全为1结果才为1；
|是按位或，全为0结果才为0；
^是按位异或，相同为1，不同为0。

故答案分别为10010110、10101010、01000001、01111101和00111100。

练习题2.14

练习题2.14
首先转成二进制，x和y分别为01100110和00111001

x&y=00100000即0x20
x|y=01111111即0x7f
~x=10011001，~y=11000110，则~x|~y=11011111即0xdf
!y=00000000，x&!y=00000000，即0x00
注意区别和运算与按位与，这里是0x01
区别或运算和按位或，这里是0x01
同上，这里是纯粹的逻辑判断，答案是0x00
先求~y=11000110不为0，所以答案是0x01

练习题2.16

练习题2.16
首先我们主要要区分逻辑右移和算数右移，前者是直接补0，后者看原本第1位是什么就补什么

$(x)$ （十六进制）	$(x)$ （二进制）	$(x << 3)$ （二进制）	$(x << 3)$ （十六进制）	$(x >> 2)$ （逻辑的，二进制）	$(x >> 2)$ （逻辑的，十六进制）	$(x >> 2)$ （算术的，二进制）	$(x >> 2)$ （算术的，十六进制）
$(0\times C3)$	$(11000011)$	$(10000110)$	$(0\times86)$	$(00110000)$	$(0\times30)$	$(11110000)$	$(0\times F0)$
$(0\times75)$	$(01110101)$	$(11010100)$	$(0\times D4)$	$(00011101)$	$(0\times1D)$	$(00011101)$	$(0\times1D)$
$(0\times87)$	$(10000111)$	$(00111000)$	$(0\times38)$	$(00100001)$	$(0\times21)$	$(11100001)$	$(0\times E1)$
$(0\times66)$	$(01100110)$	$(10011000)$	$(0\times98)$	$(00011001)$	$(0\times19)$	$(00011001)$	$(0\times19)$

家庭作业2.61

家庭作业2.61
最讨厌这种题了，尼玛老老实实按位遍历会死吗？算了反正就几道，直接背答案吧破防了
A. !(x & (~x + 1))
B. !(x ^ (x<<1))
C. !((x & 0xFF) & (~0xFF + 1))
D. !((x>>24)^((x>>24)<<1))

掌握补码编码以及有符号数和无符号数之间的转换，理解强制类型转换影响关系运算的结果

练习题2.17

练习题2.17
首先 $w$ 指的是字节数， $w = 4$ 也就意味着四个字节， $B2U_w(\vec{x})$ 和 $B2T_w(\vec{x})$ 分别指无符号数和补码，怎么计算呢？
无符号数就是正常的所有位加权加起来，比如1111就是 $1\times2^0+1\times2^1+1\times2^2+1\times2^3$ ；
补码就是所有位加权但是最高位额外乘上-1，即 $1\times2^0+1\times2^1+1\times2^2-1\times2^3$ 。
知道了上面的知识，表格也就不难填了

$\vec{x}$ 十六进制	$\vec{x}$ 二进制	$B2U_4\vec{x}$	$B2T_4\vec{x}$
$0\times E$	$[1110]$	$2^3 + 2^2 + 2^1 = 14$	$2^3 + 2^2 + 2^1 = -2$
$0\times0$	$[0000]$	$2^0 = 1$	$0$
$0\times5$	$[0101]$	$2^2 + 2^0 = 5$	$2^2 + 2^0 = 5$
$0\times8$	$[1000]$	$2^3 = 8$	$2^3 = -8$
$0\times D$	$[1101]$	$2^3 + 2^2 + 2^0 = 13$	$2^3 + 2^2 + 2^0 = -3$
$0\times F$	$[1111]$	$2^3 + 2^2 + 2^1 + 2^0 = 15$	$2^3 + 2^2 + 2^1 + 2^0 = -1$

练习题2.19

练习题2.19
先参考上一题的写出二进制表示，然后直接算无符号数即可
$B$ 代表二进制， $T$ 代表补码， $U$ 代表无符号数，2就是前者转化为后者的意思，所以主要看后面是什么就行

十进制（补码）	二进制（补码）	$T2U_4(\vec{x})$
-8	1000	8
-3	1101	13
-2	1110	14
-1	1111	15
0	0000	0
5	0101	5

练习题2.21

左边默认的int类型，int的最小值-1变成了-2147483648，为了与右边的unsigned int比较临时转成unsigned int发现刚好相等，所以类型分别是int和unsigned int，求值为1
同上，左边是-2147483648，右边是2147483647，都是int类型，直接对比即可，所以类型分别是int和int，求值为1
现在左边是2147483648U，右边为了比较强制转换为2147483647U，所以左边大于右边，所以类型分别是unsigned int和int，求值为0
左边还是-2147483648，小于右边，没有任何问题，所以类型分别是int和int，求值为1
左边是2147483648U，右边强制转换为unsigned int类型用于对比，为2147483649U，所以左边小于右边，所以类型分别是unsigned int和int，求值为1

练习题2.25

错误原因
这段代码中 for 循环的条件是 i <= length - 1，当 length 为 0 时，length - 1 会发生无符号整数下溢，在无符号整数运算中，0 - 1 的结果是 4294967295（假设是 32 位系统），所以循环会执行 4294967295 + 1 次，导致 i 会超出数组 a 的合法索引范围，从而引发内存错误，因为它试图访问不存在的数组元素。
修改方法
将 for 循环的条件改为 i < length，这样当 length 为 0 时，循环一次都不会执行，直接返回 result 的初始值 0.0，避免了内存错误。

修改后的代码如下：

/* WARNING: This is buggy code */
float sum_elements(float a[], unsigned length) {
    int i;
    float result = 0;

    for (i = 0; i < length; i++)
        result += a[i];
    return result;
}

练习题2.26

练习题2.26
A. 在什么情况下，这个函数会产生不正确的结果？
当 strlen(s) < strlen(t) 时，函数可能会产生不正确的结果。例如，当 strlen(s) = 5，strlen(t) = 10 时，strlen(s) - strlen(t) 在无符号整数运算中会得到一个很大的正数（因为无符号整数不会出现负数，而是会发生下溢），从而导致 strlen(s) - strlen(t) > 0 的判断结果错误。

B. 解释为什么会出现这样不正确的结果。
原因是 strlen 函数返回的 size_t 类型被定义为 unsigned int（无符号整数）。当进行 strlen(s) - strlen(t) 运算时，如果 strlen(s) < strlen(t)，在无符号整数运算中，结果不是负数，而是会发生下溢，得到一个很大的正数。例如，假设 unsigned int 是 32 位，strlen(s) = 1，strlen(t) = 2，那么 1 - 2 在无符号整数运算中实际上是 2^32 - 1，这个值远大于 0，所以会导致函数返回错误的结果，即本来应该返回 0（表示 s 的长度不大于 t 的长度），但却返回了 1（表示 s 的长度大于 t 的长度）。

C. 说明如何修改这段代码好让它能可靠地工作。

int strlonger(char *s, char *t) {
    return strlen(s)>strlen(t);
}

家庭作业2.72

家庭作业2.72
A. 因为sizeof(val)是unsigned int类型，所以条件判断的左边得到的结果总是unsigned int，那就 $\geq 0$ 就永远成立，所以总是成功。
B. 将条件判断中的sizeof(val)前面加上一个强制类型转换，变成(int)(sizeof(val))即可。

理解无符号数与补码数扩展、截断的基本规则

练习题2.22

练习题2.22
对于一个 $w$ 位的补码表示的数 $x$ ，其值可以通过以下方式计算：
如果 $x$ 为正数或 $0$ ，其值就是二进制位对应的无符号数的值；
如果 $x$ 为负数，其值为 $-2^{w - 1} + \sum_{i = 0}^{w - 2} x_i \times 2^i$ ，其中 $x_i$ 是二进制位向量中的第 $i$ 位（从右往左数，最右边是第 $0$ 位）。

A. $[1011]$
这里 $w = 4$ ，是一个负数（因为最高位是 $1$ ）。
根据公式计算其值为：
$-2^{4 - 1} + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = -8 + 2 + 1 = -5$
B. $[11011]$
这里 $w = 5$ ，是一个负数（因为最高位是 $1$ ）。
计算其值为：
$-2^{5 - 1} + 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = -16 + 8 + 2 + 1 = -5$
C. $[111011]$
这里 $w = 6$ ，是一个负数（因为最高位是 $1$ ）。
计算其值为：
$-2^{6 - 1} + 1 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = -32 + 16 + 8 + 2 + 1 = -5$

从上面的计算可以看出，这三个位向量按照补码的计算规则都表示 $- 5$ 。并且后两个位向量可以通过对第一个位向量 $[1011]$ 进行符号扩展得到，即在左边添加 $1$ 来扩展位数，而数值保持不变（在补码表示中，负数的符号扩展是在左边添加 $1$ ）。

练习题2.24

练习题2.24
计算方法就是直接转成二进制，截断顾名思义就是把左边的一部分直接去掉，去掉之后再直接用响应的计算规则分别算成无符号数和补码数即可。

十六进制	十六进制	无符号	无符号	补码	补码
原始值	截断值	原始值	截断值	原始值	截断值
0	0	0	0	0	0
2	2	2	2	2	2
9	1	9	1	-7	1
B	3	11	3	-5	3
F	7	15	7	-1	7

理解无符号数加法和补码加法的联系与区别

图2-25

图2-25
表格里的情况的含义课本上文也有解释，直接po原文吧
补码加法可能出现的四重情况的解释

练习题2.29

$x$	$y$	$x + y$	$x +_5^t y$	情况
`[10100]`	`[10001]`	`-27`	`[00101]`	负溢出（情况1）
`[11000]`	`[11000]`	`-16`	`[10000]`	无溢出（情况2）
`[10111]`	`[01000]`	`-1`	`[11111]`	无溢出（情况3）
`[00010]`	`[00101]`	`7`	`[00111]`	无溢出（情况4）
`[01100]`	`[00100]`	`16`	`[10000]`	正溢出（情况1）

掌握采用移位和加法运算的组合来代替乘以常数因子的乘法

练习题2.40

$K$	移位	加法/减法	表达式
$6$	$2$	$1$	$x << 2 + x << 1$
$31$	$1$	$1$	$x << 5 - x$
$- 6$	$2$	$1$	$- (x << 2 + x << 1)$
$55$	$2$	$2$	$(x << 5 + x << 4) + (x << 2 + x << 1 + x)$

家庭作业2.77

$K$	表达式
$17$	$x << 4 + x$
$- 7$	$- (x << 2 + x << 1 + x)$
$60$	$(x << 5 + x << 4) + (x << 3 + x << 2)$
$- 112$	$- (x << 6 + x << 5 + x << 4)$

掌握IEEE浮点表示

图2-35

浮点数表示的基本概念
- 在这个8位浮点格式中，有4位用于表示指数（ $e$ ），3位用于表示小数（ $f$ ），还有1位符号位（图中未体现，因为这里只讨论非负值）。
- 偏置量为7，即实际的指数值 $E = e - 7$ 。
- 规格化数的表示形式为 $(-1)^s \times M \times 2^E$ ，其中 $M = 1 + f$ （对于规格化数，隐含的整数位为1）；非规格化数的表示形式为 $(-1)^s \times M \times 2^E$ ，其中 $M = f$ （对于非规格化数，隐含的整数位为0）。
各部分含义及计算示例
- 位表示：展示了不同数值对应的8位二进制编码。
- 指数：
  - $e$ ：原始的指数位的值。
  - $E$ ：实际的指数值，通过 $E = e - 7$ 计算得到。
  - $2^E$ ：根据实际指数计算出的2的幂次。
- 小数：
  - $f$ ：小数位的值。
  - $M$ ：对于规格化数， $M = 1 + f$ ；对于非规格化数， $M = f$ 。
- 值：
  - $2^E \times M$ ：根据指数和小数计算出的中间结果。
  - $V$ ：最终的浮点数值，即 $(-1)^s \times M \times 2^E$ （这里 $s = 0$ ，因为只考虑非负值）。
  - 十进制：将浮点数值转换为十进制后的结果。
具体数值分析
- 最小的非规格化数：
  - 位表示为0 0000 001， $e = 0$ ， $E = 0 - 7 = - 6$ ， $2^E = \frac{1}{64}$ ， $\frac{1}{8}$ ， $\frac{1}{8}$ ， $2^E \times M = \frac{1}{512}$ ， $\frac{1}{512}$ ，十进制为 $0.001953$ 。
- 最大的非规格化数：
  - 位表示为0 0000 111， $e = 0$ ， $E = - 6$ ， $2^E = \frac{1}{64}$ ， $\frac{7}{8}$ ， $\frac{7}{8}$ ， $2^E \times M = \frac{7}{512}$ ， $\frac{7}{512}$ ，十进制为 $0.013672$ 。
- 最小的规格化数：
  - 位表示为0 0001 000， $e = 1$ ， $E = 1 - 7 = - 6$ ， $2^E = \frac{1}{64}$ ， $\frac{0}{8}$ ， $\frac{0}{8} = 1$ ， $2^E \times M = \frac{1}{64}$ ， $\frac{1}{64}$ ，十进制为 $0.015625$ 。
- 最大的规格化数：
  - 位表示为0 1110 111， $e = 14$ ， $E = 14 - 7 = 7$ ， $2^E = 128$ ， $\frac{7}{8}$ ， $\frac{7}{8} = \frac{15}{8}$ ， $2^E \times M = \frac{1920}{8}$ ， $V = 240$ ，十进制为 $240.0$ 。
- 无穷大：
  - 位表示为0 1111 000，用于表示无穷大，此时指数和小数的具体值不再有意义。

练习题2.47

练习题2.47
答案如下图
2.47答案

练习题2.52

格式A	格式A	格式B	格式B
位	值	位	值
011 0000	$1$	0111 000	$1$
101 1110	$7.75$	1010 111	$15$
010 1001	$\frac{25}{32}$	0110 110	$\frac{7}{8}$
110 1111	$15.5$	1011 111	$30$
000 0001	$\frac{17}{128}$	0100 001	$\frac{9}{64}$

家庭作业2.85

家庭作业2.85
A. 0 101 110
B. 0 101 110
C. 0 101 000

家庭作业2.88

格式A	格式A	格式B	格式B
位	值	位	值
1 01110 001	$-\frac{9}{16} \times 2^7$	1 1101 1111	$- 124$
0 10110 101	$\frac{13}{8} \times 2^7$	0 1110 1111	$248$
1 00111 110	$-\frac{15}{8} \times 2^8$	1 1111 1111	$- 512$
0 00000 101	$\frac{9}{8} \times 2^{-15}$	0 0000 1001	$\frac{9}{1024}$
1 11011 000	$\times 2^{12}$	1 1111 0000	$- 256$
0 11000 100	$\frac{5}{4} \times 2^9$	0 1110 1111	$248$

掌握IEEE浮点数舍入

图2-37

练习题2.50

练习题2.50
舍入到偶数规则（银行家舍入法）回顾

当舍去位（即要舍去的最低位，在本题中是从小数点后第二位开始看）小于5（对应二进制就是0）时，直接舍去。
当舍去位大于5（对应二进制就是1）时，向前进一位。
当舍去位等于5（对应二进制就是1）时，如果舍去位后面还有非零位（也就是还有数字），则向前进一位；如果舍去位后面没有非零位（即后面全是0了），则根据保留位（即要保留的最后一位，也就是小数点后第一位）的奇偶性来决定，若保留位是偶数，则直接舍去，若保留位是奇数，则向前进一位。

具体计算

A. (10.010_{2})
- 舍入前：(10.010_{2} = 2 + 0.010_{2} = 2 + \frac{1}{4} = 2.25_{10})
- 舍入到最接近的二分之一（二进制小数点右边(1)位），此时舍去位是小数点后第二位的(1)，它后面是(0)（也就是舍去位后面没有非零位了），再看保留位（小数点后第一位）是(0)（偶数），所以直接舍去，舍入后为(10.0_{2} = 2_{10})。
B. (10.011_{2})
- 舍入前：(10.011_{2} = 2 + 0.011_{2} = 2 + \frac{3}{8} = 2.375_{10})
- 舍入到最接近的二分之一，舍去位是小数点后第二位的(1)，它后面是(1)（也就是舍去位后面有非零位），所以向前进一位，舍入后为(10.1_{2} = 2 + \frac{1}{2} = 2.5_{10})。
C. (10.110_{2})
- 舍入前：(10.110_{2} = 2 + 0.110_{2} = 2 + \frac{3}{4} = 2.75_{10})
- 舍入到最接近的二分之一，舍去位是小数点后第二位的(1)，它后面是(0)（也就是舍去位后面没有非零位了），再看保留位（小数点后第一位）是(1)（奇数），所以向前进一位，舍入后为(11.0_{2} = 3_{10})。
D. (11.001_{2})
- 舍入前：(11.001_{2} = 3 + 0.001_{2} = 3 + \frac{1}{8} = 3.125_{10})
- 舍入到最接近的二分之一，舍去位是小数点后第二位的(0)（小于1，对应小于5的情况），直接舍去，舍入后为(11.0_{2} = 3_{10})。