第二章-数据的表示和运算

2.1进位计数制

1.r进制计数法

• r进制: $K_nK_{n-1}...K_2K_1K_0K_{-1}K_{-2}...K_{-m}=K_n\times r^n+K_{n-1}\times r^{n-1}+...+K_2\times r^2+K_1\times r^1+K_0\times r^0+K_{-1}\times r^{-1}+K_{-2}\times r^{-2}+...+K_{-m}\times r^{-m}$
• 基数: 每个数码位所用到的不同符号的个数, r进制的基数为r

2.任意进制转十进制

• $K_nK_{n-1}...K_2K_1K_0K_{-1}K_{-2}...K_{-m}=K_n\times r^n+K_{n-1}\times r^{n-1}+...+K_2\times r^2+K_1\times r^1+K_0\times r^0+K_{-1}\times r^{-1}+K_{-2}\times r^{-2}+...+K_{-m}\times r^{-m}$

3.二进制转八进制和十六进制

• 二进制转八进制: 3位为一组, 每组转换成对应的八进制符号
• 二进制转十六进制: 4位为一组, 每组转换成对应的十六进制符号

4.八进制和十六进制转二进制

• 八进制转二进制: 每位八进制对应3位二进制
• 十六进制转二进制: 每位十六进制对应4位二进制

5.常用进制的书写方式

• 二进制: $(1010101000001010)_2\quad 1010101000001010B$
• 八进制: $(1652)_8$
• 十六进制: $(1652)_{16}\quad 1652H\quad Ox1652$
• 十进制: $(1652)_{10}\quad 1652D$

6.十进制转化为任意进制

除基取余法证明(整数部分)

1. $\frac{K_n\times r^n+K_{n-1}\times r^{n-1}+...+K_2\times r^2+K_1\times r^1+K_0\times r^0}{r}=K_n\times r^{n-1}+K_{n-1}\times r^{n-2}+...+K_2\times r^1+K_1\times r^0...K_0$(余数)
2. 令$K_n\times r^{n-1}+K_{n-1}\times r^{n-2}+...+K_2\times r^1+K_1\times r^0=x$
3. $K_n\times r^n+K_{n-1}\times r^{n-1}+...+K_2\times r^2+K_1\times r^1+K_0\times r^0$可表示为$rx+K_0$
4. 由于$K_0∊[0, r-1], 所以\frac{rx+K_0}{r}$所得的商为$x$, 余数为$K_0$
5. 用得到的商除以r, 依次得到余数$K_n$

乘积取整法证明(小数部分)

1. $(K_{-1}\times r^{-1}+K_{-2}\times r^{-2}+...+K_{-m}\times r^{-m})\times r=K_{-1}\times r^{0}+K_{-2}\times r^{-1}+...+K_{-m}\times r^{-(m-1)}$
2. 得到的整数部分$K_{-1}\times r^{0}$为$K_{-1}$的值
3. 将剩下的小数部分$K_{-2}\times r^{-1}+...+K_{-m}\times r^{-(m-1)}$乘以$r$, 得到$K_{-2}$的值
4. 用得到的小数部分乘以$r$, 依次得到$K_{-m}$

若小数部分的无论经过多少次的乘法都无法得到准确的二进制表示, 则要保留一定的精度(不是每个十进制的小数都能用二进制精确的表示, 但是任意一个二进制的小数都可以用十进制小数表示)

7.真值和机器数

在计算机中, 常常采用数的符号和数值一起编码的方法来表示数据. 常用的有原码、反码、补码、移码

• 真值: 带正负号的数
• 机器数: 数的符号和数值一起编码，0正1负

2.2 BCD码(Binary-Coded Decimal)（大纲已删除）

• BCD码通常采用4位二进制数来表示一位十进制数中的0-9这10个数码. 但4位二进制数可以组合出16种代码, 因此必有6种状态为冗余状态

1.8421码

映射关系:

0	1	2	3	4	5	6	7	8	9
0000	0001	0010	0011	0100	0101	0110	0111	1000	1001

如“985”对应的8421码为100110000101

加法运算

• 手算: 可以先将8421码转化为十进制, 再将十进制运算结果转化为8421码
• 机算: 如果二进制加法的结果落在1010-1111中(10-15中), 在运算的结果上再加上6

余3码

8421码+(0011)2, 映射关系:

0	1	2	3	4	5	6	7	8	9
0011	0100	0101	0110	0111	1000	1001	1010	1011	1100

2421码

改变权值定义, 映射关系:

0	1	2	3	4	5	6	7	8	9
0000	0001	0010	0011	0100	1011	1100	1101	1110	1111

特点: 大于等于5的4位二进制数中的最高位为1, 小于5的最高位为0. 如5->1011而非0101

2.3 字符与字符串

1.ASCII码

• 将数字、字母、符号共128个字符用7位二进制编码表示
• 可印刷字符: 32-126, 其余为控制、通信字符

2.汉字的表示和编码

GB 2312-80

• 汉字+各种符号共7445个
• 区位码: 用两个字节表示一个汉字, 每字节用七位码, 并将汉字和图形符号排列在一个94行94列的二维代码表中. 区位码是4位十进制数, 前2位是区码, 后2位是位码
• 国标码 = (区位码)16 + 2020H
• 汉字内码 = (国标码)16 + 8080H

为什么要加上2020H和8080H

https://blog.csdn.net/zrf2112/article/details/50718684

• 为啥要将区位码转化为国标码?
  • 汉字编码之前, 已经有了标准的ASCII, 开发者只沿用了ASCII中32个控制字符其他ASCII被覆盖. 通过32D=20H的关系, 不难发现, 加上2020H是为了绕开ASCII的控制字符
