目录
第二章 运算方法和运算器
2.1 数制与编码
一、进位计数制及其相互转换
10进制和R进制之间的转换
R进制到10进制：
∑
i
=
n
−
m
k
i
×
r
i
\sum_{i = n}^{-m} k_i × r^i
i=n∑−mki×ri
eg:二进制数转换十进制数
//二转十
int bToD(char str[]) {
int sum = 0;
for(int i = 0; str[i] != '\0'; i++) {
sum = sum*2 + (str[i] - '0');
}
return sum;
}
10进制到R进制：
- 整数部分：除r取余，r为进制基数
- 小数部分：乘r取整代码如下
//将十进制数n转化为k进制整数
void dToK(int n, int k, char str[]) {
int i = 0;
if (n == 0) {
str[0] = '0';
return;
}
while(n) {
str[i++] =n % k + '0';
n = (n-n % k) / k;
}
i--;
//reverse
for (int j = 0; j < i; j++,i--) {
char t = str[j];
str[j] = str[i];
str[i] = t;
}
}
二、真值和机器数
- 真值：一般书写的数
- 机器码：机器中表示的数，要解决在计算机内部数的正、负符号和小数点运算问题。
三、BCD码
表示一位十进制数的二进制码的每一位有确定的权。一般用8421码，其4个二进制码的权从高到低分别为8、4、2和1。用0000，0001，…，1001分别表示0，1，…，9，每个数位内部满足二进制规则，而数位之间满足十进制规则，故称这种编码为“以二进制编码的十进制(binary coded decimal，简称BCD)码”。
注意！
BCD码的取值是从0000到1001（也就是十进制的0到9）
有时对BCD码进行加法或减法会有这个范围以外的值出现，需要人为调整方能得出正确的结果。
在计算机内部实现BCD码算术运算，要对运算结果进行修正，对加法运算的修正规则是:
- 如果两个一位BCD码相加之和小于或等于(1001)2，即(9)10，不需要修正;
例1 ① 1+8 = 9
0 0 0 1
+ 1 0 0 0
——————————
1 0 0 1
不需要修正
- 如相加之和大于或等于(10)10，要进行加6修正，并向高位进位，进位可以在首次相加(例1 ③)或修正时(例1 ②)产生。
例1 ② 4+9 = 13
0 1 0 0
+ 1 0 0 1
——————————
1 1 0 1
+ 0 1 1 0 修正
——————————
1 0 0 1 1
0001 0011即为13~
③ 9+7 = 16
1 0 0 1
+ 0 1 1 1
——————————
1 0 0 0 0
+ 0 1 1 0 修正
——————————
1 0 1 1 0
0001 0110即为16~
四、字符与字符串
1、字符与字符串的表示方法
符号数据:字符信息用数据表示，如ASCII等
字符表示方法ASCII:用一个字节来表示,低7位用来编码(128),最高位为校验位，如图
字符串的存放方法:占用主存中连续的多个字节，每个字节存一个字符。
2、汉字的表示方法
一级汉字3755个，二级汉字3008个
汉字内码:汉字信息的存储,交换和检索的机内代码，两个字节组成，每个字节高位都为1(区别于英文字符)
汉字字模码:汉字字形点阵
五、校验码（重点）
推荐视频3Blue1Brown的汉明码part1、3Blue1Brown的汉明码part2，讲的非常有趣！虽然主要讲汉明码，但对奇偶校验码也有详细描述。
校验码（只介绍奇偶校验码)
引入
信息传输和处理过程中受到干扰和故障，容易出错。
解决方法
在有效信息中加入一些冗余信息（校验位)
定义
设x=(x0 x1.xn-1)是一个n位字，则偶校验位C定义为:C=x0 ^ x1 ^ x2 ^ … x~n-1~,式中代表按位加，表明只有当x中包含有偶数个1时,才使C=0，否则C=1。只能检查出错，而不能纠正错误。同理可以定义奇校验。
奇校验：包含奇数个1时才使得C=0,否则C=1
2.2 定点数的表示和运算（重点）
一、定点数的表示
1、原码表示法
定点小数 xn.xn-1xn-2……x0，x为真值
[
x
]
原
=
{
x
,
0 ≤ x < 1 即 x为正数
1
−
x
,
-1 < x ≤ 0 即 x为负数
[x]_原 = \begin{cases} x, & \text{0 ≤ x < 1 即 x为正数} \\ 1-x, & \text{-1 < x ≤ 0 即 x为负数} \end{cases}
[x]原={x,1−x,0 ≤ x < 1 即 x为正数-1 < x ≤ 0 即 x为负数
范围为2-n-1~1-2-n
eg：
x = +0.1001，[x]原 = 0.1001
x = -0.1001，[x]原 = 1-(-0.1001)=1.1001
定点整数 xnxn-1xn-2……x0，x为真值
[
x
]
原
=
{
x
,
0 ≤ x <
2
n
即
x
为
正
数
2
n
−
x
,
-2
n
<
x
≤
0
即
x
为
负
数
[x]_原 = \begin{cases} x, & \text{0 ≤ x < }2^n 即 x为正数\\ 2^n-x, & \text{-2}^n<x≤ 0 {即x为负数} \end{cases}
[x]原={x,2n−x,0 ≤ x < 2n即x为正数-2n<x≤0即x为负数
范围为1-2n~2n-1
eg：
x = +1001，[x]原 = 01001
x = -1001，[x]原 = 24+1001=11001
有正0和负0之分！！
2、反码表示法
定义
- 正数的表示与原码、补码相同。
- 负数的反码符号位为1，数值位是将原码的数值按位取反，就得到该数的反码表示。
- 电路容易实现，触发器的输出有正负之分。
对尾数求反，反码跟补码的区别在于末位少加一个1，所以可以推出反码的定义
定点小数 xn.xn-1xn-2……x0，x为真值
[
x
]
反
=
{
x
,
0 ≤ x < 1 即 x为正数
(
2
−
2
−
n
)
+
x
,
-1 < x ≤ 0 即 x为负数
[x]_反 = \begin{cases} x, & \text{0 ≤ x < 1 即 x为正数} \\ (2-2^{-n})+x, & \text{-1 < x ≤ 0 即 x为负数} \end{cases}
[x]反={x,(2−2−n)+x,0 ≤ x < 1 即 x为正数-1 < x ≤ 0 即 x为负数
eg:
X1=+0.1011011 , [X1]反 =0.1011011
X2= -0.1011011 , [X2]反 =1.0100100
定点整数 xnxn-1xn-2……x0，x为真值
[
x
]
反
=
{
x
,
0 ≤ x <
2
n
即
x
为
正
数
(
2
n
+
1
−
1
)
+
x
,
-2
n
<
x
≤
0
即
x
为
负
数
[x]_反 = \begin{cases} x, & \text{0 ≤ x < }2^n 即 x为正数 \\ (2^{n+1}-1)+x, & \text{-2}^n<x≤ 0 {即x为负数} \end{cases}
[x]反={x,(2n+1−1)+x,0 ≤ x < 2n即x为正数-2n<x≤0即x为负数
反码表示有正0和负0之分！！
3、补码表示法
定义
正数的补码就是正数的本身，负数的补码是原负数加上模（原负数除符号位外取反，再加1）。 计算机运算受字长限制,属于有模运算。补码最大的优点就是将减法运算转换成加法运算。
定点小数xnxn-1xn-2……x0，以2为模
[
x
]
补
=
{
x
,
0 ≤ x < 1 即 x为正数
2
+
x
,
-1 < x ≤ 0 即 x为负数
[x]_补 = \begin{cases} x, & \text{0 ≤ x < 1 即 x为正数} \\ 2+x, & \text{-1 < x ≤ 0 即 x为负数} \end{cases}
[x]补={x,2+x,0 ≤ x < 1 即 x为正数-1 < x ≤ 0 即 x为负数
eg: x= -0.1011，[x]补=10+x=10.0000-0.1011=1.0101
y=-0.01111 [y]补=10+y=10.00000-0.01111=1.10001
定点整数xnxn-1xn-2……x0 ，以2n+1为模
[
x
]
补
=
{
x
,
2
n
＞
x
≥
0
即
x
为
正
数
2
n
+
1
+
x
,
0 ≥ x > -2
n
即
x
为
负
数
[x]_补 = \begin{cases} x, & \text{2}^n {＞x ≥ 0 即 x为正数} \\ 2^{n+1}+x, & \text{0 ≥ x > -2}^n {即x为负数} \end{cases}
[x]补={x,2n+1+x,2n＞x≥0即x为正数0 ≥ x > -2n即x为负数
补码性质:
- 高位表明正负
- 正数补码，尾数与原码相同
- 范围-2n~2n-1(定点整数）
- 无正零和负零之分！！
4、移码表示法
用在阶码中，特点是移码和补码尾数相同，符号位相反
范围:-2n~2n-1
eg：真值-1011111
原码为11011111
补码为10100001
反码为10100000
移码为00100001
5、总结
- 若x为正数，[x]原 = [x]补 = [x]反
- 若x为负数，原码符号位为1不变，整数的每一位二进制数位求反得到反码，反码符号位不变，反码数值位最低位加1，得到补码。
- 移码和补码尾数相同，符号位相反
二、定点数的运算（重点）
1、定点数的移位运算
计算机中的移位是数据相对于小数点移位（左移或右移），数据移动，小数点位置不发生变化
有符号数的移位
左移1位：机器数对应真值的绝对值变为原来2倍
右移1位：机器数对应真值的绝对值变为原来1/2倍
移位过程中，填补空位:
- 负数数值部分和真值相同
无符号数的移位
- 逻辑左移 低位添0，高位移丢
- 逻辑右移 高位添0，低位移丢
eg：
01010011
逻辑左移 所有位都参加移位操作 高位0移丢，最低位添0 ：10100110
算术左移 第一个0表示符号位，这个数为正数，符号位不参与移位，移位的是后面的数据00100110
eg：
10110010
逻辑右移 所有位都参加移位操作 空出的最高位补0，最低位丢弃01011001
算术右移 最高位不参与移位，符号位，表示负数，右移左侧空出最高位添1，右侧0丢弃11011001
2、补码加减法
补码加法
公式：
[
x
+
y
]
补
=
[
x
]
补
+
[
y
]
补
(
m
o
d
2
n
+
1
)
∣
x
∣
<
(
2
n
−
1
)
,
∣
y
∣
<
(
2
n
−
1
)
,
∣
x
+
y
∣
<
(
2
n
−
1
)
[x+y]_补=[x]_补+[y]_补 (mod 2^{n+1}) \\ |x|<(2n-1) , |y|<(2n-1) , |x+y|<(2n-1)
[x+y]补=[x]补+[y]补(mod2n+1)∣x∣<(2n−1),∣y∣<(2n−1),∣x+y∣<(2n−1) 公式表明：在2n+1模意义下，任意两数的补码之和等于该两数之和的补码。
证明：
（1）x > 0，y > 0，则x+y > 0，因正数的原码补码都一样，所以[x]补+[y]补 = x+y = [x+y]补
（2）x > 0，y < 0，则x+y > 0或x+y < 0
[x]补= x，[y]补 = 2n+1+y
[x]补+[y]补 = (x+y)+2n+1 = [x+y]补 (mod 2n+1)
（3）x < 0，y > 0，则x+y > 0或x+y < 0
[x]补= 2n+1+x，[y]补 = y
[x]补+[y]补 = (x+y)+2n+1 = [x+y]补 (mod 2n+1)
（4）x < 0，y < 0，则x+y < 0
[x]补= 2n+1+x，[y]补 = 2n+1+y
[x]补+[y]补 = 2n+1+x + 2n+1+y
= 2n+1+( 2n+1+x+y)
= [x+y]补 (mod 2n+1)
eg: x=+1011 , y=-0101 , 求 x+y=？
解：[x]补 = 01011, [y]补 = 11011
[x]补 0 1 0 1 1
＋ [y]补 1 1 0 1 1
————————————————
[x+y]补 1 0 0 1 1 0
∴ x+y = +0110
1、符号位作为数的一部分参加运算。
2、在2n+1模意义下相加，即超过2n+1的进位要丢掉
补码减法
为了将减法转变为加法，需证明公式：
[
x
−
y
]
补
=
[
x
]
补
−
[
y
]
补
=
[
x
]
补
+
[
−
y
]
补
(
m
o
d
2
n
+
1
)
[x-y]_补=[x]_补-[y]_补 = [x]_补+[-y]_补 (mod 2^{n+1})
[x−y]补=[x]补−[y]补=[x]补+[−y]补(mod2n+1)
[x-y]补= [x ]补- [ y]补=[x]补+[-y]补
（证明） 为了求得同时[-y]补， 需要证明[-y]补=乛[y]补+2-n（意义是[-y]补等于[y]补包括符号位取反，末位加1）
∵ [x]补+[y]补 = [x+y]补
∴ [y]补 = [x+y]补 - [x]补
又∵ [x-y]补 = [x+(-y)]补 = [x]补+[-y]补
∴ [-y]补 = [x-y]补 - [x]补
故[y]补 + [-y]补
= [x+y]补 - [x]补 + [x-y]补 - [x]补
= [x+y+x-y]补-[x+x]补
= [x+x]补 - [x+x]补
= 0
故[-y]补 = -[y]补(mod 2n+1)
由[X]补求[-X]补:连符号位一起各位求反，末位加1
3、定点数的乘除运算
乘法运算
除法运算
恢复余数法：将被除数－除数，
结果大于0，商1，余数左移一位。
结果小于0，商0，恢复余数，余数左移一位。
重复上述操作，直至商的精度满足要求为止。
不恢复余数法（ 加减交替法）
- 第一次： 若被除数与除数同号，做被除数减除；若被除数与除数异号，做被除数加除数
- 若余数与除数同号，商1，余数左移一位，减除数；若余数与除数异号，商0，余数左移一位，加除数
- 商的末位恒置1（误差 2-n），余数可以是负的，不需要恢复余数。
eg:p44
4、溢出概念和判别方法
溢出的概念
在定点整数机器中，数的表示范围 |x| < (2n-1) ，在运算过程中如果出现大于字长绝对值的现象，称为“溢出”。
[例15] x=+1011 , y=+1001 , 求 x+y 。
解：[x]补=01011 , [y]补=01001
[x]补 0 1 0 1 1
＋ [x]补 0 1 0 0 1
——————————————
[x+y]补 1 0 1 0 0
两个正数相加的结果成为负数，称为上溢（结果大于机器所能表示的最大正数
[例16] x=-1101 , y=-1011 , 求 x+y 。
解：[x]补=10011 , [y]补=10101
[x]补 1 0 0 1 1
＋ [x]补 1 0 1 0 1
——————————————
[x+y]补 0 1 0 0 0
两个负数相加的结果成为正数，称为下溢（结果小于机器所能表示的最小负数）
溢出的检测
双符号位法（变形补码）
参与加减运算的数采用变形补码表示
[x]补=2n+2+x (mod 2n+2)
[x+y]补=[x]补+[y]补 (mod 2n+2)
- 两个符号位都参与运算
- 在2n+2模意义下相加，即最高符号位产生的进位要丢掉
Sf1 SF2
0 0 正确（正数）
0 1 上溢
1 0 下溢
1 1 正确（负数）
两符号位相异时，表示溢出；相同时，没有溢出。 无论是否溢出，Sf1(即最高位) 表示结果正确的符号
2.3 浮点数的表示和运算
一、浮点数的表示
浮点数的表示范围
二、IEEE754标准。
三、浮点数的加减运算
- 0操作数的检查,看有无简化操作的可能；
- 比较阶码大小并完成对阶（小阶向大阶对齐）；
- 尾数进行加或减运算；
- 结果规格化并进行舍入处理。
对阶
实现使两数阶码相同的过程
对阶原则：阶码小的数向阶码大的数对齐
对阶过程：首先应求出两数阶码Ex和Ey之差，看是否相等。若不等，要通过尾数的移动以改变Ex和Ey，即对阶，使之相等。即小阶的尾数向右移动（相当于小数点左移），每右移一位，其阶码加1，直到两数的阶码相等为止，右移的位数等于阶差。
尾数求和
方法和定点加减运算完全一样
规格化
浮点数的规格化要求尾数域的最高有效位应为1，将运算结果右移以实现规格化称为右规，将运算结果左移以实现规格化称为左规
规格化数的判断方法（单符号法）
- 原码：不论正数还是负数，第一数位为1
- 反码、补码：符号位和第一数位不同
舍入处理
舍入处理的目的：在对阶或向右规格化时，尾数要向右移位，被右移的低位部分会被丢掉，造成一定误差。为了减小误差。
IEEE754标准的舍入处理
- 就近舍入(0舍1入):类似”四舍五入”,丢弃的最高位为1，进1
- 朝0舍入:简单的截尾
- 朝＋∞舍入:正数多余位不全为”0”,进1;负数,截尾
- 朝－∞ 舍入:负数多余位不全为”0”,进1;正数,截尾
2.4 算术逻辑单元ALU
一、串行加法器和并行加法器
一位全加器的逻辑表达式如下：
Fi = Ai ⊕ Bi ⊕ Cn+i
Cn+i+1 = AiBi + AiCn+i + BiCn+i
C为进位
串行加法器
- 只有一个全加器，数据逐位串行送入加法器中进行运算。进位触发器用来寄存进位信号，以便参与下一次运算。
- 如果操作数长n位，加法就要分n次进行，每次产生一位和，并且串行逐位地送回寄存器。
并行加法器
- 并行加法器由多个全加器组成，其位数与机器的字长相同，各位数据同时运算。
- 并行加法器的最长运算时间主要是由进位信号的传递时间决定的
- 并行加法器的每个全加器都有一个从低位送来的进位输入和一个传送给高位的进位输出
- 并行加法器的进位通常分为串行进位与并行进位。
二、算术逻辑单元ALU的功能和结构
ALU的逻辑图如上
Fi = Xi ⊕ Yi ⊕ Cn+1
Cn+i+1 = XiYi + YiCn+1 + XiCn+1
不同的控制参数可以得到不同的组合函数，从而能够实现多种算术运算和逻辑运算。
Xi和Yi 与控制参数和输入量的关系构造如下真值表