前言知识：
等差数列公式： \[ a_n=a_1+(n-1)d\\ S_n=\frac {n(a_1+a_n)}{2}=na_1+\frac {n(n-1)}{2}d \] 等比数列公式： \[ a_n=a_1q^{n-1}(q\neq0)\\ S_n=\frac {a_1(1-q^n)}{1-q}=\frac{a_1-a_nq}{1-q} \]
一、计算机系统概论
1.1计算机系统简介
物联网：把传感器嵌入和装备到各种物体中，并且被普遍连接
计算机系统由硬件和软件组成
硬件：计算机的实体，如主机、外设等
软件：由具有各类特殊功能的程序组成
1
2系统软件：用来管理整个计算机系统，如语言处理程序、操作系统、服务性程序、数据库管理系统、网络软件(如tcp/ip协议的模块)
应用软件：按任务需要贬值的各种程序
1.2计算机硬件基本组成
1.2.1冯诺依曼机
第一台计算机ENIAC(埃尼亚克)通过手动接线的方式进行控制计算，效率受到接线的限制
冯诺依曼提出“存储程序”：将指令以二进制代码的形式实现输入到计算机的主存储器，然后从首地址开始按序执行指令
早期冯诺依曼体系结构：
步骤：
1 | 数据或程序先进入输入设备，将信息转换为机器能识别的形式 |
冯诺依曼计算机的特点：
1 | 计算机由五大部分组成：输入设备、输出设备、控制器、运算器、存储器 |
1.2.2现代计算机的结构
以存储器为中心
CPU=运算器+控制器
主存：RAM运行内存
辅存：ROM存储大小
1.2.3主存储器
读取：CPU将地址传入MAR，从MDR获得数据，控制器控制主存储器执行"读"操作
写入：CPU将地址传入MAR，数据传入MDR，控制器控制主存储器进行"写"操作
【存储体】：
数据都在存储体内按地址存储
存储单元：存储器最小的存储单位，是一串存放二进制代码的空间
存储字（word）：存储单元中二进制代码的组合
存储字长：存储单元中二进制代码的位数（通常为8bit的整数倍）
存储元：用于存储二进制的的电子元件（电容），每个存储元可以存1bit
因此，MAR位数可以反映存储单元的个数，MDR的位数等于存储字长
1.2.4运算器
用于实现算术运算（加减乘除），逻辑运算（布尔运算）
1 | ACC:累加器。用于存放操作数或运算结果。 |
1.2.5控制器
1 | CU(Control Unit):控制单元，分析指令，给出控制信号 |
完成一条指令需要：
从PC取指令放入IR中，CU分析IR中的指令，从而控制其他配件进行指令执行
1.3计算机系统的层次结构
下层是上层的基础，上层是下层的拓展。
编译程序：将高级语言编写的源程序全部语句一次性翻译成机器语言程序，而后直接执行机器语言程序(.exe)，如C/C++，Java
解释程序：将源程序的一条语句翻译成对应的机器语言的雨具，并立即执行，紧接着翻译下一句（每次执行都要翻译）如Python、JavaScript、shell
1.4计算机性能指标
1.4.1存储器的性能指标
总容量：
- 存储单元个数*存储字长 bit
- 存储单元个数*存储字长/8 Byte
Eg：MAR为32位，MDR为8位 \[ 总容量 = 2^{32}*8=32Gbit=4GB \] MAR位数反映存储单元的个数，MDR位数反映每个存储单元的大小
1.4.2CPU的性能指标
\[ K=Kilo=千=10^3\\ M=Milion=百万=10^6\\ G=Giga=十亿=10^9\\ T=Tera=万亿=10^{12} \]
K、M、G 和 T 在不同上下文中可以表示不同的含义，具体取决于是以 2 的 10 次方（1024 的倍数）还是以 10 的 3 次方（1000 的倍数）为基础。
二进制（以 2 为基础）：
- K 表示 2^10，即 1024。
- M 表示 2^20，即 1024 * 1024。
- G 表示 2^30，即 1024 * 1024 * 1024。
- T 表示 2^40，即 1024 * 1024 * 1024 * 1024。
在计算机领域，通常使用二进制定义存储容量，如硬盘容量、内存大小等。
十进制（以 10 为基础）：
- K 表示 10^3，即 1000。
- M 表示 10^6，即 1000 * 1000。
- G 表示 10^9，即 1000 * 1000 * 1000。
- T 表示 10^12，即 1000 * 1000 * 1000 * 1000。
在一些其他上下文，如国际制度和网络速度，通常使用十进制定义单位，表示文件大小、带宽等。
(1)CPU主频：
CPU内数字脉冲信号振荡的频率 \[ CPU主频（时钟频率）=1/CPU时钟周期 \] (2)CPI（Clock cycle Per Instruction）
执行一条指令所需要的时钟周期（不同的指令CPI不同，甚至相同的指令CPI也会有变化）
执行一条指令的耗时=CPI*CPU时钟周期
Eg：某CPU主频为1000Hz，某程序包含100条指令，平均来看指令的CPI=3，则该程序要在该CPU上执行完成需要多久？ \[ 100*3*(1/1000)=0.3s \] (3)IPS (Instructions Per Second)
每秒执行多少条指令
IPS = 1/(CPI*时钟周期)= 主频/CPI
(4)FLOPS (Floating-point Operations Per Second)
每秒执行多少次浮点运算
1.4.3系统整体性能指标
(1)数据通路带宽：数据总线一次能并行传送的位数
(2)吞吐量：系统在单位时间内处理请求的数量
(3)响应时间：指的是用户向计算机发送一个请求到系统对该请求做出响应并获得所需要的结果的等待时间
二、数据的表示和运算
2.1 进位计数制
\[ 二进制:0,1\\ 八进制:0,1,2,3,4,5,6,7\\ 十进制:0,1,2,3,4,5,6,7,8,9\\ 十六进制:0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F\\ \]
\[ 二进制：101.1->1*2^2+2*2^1+1*2^0+1*2^{-1}=5.5 \\ 八进制：5.4->5*8^0+4*8^{-1}=5.5\\ 十进制：5.5->5*10^1+5*10^{-1}=5.5\\ 十六进制：5.8->5*16^0+8*16^{-1}=5.5 \] 类推：r进制计数法 \[ (K_nK_{n-1}...K_2K_1K_0K_{-1}K_{-2}...K_{-m})整体的一个数转十进制 \\ =K_n*r^n+K_{n-1}*r^{n-1}+...+K_2*r^2+K_1*r^1+K_0*r_0+K_{-1}*r^{-1}+K_{-2}*r^{-2}+...+K_{-m}*r^{-m} \] 十进制转换任意进制
1 | 真值：人类习惯的数字 |
2.2 BCD码
2.2.1 8421码
每4bit表示一个数字，如12就可以表示为“0001 0010”的形式 \[ 十进制:5+8=13\\ 8421码:0101+1000=1101(不在映射表中)\\ 如果不在映射表内，8421中1010~1111没有意义\\ +6(0110)修正即可\\ 0101+1000=1101+0110=0001\quad0011 \] 注意：如果在映射表中就无需修正。
2.2.2 余3码
余3码：8421码+(0011)
2.2.3 2421码
前五个数字第一位都为0，后五个数字第一位都为1
2.3无符号整数的加减法运算
2.3.1无符号整数的加法运算
计算机硬件：从最低位开始，按位相加，并往更高位进位
2.3.2无符号整数的减法运算
计算机硬件："被减数"不变，"减数"全部按位取反，末尾+1，减法变加法（加法电路造价便宜）---数论
2.4带符号整数(定点整数)在计算机中的应用
带符号整数的表示：原码、补码、反码
（同一个含义，只是编码方式不同，不同的编码方式有不同的优缺点）
2.4.1原码
符号位"0"表示正，"1"表示负，剩余的为数值位
若机器字长为n+1位，则原码表示范围为 \[ -(2^{n}-1)\leq x \leq 2^n-1 \] 真值0有两种形式，+0和-0, [+0]原=0 0000000，[-0]原=1 0000000
原码的缺点
符号位不能参与运算，需要设计复杂的硬件电路才能处理
2.4.2补码
补码转反码只需要末位-1即可，但是操作麻烦，所以可以先用补码算出原码，再转反码，以下为方法2：
此为手算快速转换技巧，计算机中并不是这样实现的
补码的加法运算
计算机硬件从最低位开始，按位相加（符号位参与运算），并往更高位进位
补码的减法运算
注意：原码转补码符号位不用按位取反，补码转补码的负要全部位按位取反。
无符号整数和有符号整数的减法都是全部位按位取反末位+1，所以可以用同一套电路
2.4.3移码
补码的基础上将符号位取反。注意：移码用于表示整数
2.5定点小数
定点整数的编码表示：原码、反码、补码、移码
定点小数的编码表示：原码、反码、补码
2.5.1定点小数原码、反码、移码
2.6奇偶校验码
奇校验码：整个校验码（有效信息位和校验位）中“1”的个数为奇数。
偶校验码：整个校验码（有效信息位和校验位）中“1”的个数为偶数。
Eg：给出两个编码1001101和1010111
奇校验：11001101 01010111
偶校验：01001101 11010111
奇偶校验码的局限性：如果发生了两个位置的错误，会出现校验不出的情况
硬件实现偶校验通过异或（⊕）运算求得校验位
1⊕0⊕0⊕1⊕1⊕0⊕1=0所以第一个编码的偶校验位为0
2.7符号拓展
注意负数反码和补码的拓展！
三、电路的实现
3.1算术逻辑单元（ALU）--Arithmetic and Logic Unit
3.2门电路：
运算优先级：与>或
3.3布尔运算定律
3.4一位全加器
如同手算一样，从低位到高位进行加法运算
3.4.1串行加法器
3.4.1.1单串行加法器
只有一个全加器，数据逐位串行送入到加法器中进行计算，进位触发器用来寄存进位信号，以便下一次运算。
如果操作数长位n位，则要进行n次运算，每次产生一位和，并且逐位送回寄存器中，这样效率不高。
3.4.1.2串行进位的加法器
把n个全加器串接起来，可以进行两个n位数的相加。
始终依赖于低位的进位信号，运算速度还是比较慢。
3.4.2并行加法器
\[ 对于每一位都要进行\\C_i=A_iB_i+(A_i⊕B_i)C_{i-1}\\S_i=A_i⊕B_i⊕C_{i-1} \\设G_i=A_iB_i \quad P_i=A_0⊕B_0 \\则原式=G_i+P_iC_{i-1} \\ \\ 通过展开可得：\\ C_1=G_1+P_1C_0\\ C_2=G_2+P_2C_1=G_2+P_2G_1+P_2P_1C_0\\ C_3=G_3+P_3C_2=G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1C_0 \\... \\C_i的值依赖于P、G、C_0，因此可以直接进行并行计算 \\第i项中的P_iC_{i-1}在后续项中均存在，所以可以设计简化一下电路 \]
继续展开会导致电路越来越复杂，一般只展开4个(4个FA)形成4位的CLA加法器
3.5补码加减运算器
基本（手算）方法：
1 | n bit的补码X+Y：按位相加即可 |
sub=1即采用减法操作，非门对Y进行按位取反，Cin=Sub=1即对Y的末尾+1得到[-Y]补
此电路同时也适合无符号数的加减法运算
3.6加减溢出判断
\[ [A+B]_补=A_补+B_补\\ [A-B]_补=A_补+[-B]_补 \]
只有“正数+正数”才会上溢--正+正=负
只有“负数+负数”才会下溢--负+负=正
3.6.1溢出判断方法一
可以根据上面的规律得到真值表
\[ V=A_sB_s\overline S_s + \overline A_s\overline B_sS_s\\ A_s表示第一个数的符号位，B_s表示第二个数的符号位，S_s表示最终结果符号位 \]
若V=0，表示无溢出；
若V=1，表示有溢出。
3.6.2溢出判断方法二
采用符号位进位和最高数值位的进位进行异或⊕运算判断
\[
V=C_s⊕C_1
\]
3.6.3溢出判断方法三
采用双符号位，正数的符号位为00，负数的符号位为11
对两个符号位S1S2进行异或运算即可
拓展：
- 双符号位补码又称为模4补码，单符号位补码又称为模2补码
- 双符号位实际存储时只存储一个符号位，运算时会复制一个符号位，不会增加存储空间
3.7标志位的生成
注意：OF(Overflow Flag)和SF(Sign Flag)只对有符号数加减运算有意义，CF(Carry Flag)只对无符号数加减运算有意义，ZF(Zero Flag)均有意义。
3.8移位运算
注意：由于原、反、补码的位数有限，因此某些时候移位操作不能精确等效于乘、除法。
3.8.1算数移位
移位：通过改变各个数值位和小数点的相对位置，改变各个数值位的位权，实现乘除法运算
\[
r进制数：K_nK_{n-1}...K_2K_1K_0K_{-1}K_{-2}...K{-n}
\\小数点前移x位相当于÷r^x
\\小数点后移相当于×r^x
\] 
3.8.1.1原码的算数移位
符号位保持不变，仅对数值位进行位移。
右移：高位补0，低位舍弃。若舍弃的位=0，则相当于÷r，若舍弃的位≠0，则丢失相应的精度
左移：低位补0，高位舍弃。若舍弃的位=0，则相当于×r，若舍弃的位≠0，则会出现错误
3.8.1.2反码的算数移位
反码正数的算数位移与原码的一样，
负数由于反码数值位于原码相反，因此，
右移：高位补1，低位舍弃。
左移：低位补1，高位舍弃。
3.8.1.3补码的算数移位
补码正数的算数移位与原码一样，
负数规则如下：
3.8.2逻辑移位
逻辑右移：高位补0，低位舍弃
逻辑左移：低位补0，高位舍弃。
可以看做是对”无符号数“的算数移位
3.8.3循环移位
普通循环移位：
带进位位的循环移位：
方法相同，只是要考虑进位位CF
应用：大端和小端存储之间的转换
3.9乘除法运算
3.9.1原码的乘法运算
手算：
机器实现： \[
设机器字长为n+1=5位(含1个符号位)，[x]_原=1.1101，[y]_原=0.1011，采用原码一位乘法求xy
\\符号位单独处理:符号位=x_s⊕y_s
\\数值位取绝对值进行乘法运算:[|x|]_原=0.1101，[|y|]_原=0.1011
\] 
到最后一步，要处理符号位，
小数点隐含在符号位后面，乘数的符号位不用参与真正的运算，只需要与被乘数的符号位进行异或运算
手算模拟方法：
3.9.2补码的乘法运算
3.9.3定点数的除法运算
3.9.3.1原码除法：恢复余数法
\[ 设机器字长为5位（1位符号位,n=4），x=0.1011,y=0.1101，求x/y \\|x|=0.1011,|y|=0.1101,[|y|]_补=0.1101,[-|y|]_补=1.0011 \\符号位单独处理:符号位=x_s⊕y_s \\数值位取绝对值进行除法计算。 \]
初始状态：
计算机会默认商1，如果商1出现问题再进行商0，并“恢复余数”。
此时发现ACC-(除数)得到的结果是一个负数，所以ACC是比除数小的，所以应该商0，于是：
更改为商0，并将ACC+(除数)，将结果送回ACC，恢复原本余数
此时这一位商已经计算完成，通过逻辑左移，末尾置零，计算下一位。
根据机器字长进行计算，直到计算完成，注意，最后一位商的余数为负的话也需要恢复余数并商0
最终答案的符号位用异或运算得到
手算模拟：
3.9.3.2原码除法：加减交替法（不恢复余数法）
符号位的确定还是需要异或运算，
在最后一步如果余数为负，需商0，并+[|y|]补得到正确的余数
3.9.4补码的除法运算
采用加减交替法，要让符号位参与运算，被除数/余数，除数都采用双符号位
补充：C语言强制类型转换
C语言中定点整数是用“补码”存储的。
无符号数与有符号数：不改变数据内容，只是改变解释方式
1 | void main(){ |
长整数便短等输，高位截断，保留低位
1 | void main(){ |
短整数变长整数，符号拓展
1 | void main(){ |