• 为啥要将国标码转化为机内码?
  • 国标码中除了前面32个控制字符外, 其他ASCII内容被覆盖, 这使得使用者在使用采用ASCII码编码的网页或者文本内容时不能兼容, 只能看到乱码. 为了解决这个问题要在国标码的基础上补充ASCII的32个控制字符外的其他字符. 已知道标准的ASCII码最高位为0, 国标码的最高位也是0. 那么只需要在国标码的基础上将最高位改为1即可. 通过10000000B=80H的关系, 不难发现, 加上8080H是为了在国标码基础上解决ASCII字母等符号的兼容性问题

流程

• 输入: 输入编码, 如“内”汉字, 举个例子, 输入编码为“nei2”, 将输入编码转化为国标码, 在通过系统软件将国标码转化为机内码存储在计算机中
• 输出: 汉字字形码. 先将机内码转化为国标码, 再转化为字形码

3.字符串

1. 某计算机按字节编址(每个字节对应1B), 从地址为2的单元开始, 存储字符串“abc”

		61H	62H	63H	00H

很多语言中, 将'\0'作为字符串结束的标志

2. 某计算机按字节编址(每个字节对应1B), 从地址为2的单元开始, 存储字符串“abc啊”. “啊”的机内码为B0 A1H

在所有计算机中, 多字节数据都被存放在连续的字节序列中. 根据数据中各字节排列顺序的不同, 可能有“大端模式”和“小端模式”

• 大端模式: 将数据的最高有效字节存放在低地址单元中

		61H	62H	63H	00H	B0H	A1H	00H

• 小端模式: 将数据的最高有效字节存放在高地址单元中

		61H	62H	63H	00H	A1H	B0H	00H

2.4奇偶校验码

1.校验原理简介

• 2bit映射到4个合法状态

信息	A	B	C	D
编码	00	01	10	11

• 3bit映射到4个合法状态(有4个冗余的非法状态)

信息	A	B	C	D
编码	100	001	010	111

• 由若干位代码组成的一个字叫做码字
• 将两个码字逐位进行对比, 具有不同的位的个数称为两个码字间的距离
• 一种编码方案可能有若干个合法的码字, 各合法的码字间的最小距离为“码距”. 如第一种情况, 码距为1, 即改变1位二进制位就有可能从一个合法的码字转变为另一个合法的码字; 第二种情况, 码距为2, 即改变1位二进制位只能使得从一个合法的码字转变为一个非法的码字.
• 当码距d=1时, 无检错能力; 当d=2时, 有检错能力; 当d≥3时, 若设计合理, 可能具有检错、纠错能力

2.奇偶检验法

• 整个校验码(有效信息位和校验位)中“1”的个数为奇数
• 整个校验码(有效信息位和校验位)中“1”的个数为偶数

Q: 给出两个编码1001101和1010111的奇检验码和偶检验码
设最高位为奇校验位, 余7位为信息位,则对应的奇偶检验码为:

• 奇检验: 11001101; 01010111
• 偶校验: 01001101; 11010111

• 偶检验的硬件实现: 第一步, 各个信息进行异或(模2加)运算, 得到的课结果即为偶检验位. 第二步, 进行偶校验, 所有的位进行异或, 若结果为1说明出错

2.5 海明校验码

1.思路简介

• 偶检验: 1010 -> 01010, 能发现奇数位错误, 但无法确定是哪一位出错
• 海明码设计思路: 将信息位分组进行偶检验 -> 多个校验位

2.求解步骤

1. 确定海明码的位数
2. 确定校验位的分布
3. 求校验位的值
4. 纠错

确定海明码的位数

设n为有效信息位位数, k位校验位位数, 校验位有2^k种状态, 信息位加检验位共n+k位, 出错的情况有n+k种(1位出错), 成功的情况有1种. 所以k和n的关系应该满足: $2^k≥n+k+1$

确定校验位的分布

校验位Pi放在海明位号为$2^{i-1}$的位置上

求校验位的值

将信息位所处的位置转换为二进制数. 将校验位所处的位置理解为权重, 通过异或运算得出校验位的值(基于偶校验)

纠错

将分组中的值进行异或运算, 如果没有出错的话, 得到的结果应该是0(基于偶校验)

3.海明码的检错、纠错能力

• 纠错能力 -- 1位
• 检错能力 -- 2位

信息位: 1010

1. 确定位数: $2^k≥n+k+1$ n=4 -> k=3
   设信息位D4D3D2D1, 校验位P3P2P1, 对应的海明码为H7H6H5H4H3H2H1
2. 确定校验位的分布

H7	H6	H5	H4	H3	H2	H1
D4	D3	D2	P3	D1	P2	P1
1	0	1		0

3. 求校验位的值
   H3: 3 -> 011
   H5: 5 -> 101
   H6: 6 -> 110
   H7: 7 -> 101
   $P_1=H_3\oplus H_5\oplus H_7=D_1\oplus D_2\oplus D_4=0$
   $P_2=H_3\oplus H_6\oplus H_7=D_1\oplus D_3\oplus D_4=1$
   $P_3=H_5\oplus H_5\oplus H_7=D_2\oplus D_3\oplus D_4=0$

H7	H6	H5	H4	H3	H2	H1
D4	D3	D2	P3	D1	P2	P1
1	0	1	0	0	1	0

4. 纠错
   校验方程:
   $S_1=P_1\oplus D_1\oplus D_2 \oplus D_4$ 1357
   $S_2=P_2\oplus D_1\oplus D_3 \oplus D_4$ 2367
   $S_3=P_3\oplus D_2\oplus D_3 \oplus D_4$ 4567
   接收到: 1010010
   $S_1=P_1\oplus D_1\oplus D_2 \oplus D_4=0$
   $S_2=P_2\oplus D_1\oplus D_3 \oplus D_4=0$
   $S_3=P_3\oplus D_2\oplus D_3 \oplus D_4=0$
   故无错误
   接收到: 1010000
   $S_1=P_1\oplus D_1\oplus D_2 \oplus D_4=0$
   $S_2=P_2\oplus D_1\oplus D_3 \oplus D_4=1$
   $S_3=P_3\oplus D_2\oplus D_3 \oplus D_4=0$
   故第010位出错
   
