深入理解计算机系统读书笔记

前言

我是一名刚入职半年的码农，本硕非CS专业，自知基础薄弱。但我是一个有远大抱负的人，想在这个领域有所建树，于是决定先从这本书开始作为起点，文章会对我认为的重点知识做盘点，如果我有疑惑的地方，也会写出来，请各位大神指摘。

信息的表示和处理

十六进制、十进制和二进制转换

二进制转十六进制：从低位到高位，每四位转成16进制，16进制转2进制则相反
十进制转十六进制：将十进制x转换为16进制，可以反复的用16除x，得到商q和余数r
$x=q*16+r$x=q∗16+r
原理如下，对于十进制数$x$x：
$x=a_1*16+r_1$x=a1​∗16+r1​
$a_1=a_2*16+r_2$a1​=a2​∗16+r2​
$a_2=a_3*16+r_3$a2​=a3​∗16+r3​
$...$...
$a_{n-2}=a_{n-1}*16+r_{n-1}$an−2​=an−1​∗16+rn−1​
$a_{n-1}=0*16+r_n$an−1​=0∗16+rn​
其中$a_{n-1}$an−1​表示小于16的上一次除法的商，可以写成下式:
$x=a_1*16+r_1=(a_2*16+r_2)*16+r1=((a_3*16+r_3)*16+r_2)*16+r1=...$x=a1​∗16+r1​=(a2​∗16+r2​)∗16+r1=((a3​∗16+r3​)∗16+r2​)∗16+r1=...
展开后,直到消掉$a_{n-1}$an−1​，表达式可写为:
$x=r_n*16^n+r_{n-1}*16^{n-1}+...+r_2*16^2+r1$x=rn​∗16n+rn−1​∗16n−1+...+r2​∗162+r1
根据定义，十六进制表达式为$0Xr_{n}r_{n-1}..r_2r_1$0Xrn​rn−1​..r2​r1​

字、大端与小端

每台计算机都有一个字长，比如我们通常说的32位机器或64位机器，这个32和64就是字长。字长决定的最重要的就是可访问内存的大小，虚拟地址的范围是$0$0到$2^w-1$2w−1，比如32位字长的机器，就限定了最大字长约4GB.

大小端分别指字节在内存中存储的顺序，比如对于16进制数$0X01234567$0X01234567，按照存储顺序：
大端：01 23 45 67
小端：67 45 23 01

整数表示

无符号和有符号

假设某数据类型有$w$w位，$[x_{w-1},x_{w-2},...x_0]$[xw−1​,xw−2​,...x0​]，则
无符号表示:$B2U_w=\sum_{i=0}^{w-1}x_i*2^i$B2Uw​=∑i=0w−1​xi​∗2i
有符号(补码)表示:$B2T_w=-2^{w-1}*x_{w-1}+\sum_{i=0}^{w-2}x_i*2^i$B2Tw​=−2w−1∗xw−1​+∑i=0w−2​xi​∗2i
除了补码外，还可以用反码、原码表示有符号的整数，但是他们对0有两种不同的编码。其实无论何种编码从位级上看都是相同的，不同的是表达式对它的解释。

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

无符号转有符号：设无符号的数值为$x$x，若最高位是0，为原值；最高位是1，表达式为$U2T_w=x-2^w$U2Tw​=x−2w
有符号转无符号：设有符号的数值为$x$x，若最高位是0，为原值；最高位是1，表达式为$T2U_w=x+2^w$T2Uw​=x+2w

整数运算

无符号加法

假设某数据类型有$w$w位，则表示范围是0到2^w-1，相加的范围是0到2^2w-2，因此可能产生溢出，现行的策略是截取高$w$w位，相当于对结果模运算2^w

有符号(补码)加法

假设某数据类型有$w$w位，则表示范围是-2^w-1到2^w-1-1，则相加的范围是-2^w到2^w-2，因此即可能产生正溢出，也可能产生负溢出，且产生正溢出时两个数均为负，正溢出时两个数均为正。
但由于两个数的w位补码之和与无符合之和有相同的位级表示，因此我们可以用无符号的解释来做加法，并截取高w位，再转换成补码。
设两个补码数为x,y，则有$s=U2T_w((T2U_w(x)+T2U_w(y)) mod 2^w)$s=U2Tw​((T2Uw​(x)+T2Uw​(y))mod2w),根据定义，该式等价为:
$s=U2T_w[(x_{w-1}*2^w+x+y_{w-1}*2^w+y)mod 2^w]=U2T_w[(x+y)mod 2^w]$s=U2Tw​[(xw−1​∗2w+x+yw−1​∗2w+y)mod2w]=U2Tw​[(x+y)mod2w]
…剩下的推导有部分没有理清楚，待续,直接上结论：
$s=\begin{cases} x+y-2^w, & \text{正溢出} \\ x+y, & \text{正常}\\ x+y+2^w, & \text{负溢出} \end{cases}$s=⎩⎪⎨⎪⎧​x+y−2w,x+y,x+y+2w,​正溢出正常负溢出​

乘法、除法

无符号：w位无符号的乘法可能会溢出，对结果模运算2^w即可
有符号: 对于无符号和补码乘法来说，位级的表示都是一样的。因此$s=U2T_w((x*y)mod 2^w)$s=U2Tw​((x∗y)mod2w)
乘以常数：常数可以用移位运算和加减法，再做乘法，因为乘法指令相对较慢。
除以2的幂：对于无符号数，逻辑右移k和除以2^k有相同的效果；对于补码数，在移位之前需要加上一个偏置值，c表达式为:

(x<0?(x+(1<<k)-1:x)>>k

浮点数

IEEE浮点表示

IEEE浮点标准用$V=(-1)^s*M*2^E$V=(−1)s∗M∗2E的形式来表示一个数，s表示这个数的正(0)负(1)。
M是一个二进制小数。对于规格化的值，M=1+f,f是小数位对应的值，E=e-bias，Bias的值为$2^{k-1}-1$2k−1−1，e的值为指数字段的值；对于非规格化的值，E=1-bias，M=f。
对于单精度，指数位是8，小数位是23；对于双精度，指数位是11，小数位是52。
特殊值：当指数为全为1时出现，具体不表了。

舍入

这里主要提一下向偶数舍入，对于非中间的值，跟接近哪边则向哪边舍入。举例，舍入到小数点后2位的问题，10.00011则舍入位10.00，10.00110则摄入到10.01,进1位即可。对于中间的数值，最低为是0直接舍去；最低位是1则进一位，比如10.10100舍入成10.10(舍1位)，而10.11100则舍入为11.00(进1位)。