进位计数法
任意进制转十进制
- 基数：每个数码位用到的不同符号的个数，r进制的基数为r
- 位权：某位数码在对应位置的权重，任意进制转十进制时r为对应进制数
计算公式： \[ K_nK_{n-1}\dots K_1K_0K_{-1}\dots K_{-m}=\\ K_n\times r^n+K_{n-1}\times r^{n-1}+\dots +K_1\times r^1+K_0\times r^0+K_{-1}\times r^{-1}+\dots +K_{-m}\times r^{-m} \]
二进制和八、十六进制转换
二转八：每三位一组转换对应八进制符号
二转十六：每四位一组转换对应十六进制符号
八转二：每位八进制转换对应三位二进制
十六转二：每位十六进制转换对应四位二进制
十进制转任意进制
整数：
短除法除，除数为r进制的r，余数是对应数码位
最后结果从下往上是高到低位
小数：
每次乘2，得到的小数取整数部分
最后结果从上到下是高到低位
定点数的表示
- 定点数：小数点位置固定
- 浮点数：小数点位置不固定（科学计数法）
无符号数
整个机器字长全部二进制位都是数值位，没有符号位
- 表示范围：n位无符号数为\(0\sim2^n-1\)
有符号数
原码
最高位符号位0/1表示正/负，尾数表示真值的绝对值
若字长n+1位，原码整数表示范围为\(-(2^n-1)\leq x\leq 2^n-1\)
若字长n+1位，原码小数表示范围为\(-(1-2^{-n})\leq x \leq 1-2^{-n}\)
真值0有+0和-0两种形式
反码
正数的反码和原码相同
负数的反码数值位全部取反
表示范围相同，真值0也有两种形式
补码
正数的补码和原码相同
负数的补码=反码尾数取反+1
负数补码转原码：尾数取反+1，或找最右边的1及其右侧同原码，左边同反码
速记方法：由x补码求-x补码：符号位和数值位全部取反，然后+1
补码表示0只有一种表示方式
则定点整数补码10000000就可以表示\(-2^7\)，定点小数补码10000000可以表示-1
因此n+1位字长的补码整数的表示范围：\(-2^n\leq x\leq 2^n-1\)
因此n+1位字长的补码小数的表示范围：\(-1\leq x\leq 1-2^{-n}\)
移码
补码基础上将符号位取反
注意移码只能用于表示整数
补码的真值0只有一种形式，表示范围与补码相同
应用：方便比较大小
应用
加减运算
让减法变成加法：
为了让结果能保持在可表示的范围内，我们需要在模\(2^n\)的意义下进行加法操作
在模12的意义下，我们要将需要减的负数找到它等价的一个整数
对于一个负数，它一定能找到一个正数让他俩的绝对值相加等于模数12
如-3和+9在模12的情况下是相同的，他们绝对值相加为12，称互为补数
因此负数需要通过模运算转换，只需要用模数-减数绝对值就可以得到它的补数，其实就是补码，这样就可以让减法操作变为加法
加法操作时，符号位一块参与运算
零扩展与符号扩展
将一个数据拉长bit，多出来的位怎么处理？
对于无符号整数，使用零扩展，多的位补0
对于有符号整数，需要使用符号扩展，多的位与符号位保持一致
运算
加法器
进行加法时，每一位加法都有若干数据：
- 被加数的本位\(A_i\)与加数的本位\(B_i\)
- 来自低位的进位\(C_{i-1}\)
- 本位和\(S_i\)
- 向高位的进位\(C_i\)
我们发现，当\(A_i\)、 \(B_i\)和\(C_{i-1}\)三个中有奇数个1时，\(S_i\)才为1，否则为0
因此\(S_i=A_i\oplus B_i \oplus C_{i-1}\)
产生进位要求两个本位都是1或两个本位中有一个1且来自低位的进位是1
因此\(C_i=A_iB_i+(A_i\oplus B_i)C_{i-1}\)
用门电路表示如下：
将这个电路封装，得到一位全加器（FA）
把n个FA串联起来，就可以进行两个nbits数的相加’
把这n个FA封装，即为加法器
由于两个输入端允许并行输入nbits，又称并行加法器
缺点：由于进位信息是串行的，位数越多，运算速度越慢，又称串行进位加法器
修改一下，加入n位CLA部件，同时传输进位信息，可以弥补缺点
给加法器加入一些标志位，可以判断一些特殊情况
OF：溢出标志，判断带符号数加减运算，1为溢出，0为未溢出
使用\(C_n\oplus C_{n-1}\)计算是否溢出
SF：符号标志，判断带符号数加减运算，1为负，0为正
取最高位\(S_n\)判断
ZF：零标志，1表示结果为0，0表示结果不为0
取所有bit位取或非，全为0是即为1
CF：进位/借位标志，判断无符号数加减运算，1为溢出，0为未溢出
取\(C_{out}\oplus C_{in}\)即\(C_n\oplus C_0\)判断
ALU
ALU是运算器的核心，其中加法器是ALU的核心
ALU负责算术运算、逻辑运算、求补码、直送等
- 由控制器传输mbit控制信号，表示功能
- 标志信息通常送入PSW状态字寄存器（有的称为标志寄存器FR）
若ALU支持k种功能，则控制信号位数\(m\geq \lceil \log_2 k \rceil\)
内部靠一个多路选择器接入k个功能电路实现，传入mbit控制信号分别对应使用某个电路
定点数的移位运算
移位运算即改变各个数码位和小数点的相对位置，改变位权
可以快速实现特殊值的乘除法
逻辑移位
逻辑左移：高位移出丢弃，低位补0
对于无符号整数，每左移一位，相当于乘2
注意：若左移丢弃的位为1，发生溢出
逻辑右移：低位移除丢弃，高位补0
对于无符号整数，每右移一位，相当于除2
注意：若右移丢弃的位为1，丢失精度
算术移位
算术左移：高位移出丢弃，低位补0
对有符号整数，每左移一位，相当于乘2
注意：若算术左移前后符号位不同，则发生溢出
算术右移：低位移出丢弃，高位补符号位
对有符号整数，每右移一位，相当于除2
注意：若右移丢弃的位为1，丢失精度
定点数的加减运算
原码的加减
- 正+正：绝对值做加法，结果为正
- 负+负：绝对值做加法，结果为负
- 正+负/负+正：绝对值大的-小的，符号同绝对值大的
减法运算将减数符号取反，转为加法
补码的加减
带着符号位加减即可，算完后计算原码
对于溢出问题，分为下溢与上溢
- 正+正会发生上溢，得到负数
- 负+负会发生下溢，得到正数
法一：采用一位符号位
若A的符号是\(A_s\)，B的符号是\(B_s\)，运算结果符号是\(S_s\)，则溢出逻辑表达式为\(V=A_sB_s\overline{S_s}+\overline{A_s}\overline{B_s}S_s\)
若V=0表示无溢出，若V=1时表示有溢出
法二：采用一位符号位，根据数据位进位状况判断
- 符号位进位\(C_s=0\)，最高数值位\(C_1=1\)，发生上溢
- 符号位进位\(C_s=1\)，最高数值位\(C_1=0\)，发生下溢
即\(V=C_s\oplus C_1\)，若V=0表示无溢出，若V=1时表示有溢出
法三：采用双符号位
双符号位第一位表示本应得到的符号，第二位表示实际得到的符号
正数符号为00，负数符号位为11
即\(V=C_{s1}\oplus C_{s2}\)，若V=0表示无溢出，若V=1时表示有溢出
实际存储时还是一个符号位，运算时会复制一个
运算电路
无符号数的加减运算
加法
从最低位开始，按位相加，并往更高位进位
减法
被减数不变，减数全部按位取反、末位+1，减法变加法
从最低位开始按位相加，并往更高位进位
溢出
超出\(0\sim 2^n-1\)即溢出
- 无符号加法：最高位产生进位为1时，发生溢出
- 无符号减法：减法变加法，最高位产生进位为0时，发生溢出
无符号整数的乘法
原理
和十进制类似，逐位相乘，错位相加
定义部分积为逐位相乘到当前位的积的结果
- 两个nbit无符号数乘，可以拆为n轮加法运算
- 根据乘数的各个bit，决定每轮加法运算是加被乘数还是加全0
- 注意要错位相加
电路
- 首先将被乘数和乘数放入寄存器X Y，乘积寄存器P置0，计数器\(C_n\)初始值置为n（乘数位数）
- 当乘数和被乘数其中一个为全0，则返回全0
- 重复n轮加法移位计算，直到\(C_n=0\)
- 将Y的最低位送人控制逻辑判断
- 若Y最低位为1，则执行加法，运算结果写回P，进位保存至进位触发器C
- 若Y最低位为0，则什么也不做
- 将C P Y 视为整体，逻辑右移一位
- \(C_n\)减一
- 结束时，乘法运算结果用\(2n\)位保存
- 很多架构中，通常仅保留低n位作为乘积结果，可能溢出
溢出
若高n位不全为0，表示发生溢出，将OF位置为1
（CF标志位只用于无符号加减法溢出，乘法溢出都用OF位标志）
解决方法：
- 不管
- 在乘法指令后执行一条溢出自陷指令（如x86的INTO指令），该指令会检查OF位，若为1就执行操作系统的异常处理程序
有符号整数的乘法
电路
注：符号位参与运算
首先将被乘数和乘数放入寄存器X Y，乘积寄存器P置0，辅助位置为0，计数器\(C_n\)初始值置为n（乘数位数）
当乘数和被乘数其中一个为全0，则返回全0
重复n轮加减移位运算，直到\(C_n=0\)
将Y的最低位和辅助位2bit送入控制逻辑判断
根据Y的最低位和辅助位判断操作：
将P Y 和辅助位视为整体，算术右移一位
\(C_n\)减一
结束时，乘法运算结果用\(2n\)位保存
很多架构中，通常仅保留低n位作为乘积结果，可能溢出
溢出
若高n+1位不全为0，表示发生溢出，将OF位置为1
解决方法：
- 不管
- 在乘法指令后执行一条溢出自陷指令（如x86的INTO指令），该指令会检查OF位，若为1就执行操作系统的异常处理程序
计算机实现乘法的方式
一种改进
之前提到的无符号乘法电路，若实现nbit无符号数相乘，至少需要n个时钟
若改为每轮处理寄存器Y的末尾2bit，仅需n/2个时钟就可以完成运算
阵列乘法器
快速乘法器的一种，可以在一个时钟内完成乘法运算
没有乘法运算电路
可以手动模拟加法和移位操作实现乘法，但是运算速度非常慢
如对于32位，里面有k条指令，所以需要32k个时钟才能实现
无符号整数的除法
中间余数：竖式除法时中间产生的余数
十进制除法上商规则：商×除数的值要尽可能接近但不超过中间余数
二进制除法上商规则：商×除数的值要尽可能接近但不超过中间余数，即如果中间余数>=除数，则商1，否则商0
电路
支持双精度2nbit÷nbit和单精度nbit÷nbit，得到nbit商和nbit余数
若被除数不足2nbit，需要将被除数扩展为2nbit
- 上商规则：若\(R-Y\geq0\)则商1，否则商0
- 首先将数据放入寄存器，除数放入Y，被除数放入R Q，完成零扩展
- 计数器初始值\(C_n=n\)
- 特殊情况检查：
- 若除数为0，发生异常，停止除法运算并调用异常处理程序
- 若|被除数|<|除数|，则商=0，余数=被除数，除法器不再执行
- 进行n+1轮处理
- 第1轮特殊处理：
- 直接上商，若第一位商1，发生商溢出，停止除法运算
- 直接上商，肉第一位商0，不会商溢出，不必保存这位商，也不\(C_n--\)，继续
- 其余n轮处理：
- 先左移，空出的位用于上商
- 上商，背后可能会进行加法/减法
- 计数器\(C_n--\)，当计数器为0时结束运算
- 寄存器R保存余数，寄存器Q保存商
溢出
只有双精度除法可能发生商溢出
有符号整数的除法
电路
初始化
- nbit被除数符号扩展为2nbit，放入寄存器R Q
- nbit除数放入寄存器Y
- 计数器重置为\(C_n=n\)，表示剩余n轮
进行n轮处理，先左移，空出的位置上商
- 由控制逻辑根据中间余数与除数的符号组合来决定加减法（同号减，异号加）
- 再根据ALU运算结果（新余数）的符号位决定商1还是0
- 新老余数相比，符号不变：商1，符号变：商0，新余数写入
- 若符号位发生变化，余数计数器R会将余数恢复成老余数
计数器\(C_n--\)，\(C_n=0\)时除法运算结束
当\(C_n=0\)时，除法运算结束，R保存余数，Q保存商
- 若原被除数和除数异号，商Q还需要取补
特殊情况：
- 如果|被除数|<|除数|，则商为0，余数=被除数，除法器不必再执行
- 如果除数为0，发生除数为零异常，停止运算并调用异常处理程序
- 对于补码的单精度除法，仅绝对值最大的负数÷-1才有可能发生商溢出
IEEE 754浮点数
规格化：确保尾数最高位非零数位刚好在小数点前
如二进制小数\(-110.11\)，规格化后为\(-1.1011\times 2^2\)
其中：
- 符号决定正负性
- 尾数1.1011影响数值精度，位数越多精度越高
- 阶码2反应小数点的实际位置
- 基数2表示2进制，k进制默认基数为k
格式
float：
double：
- 阶码越大，表示范围越大
- 尾数越大，表示精度越大
单精度浮点存储
- 符号：0正1负
- 尾数：规定小数点位置在23bit前，默认存储规格化尾数，小数点前的1省略
- 阶码：用移码表示，规定偏置值为127（\(2^{阶码-1}-1\)）
- 基数：不用专门存储，规定为2即可
如何将十进制真值转为偏置值为M的移码：
- 将十进制真值+偏置值M
- 按无符号整数规则转换为指定位数
双精度浮点存储
- 符号：0正1负
- 尾数：规定小数点位置在52bit前，默认存储规格化尾数，小数点前的1省略
- 阶码：用移码表示，规定偏置值为1023（\(2^{阶码-1}-1\)）
- 基数：不用专门存储，规定为2即可
表示范围
规格化浮点
规格化浮点数：阶码部分不全为0且不全为1的浮点数
阶码：真值取值范围\(-126\sim 127\)
上溢：运算结果大于最大规格化正数称为正上溢，小于绝对值最大的规格化负数时称为负上溢
正上溢的结果设置为+∞，负上溢为-∞，并设置溢出异常标志位（x86中为OE）
IEEE 754规定默认不响应浮点数溢出异常，不中断程序
下溢：运算结果在0至绝对值最小的规格化正数之间时称为正下溢，在0至绝对值最小的规格化负数之间时称为负下溢
下溢时若结果落入非规格化区间，用非规格化浮点数存储，若结果太小，按机器零存储
若下溢至机器0，设置浮点数下溢异常标志位（x86中为UE）
真值0
非规格化浮点
非规格化正数的阶码要固定解读为最小真值-126
尾数小数点前隐含0而不是1
0除0、负数开根号、∞-∞结果均为NaN
非零数值除以0，结果为±∞
加减运算
步骤
对阶：对齐为相同数阶码，小阶向大阶对齐
IEEE规定右移移出的bit至少额外保留三位
尾数加减：尾数相加减，更可能得到规格化的尾数
尾数规格化：若未规格化，需要左右规格化
尾数舍入处理：若规定只保留n位有效尾数，多余的尾数：
- 直接舍弃
- 若舍弃部分非0，则入1
- 四舍五入
溢出判断：若规定阶码不能超过x，且运算后阶码超出范围则发生溢出
舍入问题
默认就近舍入：
类似零舍一入，即更高位为0舍去，1进位
若三个舍弃位刚好为100，则看前一位，若1+23bit的末位为0，则直接截取多余位，否则进位1
溢出问题
上溢：
浮点数溢出不以尾数溢出判断，尾数溢出可以通过右规纠正
是否溢出主要看指数是否上溢
如：
X=0 11111110 0000000000000000000000
Y=0 11111110 1000000000000000000000
求X+Y
对阶，尾数加减后得到尾数原码为+10.1000000000000000000000
进行规格化，尾数原码变为1.01000000000000000000000，阶码+1变为11111111，此时阶码全1发生上溢，尾数强制置为0
结果为正无穷
下溢：
如：
X=0 00000001 00000000000000000000001
Y=1 00000001 00000000000000000000000
求X+Y
对阶，尾数加减后得到尾数原码为+0.00000000000000000000001
进行规格化，如果尾数继续左移，阶码需要-1，变为00000000，此时变为非规格化浮点数
若当前阶码已经为00000001但尾数需要左规，直接把阶码置为全0，尾数不移位
结果为0 00000000 00000000000000000000001
阶码全0，发生下溢，进入非规格化浮点数区间，则结果为\(2^{-149}\)
数据的存储和排列
大小端
多字节数据在内存里一定是占连续的几个字节，其中最左边为最高有效字节MSB，最右边为最低有效字节LSB
- 大端法：把MSB存到更低地址部分，LSB存到更高地址部分
- 小端法：把MSB存到更高地址部分，LSB存到更低地址部分
机器更适于读小端法
边界对齐
现代计算机通常按字节寻址，每个字节对应一个地址
也可以按照字、半字寻址
若存储字长为32位，则一个字=32bit，半字=16bit，每次访存只能读写一个字
按字寻址时，将字的编号左移2就是对应字的地址，按半字是左移1
因此，结构体中如果有多个变量，他们的排布有边界对齐和不对齐两种方式，边界对齐时多出的空间放不下下一个数据类型时，会空出来，这样可以空间换时间，访问一个字和半字时都只需要一次访存