5. 全校验位
   $S_3S_2S_1=000$且全体偶校验成功->无错误
   $S_3S_2S_1≠000$且全体偶校验失败->有1位错误, 纠正即可
   $S_3S_2S_1≠000$且全体偶校验成功->有2位错误, 需要重新传输

H8	H7	H6	H5	H4	H3	H2	H1
P全	D4	D3	D2	P3	D1	P2	P1
1	1	0	1	0	0	1	0

2.6 循环冗余校验码

1.基本思想

数据发送、接受方约定一个“除数”, K个信息位+R个校验位作为“被除数”, 添加校验位后需要保证除法的余数为0. 收到数据后, 进行除法检查余数是否为0. 若余数非0说明出错, 则进行重传或者纠错

2.步骤

移位

将原信息码左移R位(多项式最高次项的次数), 低位补0

相除

• 对移位后的信息码, 用生成的多项式进行模2除法, 产生余数, 得到的余数就是校验码
• 模2除法: 模2加法和模2减法的结果相同, 都是异或运算. 模2除法和算数除法类似, 但每位除(减)的结果不影响其他位, 步骤如下:
  • ①用除数对被除数最高几位做模2减运算(异或)不错位;
  • ②除数右移1位, 若余数的最高位为1, 商为1, 并对余数做模2减运算. 若余数最高位为0, 商为0, 余数继续右移1位;
  • ③ 循环直到余数位数小于余数时, 该余数为最终余数.

检错和纠错

• 将接收端收到的CRC码, 用生成多项式G(x)做模2除法, 若余数为0, 则码字无错
• K个信息位, R个校验位, 若生成多项式选择得当, 且$2^R≥K+R+1$, 则CRC码可以纠正1位错(无法纠正的情况, 看下面例子)
• 在实际应用当中, 这种校验码一般只用来检错, 因为信息位实在是太长了
• 理论上可以证明循环冗余校验码的检错能力有以下几点:
  • 可检测出所有奇数个错误
  • 可检测出所有双比特的错误
  • 可检测出所有小于等于校验长度的连续错误

Q: 设生成多项式为$G(x)=x^3+x^2+1$, 信息码为101001, 求对应的CRC码
R=生成多项式的最高幂次=3, K=信息码的长度=6, N=K+R=9
生成多项式G(x)对应的二进制码为1101

1. 移位
   将原信息码左移R位, 低位补0, 得到了101001000
2. 相除
   
   最终得到的余数为001, 则CRC码为101001001
3. 检错和纠错
   发送: 101001001 记为$C_9C_8C_7C_6C_5C_4C_3C_2C_1$
   接收: 101001001 用1101进行模2除 余数为000, 代表没有出错
   接收: 101001011 用1101进行模2除 余数位010, 代表C2出错
   
   注意: 余数为010并不一定代表C2出错
   
   3个bit位最多只能表示8种状态(注意这里的出错位不是余数二进制转十进制!), 000表示正确状态. 从表中可以看出, 如果第9位出错的话, 余数也为010. 但不能说CRC码没有纠错能力, 只是本例中的信息位太长

2.7 定点数的表示

1.定点数和浮点数

• 定点数: 小数点的位置固定
• 浮点数: 小数点的位置不固定

2.无符号数的表示

• 无符号数: 整个机器字长的全部二进制位为数值位, 没有符号位, 相当于数的绝对值
• n位二进制数能够表示的范围: $0$ ~ $2^n-1$, 有$2^n$种不同的状态
• 通常只有无符号整数, 而没有无符号小数

3.有符号数的表示

• 可用原码、反码、补码三种方式来表示定点整数和定点小数, 还可以用移码表示定点整数
• 若真值为x, 则用[x]原、[x]反、[x]补、[x]移分别表示真值对应的原码、反码、补码、移码
• 注意: 定点小数是纯小数, 定点整数是纯整数

4.原码

原码: 用尾数表示真值的绝对值, 符号位"0/1"对应"正/负"

表示+19D

0	0	0	1	0	0	1	1

表示-19D

1	0	0	1	0	0	1	1

常写为[x]原=1, 0010011
如果未指明机器字长, 也可以写为[x]原=1, 10011

表示+0.75D

0	1	1	0	0	0	0	0

表示-0.75D

1	1	1	0	0	0	0	0

常写为: [x]原=1.1100000

表示范围

真值0有两种表示形式: +0和-0

• 原码整数: 若机器字长为$n+1$位, 原码整数的表示范围: $-(2^n-1)\leq x \leq 2^n-1$(关于原点对称). ($n+1$个字节总共能表示的状态的个数为$2^{n+1}$个, 但实际只能表示$2^{n+1}-1$个数, 原因就是真值0有两种表示形式)
• 原码小数: 若机器字长为$n+1$位, 原码小数的表示范围: $-(1-2^{-n})\leq x\leq 1-2^{-n}$(关于原点对称)

5.反码

• 若符号位为0, 则反码与原码相同
• 若符号位为1, 则数值位全部取反

表示范围

真值0有+0和-0两种形式
[+0]原=00000000 [-0]原=10000000
[+0]反=00000000 [-0]反=11111111

• 反码整数: 若机器字长$n+1$位, 反码整数的表示范围: $-(2^n-1)\leq x\leq 2^n-1$(关于原点对称)
• 反码小数: 若机器字长$n+1$位, 反码小数的表示范围: $-(1-2^{-n})\leq x\leq 1-2^{-n}$(关于原点对称)

6.补码

• 正数的补码=原码
• 负数的补码=反码末位+1(要考虑进位)
• 将负数补码转回原码的方法相同, 尾数取反, 末位+1

