SCAU期末通关 - 计算机系统基础核心习题精讲

1. 信息的表示与处理从补码到浮点打通数据底层逻辑每次期末复习《计算机系统基础》看到“信息的表示与处理”这一章很多同学就开始头疼。十六进制转换、补码运算、浮点表示……感觉知识点又多又散做题时总在细节上栽跟头。别慌这章的核心其实就一条线计算机如何用有限的0和1来表示和运算无限的数字世界。理解了这条主线所有习题都能迎刃而解。我当年学这门课也是被各种位运算绕得晕头转向。后来在项目里调试一个硬件驱动发现一个数值溢出的Bug追根溯源才发现是C语言里无符号数和有符号数混用导致的。那一刻我才真正明白课本上那些枯燥的习题其实都是未来写代码时实实在在的“坑”。咱们今天不搞填鸭式背诵就挑几道最典型、最容易出错的题带你彻底搞懂背后的原理让你以后写代码时心里有底。1.1 补码运算有符号数的“环形世界”补码是本章的绝对核心也是考试必考。很多同学会算但不懂为什么这么算。我们来看一道经典题已知一个4位补码表示的数[1011]求其十进制值。最直接的方法是套公式最高位权重为负。对于[1011]w4最高位第3位是1所以值是-2^3 0*2^2 1*2^1 1*2^0 -8 0 2 1 -5。但死记公式容易忘。我教你一个更直观的“借位”理解法把补码想象成一个钟表盘。对于4位数范围是-8到7。我们从0开始逆时针减走。[1011]我们看它离“0点”[0000]有多远。你可以把它当成无符号数11821。在4位补码的“钟表”上总数是16个刻度2^4。一个数x的补码值可以看作是x - 16如果x8。11 - 16 -5。是不是快多了再来看一道容易混淆的题执行C语句int i -2147483648; printf(“%d\n”, i-1 i);输出是什么很多同学一看i是32位int的最小值-2^31减1不就溢出了吗在C语言中有符号整数的溢出是未定义行为但大多数机器使用补码运算其行为是“环绕”的。在补码表示下-2^31 - 1会变成2^31 - 1也就是最大的正数。所以(i-1) i的比较在补码运算的视角下就是2147483647 -2147483648结果为真1。这里的关键是跳出数学思维进入计算机的“有限位”思维。补码的世界是一个首尾相接的环最大值加1会变成最小值最小值减1会变成最大值。理解了这个“环”你就能看透很多关于溢出的题目。1.2 浮点数IEEE 754的“科学计数法”浮点数绝对是“老大难”。一堆名词符号位、阶码、尾数、规格化、非规格化、NaN、无穷大……别怕咱们用生活化的方式来理解。把浮点数看作科学计数法(-1)^s * M * 2^E。s是符号位0正1负。M是尾数是一个在[1, 2)或[0, 1)之间的二进制小数。E是指数决定了小数点的位置。我们来看一道8位浮点格式的题1位符号位4位阶码3位尾数偏置量7。求位模式0 1010 110表示的值。第一步拆解。符号位s0正数。阶码字段exp1010二进制 10十进制。尾数字段frac110二进制 6/8 0.75。第二步判断规格化。因为exp的位模式既非全0也非全1不是0000或1111所以这是一个规格化数。第三步计算指数E。对于规格化数E exp - Bias。这里Bias 2^(k-1) - 1 2^(4-1)-1 7。所以E 10 - 7 3。第四步计算尾数M。对于规格化数M 1 frac。这里M 1 0.75 1.75。第五步组合求值。V (-1)^0 * 1.75 * 2^3 1.75 * 8 14.0。搞定关键在于记住三个区间的处理方式1.规格化数exp不全0不全1E exp - Bias,M 1 frac。2.非规格化数exp全0E 1 - Bias,M frac。这是用来表示0和非常接近0的数。3.特殊值exp全1如果frac全0表示无穷大正负由s决定否则表示NaN非数。我调试程序时曾遇到一个诡异的Bug两个很小的数相乘结果突然变成了0。就是因为乘积进入了非规格化区域精度丢失严重。理解了浮点数的表示你就能明白为什么在金融计算中要用定点数或十进制库而不是直接用float或double。2. 程序的机器级表示像侦探一样阅读汇编代码学完信息的表示我们进入更“刺激”的部分看看你写的C代码在CPU眼里到底是什么样子。这一章的核心是逆向工程——给你一段汇编代码让你还原出C语言逻辑。这就像侦探破案根据现场痕迹汇编指令还原案发过程程序逻辑。刚开始看汇编感觉像天书。movq,leaq,testq,jmp…… 别急把握几个关键点数据在哪寄存器/内存、怎么流动数据传送、怎么计算算术/逻辑运算、怎么跳转控制流。我们通过两道经典题来掌握。2.1 数据传送与算术运算还原基本表达式看下面这段汇编代码片段decode1: movq (%rdi), %r8 movq (%rsi), %rcx movq (%rdx), %rax movq %r8, (%rsi) movq %rcx, (%rdx) movq %rax, (%rdi) ret问题请写出对应的C函数原型和实现。我们一步步分析前三条movq是加载操作从%rdi,%rsi,%rdx这三个寄存器指向的内存地址中取值。根据x86-64调用约定它们通常存放前三个参数。所以我们可以假设函数接收三个指针参数long *xp,long *yp,long *zp。取出的值分别放到了%r8,%rcx,%rax寄存器。这相当于三个临时变量temp1 *xp,temp2 *yp,temp3 *zp。后三条movq是存储操作把寄存器的值存回内存但顺序交叉了。%r8原xp存到了(%rsi)即yp%rcx原yp存到了(%rdx)即zp%rax原zp存回了(%rdi)即xp。这不就是一个轮换赋值吗相当于*yp temp1; *zp temp2; *xp temp3;。所以完整的C函数是void decode1(long *xp, long *yp, long *zp) { long temp1 *xp; long temp2 *yp; long temp3 *zp; *yp temp1; *zp temp2; *xp temp3; }本质交换了三个指针所指向的值。xp指向的值给了ypyp的给了zpzp的又给了xp完成了一次三角交换。这类题的关键是跟踪每个寄存器的“身份”变化像玩“找不同”游戏一样看清数据是如何流动和交换的。2.2 控制流if-else和循环的“真面目”控制流是汇编的精华也是难点。我们看一个包含if-else的复杂例子。给你如下汇编请还原C代码test: leaq (%rdi,%rsi), %rax addq %rdx, %rax cmpq $-3, %rdi jge .L2 cmpq $2, %rdi jle .L4 ret .L2: cmpq %rdx, %rsi jge .L3 movq %rdi, %rax imulq %rsi, %rax ret .L3: movq %rsi, %rax imulq %rdx, %rax ret .L4: movq %rdi, %rax imulq %rdx, %rax ret我们来当一回“代码翻译官”开场计算leaq (%rdi,%rsi), %rax和addq %rdx, %rax计算了x y z并把结果存在%rax返回值寄存器里。所以初始long val x y z;。第一层判断cmpq $-3, %rdi比较x和-3。jge .L2是“大于等于则跳转”。所以如果x -3跳转到.L2否则x -3继续执行下一行。x -3 的分支接着cmpq $2, %rdi比较x和2。jle .L4是“小于等于则跳转”。所以如果x 2跳转到.L4否则x -3且x 2这不可能因为x是整数x-3时最大是-4不可能大于2直接返回初始的val。.L4标签里是movq %rdi, %rax; imulq %rdx, %rax即val x * z;然后返回。x -3 的分支.L2这里比较%rsi(y) 和%rdx(z)。jge .L3如果y z则跳转。.L3里是val y * z;。如果不跳转即y z则执行movq %rdi, %rax; imulq %rsi, %rax即val x * y;。把逻辑整理一下用C语言写出来就是long test(long x, long y, long z) { long val x y z; if (x -3) { if (y z) { val y * z; } else { val x * y; } } else if (x 2) { val x * z; } // 如果 x -3 且 x 2保持 val x y z return val; }逆向心法cmp A, B后面紧跟的跳转指令是关键。jg/jge/jl/jle分别对应 / / / 。标签如.L2是跳转的目的地。画流程图是理清复杂控制流的不二法门。我在实际做性能分析时经常需要看编译器生成的汇编来优化热点循环。掌握了这门“外语”你就能和CPU直接对话了。3. 存储器层次结构让程序飞起来的缓存奥秘这是影响程序性能最关键的一章也是面试高频考点。CPU速度比内存快100倍如果没有缓存计算机将慢得无法忍受。缓存的核心思想是局部性原理时间局部性最近访问的很可能再次访问和空间局部性访问一个位置很可能访问其相邻位置。考题通常围绕缓存的结构S, E, B和地址划分CT, CI, CO展开。我们通过一道综合题把整个流程跑通。3.1 缓存地址解析与命中判断假设我们有一个高速缓存参数如下容量C32字节块大小B8字节相联度E22路组相联共有S4个组。地址宽度为m8位。问题1对于物理地址0xAD请问缓存如何解析是否命中如果命中返回什么数据我们一步步来确定地址字段长度块大小B8字节所以块内偏移CO需要 log2(8) 3 位。组数S4所以组索引CI需要 log2(4) 2 位。标记位CT长度 m - (s b) 8 - (23) 3 位。所以地址划分是[CT: 3位] [CI: 2位] [CO: 3位]。解析地址0xAD0xAD 的二进制是1010 1101。从最低位开始CO是低3位101(二进制) 5。接下来2位是CI01(二进制) 1。最高3位是CT101(二进制) 5。查询缓存根据CI1找到缓存中的第1组。这一组有E2行。检查这两行的有效位和标记位。假设我们有一个如下的缓存状态表组索引有效位标记位数据块字节0-7013...017...112[0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17]115[0xA0, 0xA1, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7]20-...214...316...30-...在第1组中我们找到有一行的标记位CT5且有效位为1。因此缓存命中获取数据命中行的数据块是[0xA0, 0xA1, ..., 0xA7]。CO5表示我们需要该数据块内的第5个字节从0开始计数。所以返回的数据是0xA5。答案CT5 CI1 CO5。缓存命中返回的字节值为0xA5。3.2 编写缓存友好的代码知道原理是为了写出更快的代码。我们来看一个经典例子遍历一个二维数组行优先和列优先性能差异有多大假设有一个int array[1024][1024]缓存足够大能放得下1024个int即一行。我们计算所有元素之和。版本A行优先缓存友好int sum_array_rows(int a[1024][1024]) { int i, j, sum 0; for (i 0; i 1024; i) for (j 0; j 1024; j) sum a[i][j]; return sum; }版本B列优先缓存不友好int sum_array_cols(int a[1024][1024]) { int i, j, sum 0; for (j 0; j 1024; j) for (i 0; i 1024; i) sum a[i][j]; return sum; }为什么A比B快很多因为数组在内存中是按行连续存储的。对于版本A内层循环j访问的是a[i][0],a[i][1],a[i][2]... 这些地址在内存中是连续的。当CPU加载a[i][0]时会把包含它及其后面若干个字节的整个缓存块比如64字节16个int都加载到缓存中。接下来访问a[i][1]到a[i][15]都在同一个缓存块里全部命中只有跨到下一个缓存块时才会发生一次不命中。不命中率极低。对于版本B内层循环i访问的是a[0][j],a[1][j],a[2][j]... 每次访问都跳过了1024个int一整行的内存距离。每次访问几乎都在不同的缓存行导致每次内层循环迭代都可能发生缓存不命中。不命中率接近100%我在优化一个图像处理算法时就因为把访问顺序从列优先改成行优先性能直接提升了8倍。记住这个黄金法则让内存访问模式尽可能连续充分利用空间局部性。4. 链接与异常控制流程序运行的幕后故事最后这两章揭示了程序从静态代码到动态进程的完整生命周期。链接讲的是“如何拼装”异常控制流讲的是“如何运行”。4.1 符号解析解决“谁是谁”的拼图游戏链接器就像一个拼图大师它的任务是把多个.o目标文件中的符号变量名、函数名引用和定义对应起来。规则听起来简单强符号已初始化的全局变量、函数只能有一个弱符号未初始化的全局变量可以合并。但坑就藏在细节里。看这道题有两个源文件。// foo.c int x 100; void f() { x 200; }// bar.c double x; void g() { x 3.14; }问题链接这两个文件会怎样这里foo.c定义了强符号int x 100;bar.c定义了弱符号double x;未初始化。根据链接器规则不允许出现两个同名的强符号。这里只有一个强符号int x所以不冲突。如果有强符号和弱符号同名链接器会选择强符号的定义。所以最终链接后全局变量x是int类型大小为4字节初始值为100。那么问题来了bar.c中的g()函数执行x 3.14;会发生什么x现在是一个int变量但3.14是一个double值。这会导致将8字节的double值写入一个4字节的int内存空间造成内存越界写入破坏相邻变量。浮点数3.14被截断并转换为整数3存入x。这是一个非常危险的错误但链接器不会报错它只检查符号是否存在不检查类型是否匹配。这种Bug极难调试因为症状可能出现在完全不相干的地方。教训尽量避免使用全局变量。如果必须用一定要加上static限制作用域或者使用命名前缀来避免冲突。4.2 进程与信号理解并发世界的秩序与混乱异常控制流中进程和信号是核心。我们通过一道经典的“进程扇”题目来理解。int main() { int i; for (i 0; i 2; i) { Fork(); printf(hello\n); } exit(0); }问题一共会打印多少行 “hello”很多同学会脱口而出4行。因为循环2次每次fork所以是2^24。对吗我们仔细分析一下。初始状态只有父进程P0。i0时P0调用Fork()创建子进程C1。现在有两个进程P0和C1。注意Fork()之后两个进程都会执行printf(hello\n)。所以此时会输出2个“hello”。然后两个进程都进入下一次循环。i1时进程P0再次调用Fork()创建子进程C2。P0和C2都会执行printf。输出2个“hello”。进程C1它也执行到了i1调用Fork()创建子进程C3。C1和C3都会执行printf。输出2个“hello”。所以总的“hello”输出行数 2i0时 2P0在i1时 2C1在i1时6行。你可以画一个进程图来辅助理解每个进程是一个节点Fork()产生分支。在每次printf的地方标记输出。你会发现每个进程在创建后都会执行它自己后续的所有循环和打印。这才是理解fork的关键fork之后父子进程在相同的代码位置继续执行拥有各自独立的变量副本。信号处理是另一个难点核心在于理解信号是异步送达的。信号处理函数handler可能会在任何时刻打断主程序的执行。这意味着在handler中调用像printf,malloc这样的非异步信号安全函数是危险的因为它们可能在被中断的主程序函数中正处于不 consistent 的状态。复习这部分时不要死记硬背。想象自己是一个操作系统调度器你的任务是在多个进程间公平切换并处理各种硬件和软件中断。理解了“并发”和“异步”这两个核心概念你就能把握住异常控制流的精髓。把这四章的核心习题吃透SCAU的《计算机系统基础》考试基本就稳了。这些知识不仅仅是应付考试更是你未来写出高效、健壮代码的基石。当你再遇到内存越界、数值溢出、性能瓶颈或者诡异的并发Bug时你会感谢现在努力理解底层原理的自己。学习计算机系统就像给程序员打开了“上帝视角”让你能从电子流动的层面理解屏幕上每一行代码的真正含义。