一、计算机系统基础知识
1.计算机硬件组成
计算机的硬件基本系统由五大部分组成：运算器、控制器、存储器、输入设备（如鼠标键盘）、输出设备（如显示器）
存储器分为内部存储器（即内存，容量小，速度快，临时存放数据）和外部存储器（即硬盘、光盘等，容量大，速度慢，长期保存数据）
输入设备和输出设备合并称为外部设备，即外设
主机：CPU+主存储器
2.中央处理单元(CPU)
中央处理单元组成：由运算器、控制器、寄存器组和内部总线组成。
中央处理单元功能：实现程序控制、操作控制、时间控制、数据处理功能。
运算器组成：由算术逻辑单元ALU（实现对数据的算术和逻辑运算）、累加寄存器AC(运算结果或源操作数的存放区）、数据缓冲寄存器DR(暂时存放内存的指令或数据）、状态条件寄存器PSW(保存指令运行结果的条件码内容，如溢出标志等）组成。
运算器功能：执行所有的算术运算，如加减乘除等；执行所有的逻辑运算并进行逻辑测试，如与、或、非、比较等。
控制器组成：由指令寄存器IR（暂存CPU执行指令）、程序计数器PC（存放指令执行地址）、地址寄存器AR(保存当前CPU所访问的内存地址）、指令译码器ID（分析指令操作码）等组成。
控制器功能：控制整个CPU的工作，最为重要，包括程序控制、时序控制等。
3.数据表示
3.1数据的进制转化
进制的表示：二进制二进制符号为0b，一般表示为0b0011，十六进制符号为0x或H，可表示为0x18F或18FH。
3.1.1 R进制整数转十进制
方法：位权展开法，用R进制数的每一位乘以R的n次方,n是变量,从R进制数的整数最低位开始,依次为0,1,2,3…累加
示例：有6进制数5043，此时R=6，用6进制数的每一位乘以6的n次方，n是变量，从6进制数的整数最低位开始（5043从低位到高位排列：3,4,0,5），n依次为0,1,2,3,那么最终5043 = 3 ∗ 6 0 + 4 ∗ 6 1 + 0 ∗ 6 2 + 5 ∗ 6 3 = 1107 5043=3*6 ^ 0+4*6^1+0*6^2+5*6^3=11075043=3∗6
0
+4∗6
1
+0∗6
2
+5∗6
3
=1107。
图示:
3.1.2 十进制转R进制整数
方法：十进制整数(除以R倒取余数），用十进制整数除以R，记录每次所得余数，若商不为0，则继续除以R，直至商为0，而后将所有余数从下至上记录，排列成从左至右顺序，即为转换后的R进制数
示例：有十进制数200，转换为六进制，此时R=6，将200/6，得商为33，余数为2；因为商不等于0，因此再将商33/6，得商为5，余数为3；再将5/6，得商为0，余数为5；此时商为0，将所有余数从下到上记录，得532
图示:
3.1.2 M进制转N进制整数
方法：先将M进制转化为十进制数，再将十进制数转化为N进制数，中间需要通过十进制中转
特殊:二进制与八进制可以直接转化:
①二进制转八进制
方法:每3位二进制数转换为1位八进制数，二进制数位个数不是三的倍数，则在前面补0（原则是数值不变）
示例:二进制数01101有五位，前面补一个0就有六位，为001 101，每三位转换为一位八进制数，001=1,101=1+4=5，也即01101=15。
图示:
②二进制转十六进制
方法:每4位二进制数转换为1位十六进制数，二进制数位个数不是四的倍数，则在前面补0，如二进制数101101有六位，前面补两个0就有八位，为0010 1101，每四位转换为一位十六进制数，0010=2,1101=13=D，也即101101=2D。
图示:
3.2 数的表示
机器数：各种数值在计算机中表示的形式，其特点是使用二进制计数制，数的符号用0和1表示，小数点则隐含，不占位置。
机器数有无符号数和带符号数之分。
无符号数表示正数，没有符号位。
带符号数最高位为符号位，正数符号位为0，负数符号位为1。
定点表示法分为纯小数和纯整数 两种，其中小数点不占存储位，而是按照以下约定：
纯小数：约定小数点的位置在机器数的最高数值位之前。
纯整数：约定小数点的位置在机器数的最低数值位之后
真值：机器数对应的实际数值。
3.2.1 数的编码方式(带符号数)
①原码、反码、补码、移码：
原码：
一个数的正常二进制表示，最高位表示符号
数值0的源码有两种形式：
+0（0 0000000）
-0（1 0000000）
反码：
正数的反码即原码
负数的反码是在原码的基础上，除符号位外，其他各位按位取反。
数值0的反码有两种形式：
+0（0 0000000）
-0（1 1111111）
补码：
正数的补码即原码；
负数的补码是在原码的基础上，除符号位外，其他各位按位取反，而后末位+1，若有进位则产生进位。
数值0的补码只有一种形式
+0 = -0 = 0 0000000
移码：
用作浮点运算的阶码，无论正数负数，都是将该原码的补码的 首位（符号位） 取反得到移码
②知机器字长,求原码/反码/补码/移码
机器字长为n时各种码制表示的带符号数的取值范围（差别在于0的表示，原码和反码分+0和-0，补码只有一个0，因此可以多表示一个）
例：若机器字长为8，请给出45和-45的原码、反码、补码和移码
真值 原码 反码 补码 移码
45 00101101 00101101 00101101 10101101
-45 10101101 11010010 11010011 01010011
3.2.2 浮点数表示
①表示方法:
N = 尾数 ∗ 2 阶码 = F ∗ 2 E N = 尾数*2^{阶码}=F * 2^EN=尾数∗2
阶码
=F∗2
E
，其中E称为阶码， F称为尾数；类似于十进制的科学计数法
十进制如85.125 = 0.85125 ∗ 1 0 2 85.125 = 0.85125*10^285.125=0.85125∗10
2
二进制如101.011 = 0.101011 ∗ 2 3 101.011 = 0.101011*2^3101.011=0.101011∗2
3
在浮点数的表示中，阶码为带符号的纯整数，尾数为带符号的纯小数，要注意符号占最高位（正数0负数1），其表示格式如下:
阶符 阶码 数符 尾数
很明显，与科学计数法类似，一个浮点数的表示方法不是唯一的，浮点数所能表示的数值范围由阶码确定，所表示的数值精度由尾数确定
尾数的表示采用规格化方法，也即带符号尾数的补码必须为1.0xxxx（负数）或者0.1xxxx（正数），其中x可为0或1
②浮点数的运算:
1.对阶（使两个数的阶码相同，小阶向大阶看齐，较小阶码增加几位，尾数就右移几位）
2.尾数计算（相加，若是减运算，则加负数）
3.结果规格化（即尾数表示规格化，带符号尾数转换为1.0xxxx或0.1xxxx）
3.2.3 算数运算和逻辑运算
①算术运算:
数与数之间的算术运算包括加、减、乘、除等基本算术运算
②逻辑运算:
逻辑与&： 0和1相与，只要有一个为0结果就为0，两个都为1才为1
逻辑或|： 0和1相或，只要有一个为1结果就为1，两个都为0才为0
异或：同0非1，即参加运算的二进制数同为0或者同为1结果为0，一个为0另一个为1结果为1
逻辑非!： 0的非是1， 1的非是0
逻辑左移<<：二进制数整体左移n位，高位若溢出则舍去，低位补0
逻辑右移>>：二进制数整体右移n位，低位溢出则舍去，高位补0
4.校验码
码距:在两个编码中， 从A码到B码转换所需要改变的位数称为码距
就单个编码A：00而言，其码距为1，因为其只需要改变一位就变成另一个编码。
在两个编码中,从A码到B码转换所需要改变的位数称为码距，如A：00要转换为B：11，码距为2。
一般来说，码距越大，越利于纠错和检错
奇偶校验码:在编码中增加1位校验位来使编码中1的个数为奇数（奇校验）或者偶数（偶校验），从而使码距变为2
2.1. 奇校验：编码中，含有奇数个1，发送给接收方，接收方收到后，会计算收到的编码有多少个1，如果是奇数个，则无误，是偶数个，则有误。
2.2. 偶校验 同理，只是编码中有偶数个1
2.3.奇偶校验只能检1位错，并且无法纠错
4.1循环冗余校验码CRC
4.1.1原理:找出一个能整除多项式的编码
首先要将原始报文除以多项式，将所得的余数作为校验位加在原始报文之后，作为发送数据发给接收方
4.1.2编码格式
CRC由两部分组成，左边为信息码（原始数据），右边为校验码。
校验码是由信息码产生的，校验码位数越长，校验能力越强
求CRC编码时，采用的是模2运算（按位运算，不发生借位和进位）
4.1.3特点:CRC只能检多位错，不能纠错
4.1.4 例题应用
例题: 原始报文为“11001010101”，其生成多项式为：“x 4 + x 3 + x + 1 x^4+x^3+x+1x
4
+x
3
+x+1”。对其进行CRC编码后的结果为？
步骤1.求多项式:
步骤2:为接下的操作做准备
求得的多项式为除数:11011
原始多项式后面+多项式最高指数个数个0 ,作为被除数:11001010101 0000(因为多项式最高指数为4,所以后面加4个0)
步骤3:进行模2除法 ,一直在商上1
模2运算其实相当于异或运算(即同0非1)
步骤4:最终编码为11001010101 0011，然后发送出去
接收方将收到的数据110010101010011与多项式的11011进行模2运算，若余数为0，说明校验正确，数据传输正确
4.2 海明校验码
4.2.1原理:利用奇偶性
海明码：本质也是利用奇偶性来检错和纠错的检验方法
方法：在数据位之间的确定位置上插入k个校验位，通过扩大码距实现检错和纠错
设数据位是n位，校验位是k位，则n和k必须满足以下关系： 2 k ≥ n + k + 1 2^k≥n+k+12
k
≥n+k+1
数据位n与校验位位数k的关系
n k(最小)
1 2
2~4 3
5~11 4
12~26 5
4.2.2 例题应用
例题:求信息1011的海明码
(1)校验位的位数和具体的数据位的位数之间的关系：
根据上面数据位n与校验位位数k的关系可知,如果信息数据是1011,则数据位是4位,那么校验位是3位
校验位处于2的n（n=0 1 2…）次方中，即处于第1,2,4,8,16,32…位上
所以,第1,2,4位为校验位，第3,5,6,7位为数据位，用来从低位开始存放1011
(2)每一位校验码的计算公式：
确定每一位校验码到底校验哪些信息位
将信息位（即编号）拆分成二进制表示
如第7位数据位7=4+2+1
第7位数据由第4位校验位(r2)和第2位校验位(r1)和第1位校验位(r0)共同校验
同理：第6位数据位6=4+2； 第5位数据位5=4+1；第3位数据位3=2+1
前面知道，这些2的n次方都是校验位，可知，第4位校验位校验第7 6 5三位数据位，因此，第4位校验位r2等于这三位数据位的值异或
r 2 = I 4 ⊕ I 3 ⊕ I 2 = 1 ⊕ 0 ⊕ 1 = 0 r_2 =I_4⊕I_3⊕I_2=1⊕0⊕1=0r
2
=I
4
⊕I
3
⊕I
2
=1⊕0⊕1=0
第2位和第1位校验位计算原理同上
r 1 = I 4 ⊕ I 3 ⊕ I 1 = 1 ⊕ 0 ⊕ 1 = 0 r_1 =I_4⊕I_3⊕I_1=1⊕0⊕1=0r
1
=I
4
⊕I
3
⊕I
1
=1⊕0⊕1=0
r 0 = I 4 ⊕ I 2 ⊕ I 1 = 1 ⊕ 1 ⊕ 1 = 1 r_0 =I_4⊕I_2⊕I_1=1⊕1⊕1=1r
0
=I
4
⊕I
2
⊕I
1
=1⊕1⊕1=1
计算出三个校验位后，可知最终要发送的海明校验码为1010101
(3)检错和纠错原理
接收方收到海明码之后，会将每一位校验位与其校验的位数分别异或，即做如下三组运算：
如果是偶校验，那么运算得到的结果应该全为0，如果是奇校验，应该全为1，才是正确
假设是偶校验，且接收到的数据为1011101（第四位出错），此时，运算的结果为
上图中的运算结果不全为0(偶校验的运算结果应该全为0)，表明传输过程有误
且按照r 2 r 1 r 0 r_2r_1r_0r
2
r
1
r
0
排列为二进制100，这里指出的就是错误的位数，表示第100，即第4位出错，找到了出错位，纠错方法就是将该位逆转