表示范围

真值0的补码形式是唯一的, [+0]补=[-0]补=00000000
定点整数补码[x]补=1, 0000000表示$x=2^7$
定点小数补码[x]补=1. 0000000表示$x=-1$

• 补码整数: 若机器字长为$n+1$位, 补码整数的表示范围: $-2^n\leq x\leq 2^n-1$(比原码多表示一个$-2^n$)
• 补码小数: 若机器字长为$n+1$位, 补码小数的表示范围: $-1\leq x\leq 1-2^{-n}$(比原码多表示一个$-1$)

7.移码

移码: 补码的基础上将符号位取反. 注意: 移码只能适用于表示整数

表示范围

移码的真值0和补码一样只有一种表示形式, [+0]移=[-0]移=10000000

• 移码整数: 若机器字长为$n+1$位, 移码整数的表示范围: $-2^n\leq x\leq 2^n-1$(与补码相同)

作用

移码保持了数据原有的大小顺序, 移码大真值就大, 移码小真值就小

8.用几种码表示定点整数

2.8 各种码的作用

1.加减运算

使用原码运算:

• 加法: 用加法器完成
• 减法: 用减法器完成

由于减法器的电路结构复杂, 所以一般用加法代替减法运算

2.模运算的性质

• 带余除法: 设x, m∊Z, m>0则存在唯一确定的整数q和r, 使得: x=qm+r, 0≤r<m
• 在(mod m)的条件下, 若能找到负数的补数, 就可以用正数的加法等价替代减法
• 设a为负数, 则a的补数(其实就是a的补码)+a的绝对值=模

-3mod12=9, 因为-3=(-1)*12+9
9mod12=9
21mod12=9
33mod12=9
-15mod12=9

(mod 12)把所有整数分为12类(余数为0~11)
mod 12余数相同的数, 都是同一类, 都是等价的
即10+(-3)、10+9、10+21...在(mod 12)的条件下效果相同
-3和9互为补数, 二者的绝对值之和=模

3.加减运算

• 任何运算结果在(mod 2^8)以后只保留最低8位
• 补码: 让减法操作转变为加法操作, 节省硬件的成本
• 模-a的绝对值=a的补数(a为负数)
• 补码的作用: 使用补码可将减法操作转变为等价的加法, ALU中无需集成减法器. 执行加法操作时, 符号位一起参与运算

2.9移位运算

1.原码的算术移位

原码的算数移位: 保持符号位不变, 仅对数值进行移位

符	2^6	2^5	2^4	2^3	2^2	2^1	2^0	实际值	操作
1	0	0	1	0	1	0	0	-20D
1	0	0	0	1	0	1	0	-10D	右移一位
1	0	0	0	0	1	0	1	-5D	右移两位
1	0	0	0	0	0	1	0	-2D	右移三位

右移: 高位补0, 低位舍弃. 若舍弃的位=0, 则相当于除以2; 若舍弃的位≠0, 则会丢失精度

符	2^6	2^5	2^4	2^3	2^2	2^1	2^0	实际值	操作
1	0	0	1	0	1	0	0	-20D
1	0	1	0	1	0	0	0	-40D	左移一位
1	1	0	1	0	0	0	0	-80D	左移两位
1	0	1	0	0	0	0	0	-32D	左移三位

2.反码的算术移位

反码的算数移位--正数的反码和原码相同, 因此对正数反码的移位运算也和原码相同

右移: 高位补0, 低位舍弃
左移: 低位补0, 高位舍弃

反码的算数移位--负数的反码数值位与原码相反, 因此负数反码的移位运算规则如下

右移: 高位补1, 低位舍弃
左移: 低位补1, 高位舍弃

3.补码的算数移位

补码的算数移位--正数的补码与原码相同, 因此对正数补码移位运算也和原码相同

右移: 高位补0, 低位舍弃
左移: 低位补0, 高位舍弃

补码的算数移位--负数的补码=反码末位+1, 导致反码最右边几个连续的1都因进位而变为0, 直到碰到第一个0为止.
规律--负数补码中, 最右边的1及其右边同原码, 最右边的1的左边同反码

负数移位的算数移位规则如下:
右移(同反码): 高位补1, 低位舍弃
左移(同原码): 低位补0, 高位舍弃

4.算数移位总结

	码制	添补代码
正数	原码\补码\反码	0
负数	原码	0
负数	补码	左移添0
负数	补码	右移添1
负数	反码	1

左移相当于*2, 右移相当于/2
由于位数有限, 因此有时候无法用算数移位精确地等效乘除法

5.逻辑移位

逻辑移位可以看作是对无符号数的移位

移位规则:
逻辑左移时, 舍弃高位, 低位补0
逻辑右移时, 舍弃低位, 高位补0

6.循环移位

带进位位的循环左移

• 不带进位位：移出来的不仅要去另一头，还要去进位位
• 带进位位：移出来的去进位位，进位位去空出来的地方

2.10 加减运算和溢出运算

1.原码的加减运算

加法器直接对原码进行加法运算, 可能出错, 需要用减法器实现

原码的加法运算:
正+正 -> 绝对值做加法, 结果为正
负+负 -> 绝对值做加法, 结果为负
正+负 -> 绝对大的减绝对值小的, 符号同绝对值大的数
负+正 -> 绝对值大的减绝对值小的, 符号同绝对值大的数

原码的减法运算, "减数"符号取反, 转变为加法:
正-负 -> 正+正
负-正 -> 负+负
正-正 -> 正+负
负+正 -> 负-负

2.补码的加减运算

对于补码来说, 无论加法还是减法, 最后都会转变为加法, 由加法器实现运算, 符号位也参与运算

负数补码转化为原码的方式

• 数值位取反+1
• 负数补码中, 最右边的1及其右边同原码. 最右边的1的左边同反码

溢出判断

设机器的字长为8位(含1位符号位), A=15, B=-24
C=124, 求[A+C]补和[B-C]补
[A+C]补=0,000111+0,1111100=1,0001011 真值-117
[B-C]补=1,1101000+1,0000100=0,1101100 真值+108

• 只有"正数+正数"才会上溢--正+正=负
• 只有"负数+负数"才会下溢--负+负=正

方法一 采用一位符号位

采用一位符号位, 设A的符号为As, B的符号为Bs, 运算结果的符号为Ss, 则溢出逻辑表达式为$V=A_sB_s\overline{S_s}+\overline{A_s}\overline{B_s}S_s$

若V=0, 表示无溢出
若V=1, 表示有溢出

溢出的两种情况:
As为1且Bs为1且Ss为0
As为0且Bs为0且Ss为1

方法二 采用一位符号位根据数据位的进位情况判断溢出

采用一位符号位, 根据数据位进位情况判断溢出

	符号位的进位Cs	最高数值位的进位C1
上溢	0	1
下溢	1	0

即: Cs与C1不同时有溢出
处理不同的逻辑符号: 异或⊕
溢出逻辑判断表达式为V=Cs⊕C1
若V=0, 表示无溢出; V=1, 表示有溢出

方法三 采用双符号位

正数符号为00, 负数符号为11

记两个符号位为Ss1,Ss2, 则V=Ss1⊕Ss2
若V=0, 表示无溢出; 若V=1, 表示有溢出

双符号位补码又称: 模4补码 单符号位补码又称: 模2补码

3.符号扩展

正整数

01011010 -> 0000000001011010

负整数

	转换前	转换后
原码	11011010	1000000001011010
反码	10100101	1111111110100101
补码	10100110	1111111110100110

正小数

0.1011010 -> 0.101101000000000

负小数

	转换前	转换后
原码	1.1011010	1.101101000000000
反码	1.0100101	1.010010111111111
补码	1.0100110	1.010011000000000

• 定点整数的符号扩展: 在原符号位和数值位中间添加新位, 正数都添0; 负数原码添0, 负数反, 补码添1
• 定点小数的符号扩展: 在原符号位和数值位后面添加新的位, 正数都添0; 负数原, 补码添0, 负数反码添1

2.11 原码乘法运算

1.原码一位乘法

符号单独处理:

• 符号位=$X_s⊕Y_s$
• 数值位取绝对值进行乘法计算

实现方法: 先加法再移位, 重复n次

手算实现方法

• 乘数的符号位不参与运算, 可以忽略
• 原码一位乘可以只用单符号位
• 答题时最终结果最好写为原码机器数

原码一位乘法:
符号位通过异或确定; 数值部分通过被乘数和乘数绝对值的n轮加法, 移位完成. 根据当前乘数中参与运算的位确定(ACC)加什么. 若当前运算位=1, 则(ACC)+[|x|]原; 若当前运算位=0, 则(ACC)+0
每轮加法后ACC, MQ的内容统一逻辑右移

机器实现方法

2.11 补码的乘法运算

1.补码一位乘法(Booth算法)

原码一位乘法和补码一位乘法的区别

原码一位乘法

• 原码中每次加法可能+0, +[|x|]原
  • MQ中最低位=1时, (ACC)+[|x|]原
  • MQ中最低位=0时, (ACC)+0
• 进行n轮加法, 移位
• 每次移位都是"逻辑右移"
• 符号位不参与运算

补码一位乘法

• 每次加法可能+0, +[x]补, +[-x]补
  • 辅助位-MQ中最低位=1时, (ACC)+[x]补
  • 辅助位-MQ中最低位=0时, (ACC)+0
  • 辅助位-MQ中最低位=-1时, (ACC)+[-x]补
• 进行n轮加法, 移位, 最后再多来一次加法
• 每次移位都是"补码的算数右移"
• 符号位参与运算

机器实现

手算实现

• n轮加法, 算数右移, 加法规则如下:
  • 辅助位-MQ中最低位=1时, (ACC)+[x]补
  • 辅助位-MQ中最低位=0时, (ACC)+0
  • 辅助位-MQ中最低位=-1时, (ACC)+[-x]补
• 补码的算数右移:
  • 符号位不动, 数值位右移, 正数右移补0, 负数右移补1(符号位是啥就补啥)

2.12 原码的除法运算

不恢复余数法

手算除法(二进制)

设机器字长为5位(含1位符号位, n=4), x=0.1011, y=0.1101, 求x/y
规律: 忽略小数点, 每确定一位商, 进行一次减法, 得到4位余数, 在余数的末尾补0, 再确定下一位商, 确定5位商即可停止(机器字长为5位)

机器实现

符号位

符号单独处理: 符号位=Xs⊕Ys

数值位

• 计算机很傻, 会先默认上商1, 如果搞错了再改上商0, 并"恢复余数"
• ACC, MQ整体"逻辑左移". ACC高位丢弃, MQ低位补0

手算实现

恢复余数法

加减交替法(不恢复余数法)

若余数a为负, 则可直接商0, 并让余数左移1位再加上|除数|

区别

• 恢复余数法: 当余数为负时商0, 并+|除数|, 再左移, 再-|除数|
• 加减交替法: 当余数为负时商0, 并左移, 再+|除数|

注意

• 余数的正负性和商相同
• 若余数为负数, 则需要商0, 并+[|y|]补得到正确余数

2.13 补码的除法运算

加减交替法

补码除法:

• 符号位参与运算
• 被除数/余数, 除数采用双符号位

被除数和除数同号, 则被除数减去除数, 异号则被除数加上除数

余数和除数同号, 商1, 余数左移一位减去除数;
余数和除数异号, 商0, 余数左移一位加上除数;
重复n次

除法运算回顾

除法类型	符号位参与运算	加减次数	方向	次数	上商, 加减原则	说明
原码加减交替法	否	N+1或N+2	左	N	余数的正负	若最终余数为负, 需要恢复负数
补码加减交替法	是	N+1	左	N	余数和除数是否同号	商末位恒置1

2.14 强制类型转换

代码

void main() {
    short x = -4321; // short类型占用2个字节, x: 1110 1111 0001 1111
    unsigned short y = (unsigned short)x; // 会将x的二进制数值完整地复制给y, y的值为1110 1111 0001 1111, 真值为61215. 无符号数与有符号数, 不改变数据内容, 改变解释方式
    int a = 165537, b = -34991; // int型占用4个字节, a:0x000286a1, b:0xffff7751
    short c = (short)a, d = (short)b; // short型占用2个字节, 长整数变短整数: 高位截断, 保留低位, c:0x86a1, 真值:-31071; d:0x7751, 真值:30545
    short x = -4321; // x:1110 1111 0001 1111 x:0xef1f
    int m = x; // m:1111 1111 1111 1111 1110 1111 0001 1111 m:0xffffef1f 真值:-4321
    unsigned short n = (unsigned short)x; // n:1110 1111 0001 1111 0xef1f 真值:61215
    unsigned int p = n; // p:0000 0000 0000 0000 1110 1111 0001 1111 0x0000ef1f 真值61215
}

2.15 数据的存储和排列

大小端模式

4字节int: 01 23 45 67H -> 19088743D -> 0000 0001 0010 0011 0100 0101 0110 0111B
最高有效字节为01(MSB), 最低有效字节为67(LSB)

• 大端模式: 最高的有效字节存储在更低地址的部分, 最低有效字节存储在更高地址的部分(更适合人类阅读)
• 小端模式: 最低的有效字节存储在更低地址的部分, 最高有效字节存储在更高地址的部分(更适合机器存储)

边界对齐

现代计算机通常是按字节编址, 即每个字节对应1个地址
通常也支持按字, 按半字, 按字节寻址
假设存储字长为32位, 则1个字=32bit, 半字=16bit. 每次访存只能读/写1个字
字节始终是8位

2.16 浮点数的表示和运算

1.从科学计数法理解浮点数

2.浮点数的表示

• 浮点数的真值: $N=r^E\times M$
• 阶码E: 常用补码或者移码表示的定点整数, 通常阶码的底是2
• 基数r：2、4、16等
• 尾数M: 常用原码或者补码表示的定点小数, 数值部分的位数n反映浮点数的精度
• 尾数给出一个小数, 阶码指明了小数点要向前/向后移动几位
• 尾数的最高位是无效值, 会丧失精度

阶码, 尾数均用补码表示, 求a, b的真值
a=0,01; 1.1001
b=0,10; 0.10001
a: 阶码0,01对应真值+1; 尾数1.1001对应真值-0.0111=-(2^-2+2-3+2^-4)
a的真值=2^1*(-0.0111)=-0.111, 相当于尾数表示的定点小数算数左移一位, 或小数点右移一位
b: 阶码0,10对应的真值位+2; 尾数0.01001对应的真值+0.01001=+(2^-2+2-5)
b的真值=2^2*(+0.01001)=+1.001

3.浮点数尾数的规格化

规格化浮点数: 规定尾数的最高数值位必须是一个有效值

• 左规: 当浮点数运算结果为非规格化时要进行规格化处理
• 右规: 当浮点数运算的结果尾数出现溢出(双符号位为01或者10)时, 将尾数算数右移一位, 阶码加1

a=010;00.1100, b=010;00.1000, 求a+b
a=2^2*00.1100, b=2^2*00.1000
a+b=2^2*00.1100+22*00.1000=2^{2*(00.1100+00.1000)=2}201.0100=2^300.1010(发现溢出)

采用"双符号位", 当溢出发生的时候, 可以挽救. 更高的符号位是正确的符号位

4.规格化浮点数的特点

用原码表示的尾数的规格化

• 正数为0.1XX...X的形式, 其最大值表示为0.11...1; 最小值表示为0.10...0
  • 尾数的表示范围为$0.5≤M≤(1-2^{-n})$
• 负数为1.1XX...X的形式, 其最大值表示为1.10...0, 最小值表示为1.11...1
  • 尾数的表示范围为$-(1-2^{-n})≤M≤-0.5$

用补码表示的尾数进行格式化

• 正数为0.1XX...X的形式, 其最大值表示为0.11...1; 最小值表示为0.10...0
  • 尾数的表示范围为$0.5≤M≤(1-2^{-n})$
• 负数为1.0XX...X的形式, 其最大值表示为1.01...1; 最小值表示为1.00...0
  • 尾数的表示范围为$-1≤M≤-(1/2+2^{-n})$

若某浮点数的阶码, 尾数用补码表示, 共4+8位: 0,110; 1.1110100如何规格化?
应该将数值部分左移3位, 并将阶码从+6变成+3.
补码算数左移, 低位补0; 补码算数右移, 高位补1.

2.17 浮点数标准 IEEE 754

1.移码

• $2^{n-1}$,补码的基础上符号位取反. 注意: 移码只能用于表示整数
• 移码的定义: 移码=真值+偏置值; 偏置值一般取$2^{n-1}$, 此时的移码=补码符号位取反. 偏置值也可以是其他的值, 比如说$2^{n-1}-1$

2.IEEE 754标准

类型	数符	阶码	尾数数值	总位数	十六进制	十进制
短浮点数	1	8	23	32	7FH	127
长浮点数	1	11	52	64	3FFH	1023
临时浮点数	1	15	64	80	3FFFH	16383

• 阶码全1, 全0用作特殊用途, 故单精度浮点型数阶码真值的正常范围是-126~127
• 阶码的真值=移码-偏移量
• 规格化的短浮点数的真值为: $(-1)^s\ *1.M \ *2^{E-127}$
• 规格化的长浮点数的真值为: $(-1)^s \ *1.M\ *2^{E-1023}$

将十进制数-0.75转换为IEEE 754的单精度浮点数格式表示
(-0.75)10=-(0.11)2=(-1.1)2*2^(-1) 最后一步为规格化
数符=1
尾数部分=.1000000...(隐含的最高位1)
阶码真值=-1
单精度浮点型偏移量=127D
移码=阶码真值+偏移量=-1+1111111=01111110(凑足8位)

IEEE 754的单精度浮点数C0 A0 00 00H的值是多少
数符=1 -> 是一个负数
尾数部分=.0100... (隐含最高位1) -> 尾数真值=(1.01)2
移码=10000001, 若看作无符号数=129D
单精度浮点型偏移量=127D
阶码真值=移码-偏移量=10000001-1111111=(00000010)2=(2)10
-> 浮点数真值=(-1.01)2*2^2=-1.25*22=-5.0

IEEE 754单精度浮点型能表示的最小绝对值, 最大绝对值是多少?

• 最小绝对值: 尾数全为0, 阶码真值最小-126, 对应的移码机器数为00000001, 此时整体的真值为(1.0)2*2^(-126)
• 最大绝对值: 尾数权为1, 阶码真值最大127, 对应移码机器数11111110, 此时整体的真值为(1.111...11)2*2^127

格式	格式化的最小绝对值	格式化的最大绝对值
单精度	E=1, M=0: 1.0*2(1-127)=2(-126)	E=-254, M=.11...1: 1.11...12(254-127)=2127(2-2^(-23))
双精度	E=1, M=0: 1.0*2(1-1023)=2(-1022)	E=2046, M=.11...1: 1.11...12(2046-1023)=21023(2-2^(-52))

表示绝对值更小的浮点数

• 阶码全1或者全0用作特殊用途
• 当阶码E不全为0, 尾数M不全为0的时候, 也就是只有1≤E≤254时, 真值=$(-1)^s\ *1.M*2^{E-127}$(隐含的最高位变为1)
• 当阶码E全为0, 尾数M不全为0的时候, 表示非规格化小数$±(0.xx...x)2\ *2^{-126}$(隐含的最高位变为0, 阶码真值固定视为-126)
• 当阶码E全为0, 尾数M全为0的时候, 表示真值±0
• 当阶码E全为1, 尾数M全为0的时候, 表示无穷大±∞(发生上溢或者下溢的时候会出现这种情况
• 当阶码E全为1, 尾数M不全为0的时候, 表示非数值"NaN"(Not a Number, 0/0, ∞-∞等非法运算的结果就是NaN)

2.18 浮点数的运算

1.浮点数的加减运算

$9.85211\ *10^{12}+9.96007\ *10^{10}$

对阶

9.85211*10^{12+0.0996007*10}12

• 小阶向大阶对齐
  • 将阶码小的尾数右移一位，阶加1,直到两个数的阶码相等为止

因为在计算机内部, 尾数是定点小数

尾数相减

9.9517107*10^12

规格化

如果尾数加减出现类似0.定点951710^12时, 需要"左规"; 如果尾数加减出现类似99.51710710^12时, 需要"右规"

舍入

若规定只能保留6位有效尾数, 则9.9517107*10^12 -> 9.95171*10^12 (多余的直接砍掉); 或者, 9.9517107*10^12 -> 9.95172*10^12(若砍掉部分非0, 则入1); 或者, 也可以采用四舍五入的原则, 当舍弃位≥5时, 高位入1

判断溢出

若规定阶码不能超过两位, 则运算后阶码超出范围, 则溢出. 如:9.85211*10^{99+9.96007*10}99=19.81218*10^99, 规格化并用四舍五入的原则保留6位尾数, 得1.98122*10^100. 阶码超过两位, 发生溢出(注: 尾数溢出未必导致整体溢出, 也许可以通过③④两步来拯救)

2.加减运算示例

已知十进制数X=-5/256, Y=59/1024, 按机器补码浮点运算规则计算X-Y, 结果用二进制表示, 浮点数格式如下: 阶符取2位, 阶码取3位, 数符取2位, 尾数取9位
用补码表示阶码和尾数: 5D=101B, 1/256=2^{(-8)->X=-101*2}(-8)=-0.101*2^{(-5)=-0.101*2}(-101); 59D=111011B, 1/1024=2^{(-10)->Y=+111011*2}(-10)=+0.111011*2^{(-4)=+0.111011*2}(-100)
X的阶码双符号位补码: 11011; 尾数双符号位补码并扩展: 11.011000000; Y的阶码和尾数自己算. 最终得到X: 11011,11.011000000; Y: 11100,00.111011000

1. 对阶: 使两个数的阶码相等, 小阶向大阶看齐, 尾数每右移一位, 阶码+1. 求阶差: [∆E]补=11011+00100=11111, 知∆E=-1; 对阶: X: 11011,11.011000000 -> 11100,11.101100000
2. 尾数加减: -Y: 11100,11.000101000; X-Y=: 11100,10.110001000, 由双符号位得出发生溢出, 但是可以通过规格化拯救溢出
3. 规格化: X-Y: 11100, 10.110001000 -> 11101, 11.011000100
4. 舍入: 无舍入
5. 判断溢出: 常阶码, 无溢出, 结果真值为2^(-3)*(-0.1001111)2

3.浮点数的加减运算-舍入

"0"舍"1"入法

类似于十进制数运算中的"四舍五入"法, 即在尾数右移的时候, 被移去的最高位数值为0, 则舍去; 被移去的最高位数值为1, 则在尾数的末位加1. 这样做可能会使尾数又溢出, 此时需要再做一次右规

恒置"1"法

尾数右移的时候, 不论丢掉的最高数值位是"1"还是"0", 都使右移后的尾数末位恒置"1". 这种方法同样有使尾数变大和变小的两种可能

4.强制类型转换

类型	16位机器	32位机器	64位机器
char	8	8	8
short	16	16	16
int	16	32	32
long	32	32	64
long long	64	64	64
float	16	32	32
double	64	64	64

• char -> int -> long -> double: 如果long是32bit的话, 则long转换为double为无损转化. 如果long是64bit的话, 则long转化为double为有损转换, 因为double的有效数值位只有53位
• float -> double: 不会损失精度

32位int和float

• int: 表示整数, 1位符号位+31位数值位, 范围-2^(31)~2(31)-1, 有效数字32位
• float: 表示整数及小数, 范围±[2^(-126)~2(127)*(2-2^(-23))], 1位符号位8个阶码23个尾数, 有效数字23+1=24位

1. int -> float: 可能损失精度
2. float -> int: 可能溢出及损失精度(小数转化为小数的时候)

2.18电路基本原理&加法器设计

1.算数逻辑单元(ALU)

2.最基本的逻辑运算

• $A(C+D)=AC+AD$ --- 分配律
• $ABC=A(BC)$ --- 结合律
• $A+B+C=A+(B+C)$ --- 结合律

"与"

$Y=A·B$

A	B	Y
0	0	0
0	1	0
1	0	0
1	1	1

"或"

$Y=A+B$

A	B	Y
0	0	0
0	1	1
1	0	1
1	1	1

"非"

$Y=\overline{A}$

A	Y
0	1
1	0

3.复合逻辑运算

• $\overline{A+B}=\overline{A}\cdot \overline{B}$
• $\overline{A\cdot B}=\overline{A}+\overline{B}$

"与非"

$Y=\overline{A·B}$

A	B	Y
0	0	1
0	1	1
1	0	1
1	1	0

"或非"

$Y=\overline{A+B}$

A	B	Y
0	0	1
0	1	0
1	0	0
1	1	0

"异或"

$Y=A⊕B=\overline{A}\cdot B+A\cdot \overline{B}$

A	B	Y
0	0	0
0	1	1
1	0	1
1	1	0

"同或"

$Y=A⊙B$

A	B	Y
0	0	1
0	1	0
1	0	0
1	1	1

4.一位全加器(FA, full adder)

输入

$A_i, B_i, C_{i-1}$

输出

• $S_i=A_i⊕B_i⊕C_{i-1}$: 输入有奇数个1时为1(异或)
• $C_i=A_iB_i+(A_i⊕B_i)C_{i-1}$: 输入中至少2个1(两个为都是1或者两个本位中有一个是1, 且来自低位的进位是1)

电路设计

5.串行加法器

• 只有一个全加器, 数据逐位串行送入加法器中进行运算. 进位触发器用来寄存进位信号, 以便参与下一次运算.
• 如果操作数长n位, 加法就要分为n次进行, 每次产生一位和, 并且串行逐位送回寄存器

6.并行加法器

• 该种并行加法器称为串行进位的并行加法器
• 把n个全加器串接起来, 就可进行两个n位数的相加
• 串行进位又称为行波进位, 每一级进位直接依赖于前一级的进位, 即进位信号是逐级形成的

2.19加法器&ALU的改进

1.如何更快地产生进位?

$C_i=A_iB_i+(A_i⊕B_i)C_{i-1}$
$C_i=A_iB_i+(A_i⊕B_i)(A_{i-1}B_{i-1}+(A_{i-1}⊕B_{i-1}C_{i-2}))$
$C_i=A_iB_i+(A_i⊕B_i)(A_{i-1}B_{i-1}+(A_{i-1}⊕B_{i-1}(A_{i-2}B_{i-2}+(A_{i-2}⊕B_{i-2})C_{i-3}))$
... 终有一天可以展开到$C_0$

第i位向更高位的进位可根据被加数, 加数的第1~i位, 再结合C0确定

2.并行加法器的优化

记$G_i=A_iB_i, P_i=A_i⊕B_i$, 可以将上述的式子化简, 得到:
$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_4=G_4+P_4C_3=G_4+P_4G_3+P_4P_3G_2+P_4P_3P_2G_1+P_4P_3P_2P_1C_0$
...

并行进位的并行加法器: 各级进位信号同时形成, 又称为先行进位, 同时进位. 但是, 继续套娃会导致电路越来越复杂, 故一般只支持四位进位并行处理, 也就是4位CLA加法器

由4个FA和一些新的线路, 运算逻辑组成

单级先行进位方式(组内并行, 组间串行)

组内进位信号:
$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_4=G_4+P_4C_3=G_4+P_4G_3+P_4P_3G_2+P_4P_3P_2G_1+P_4P_3P_2P_1C_0$

记: $G_1^*=G_4+P_4G_3+P_4P_3G_2+P_4P_3P_2G_1; P_1^*=P_4P_3P_2P_1$

$G_1^*$称为组进位产生函数, $P_i^*$称为组进位传递函数. 根据本组的4*2个输入位即可确定本组的$G_1^*$和$P_i^*$

组间传递信号:
$C_4=G_1^*+P_1^*C_0$
$C_8=G_2^*+P_2^*C_4=G_2^*+P_2^*G_1^*+P_2^*P_1^*C_0$
$C_{12}=G_3^*+P_3^*C_8=G_3^*+P_3^*G_2^*+P_3^*P_2^*G_1^*+P_3^*P_2^*P_1^*C_0$
$C_{16}=G_4^*+P_4^*C_{12}=G_4^*+P_4^*G_3^*+P_4^*P_3^*G_2^*+P_4^*P_3^*P_2^*G_1^*+P_4^*P_3^*P_2^*P_1^*C_0$

多级先行进位方式(组内并行, 组间并行)

3.ALU芯片的优化