# 第二章 运算方法和运算器

# 2.1 数制与编码

# 一、进位计数制及其相互转换

10 进制和 R 进制之间的转换
R 进制到 10 进制：

$$\sum_{i = n}^{-m} k_i × r^i$$

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)₂，即 (9)₁₀，不需要修正；

例1 ① 1+8 = 9
  0 0 0 1
+ 1 0 0 0 
——————————
  1 0 0 1 
不需要修正

• 如相加之和大于或等于 (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=(x₀ x₁.x_n-1) 是一个 n 位字，则偶校验位 C 定义为：C=x₀ ^ x₁ ^ x₂ ^ ... ^{x~n-1~, 式中}代表按位加，表明只有当 x 中包含有偶数个 1 时，才使 C=0，否则 C=1。只能检查出错，而不能纠正错误。同理可以定义奇校验。
奇校验：包含奇数个 1 时才使得 C=0, 否则 C=1

# 2.2 定点数的表示和运算（重点）

# 一、定点数的表示

# 1、原码表示法

定点小数 x_n.x_n-1x_n-2…..x₀，x 为真值

$$[x]_原 = \begin{cases} x, & \text{0 ≤ x < 1 即 x为正数} \\ 1-x, & \text{-1 < x ≤ 0 即 x为负数} \end{cases}$$

范围为 2^-n-1~1-2^-n
eg：
x = +0.1001，[x] 原 = 0.1001
x = -0.1001，[x] 原 = 1-(-0.1001)=1.1001

定点整数 x_nx_n-1x_n-2…..x₀，x 为真值

$$[x]_原 = \begin{cases} x, & \text{0 ≤ x < }2^n 即 x为正数\\ 2^n-x, & \text{-2}^n<x≤ 0 {即x为负数} \end{cases}$$

范围为 1-2ⁿ~2ⁿ-1
eg：
x = +1001，[x] 原 = 01001
x = -1001，[x] 原 = 2⁴+1001=11001
有正 0 和负 0 之分！！

# 2、反码表示法

定义

• 正数的表示与原码、补码相同。
• 负数的反码符号位为 1，数值位是将原码的数值按位取反，就得到该数的反码表示。
• 电路容易实现，触发器的输出有正负之分。
  对尾数求反，反码跟补码的区别在于末位少加一个 1，所以可以推出反码的定义

定点小数 x_n.x_n-1x_n-2…..x₀，x 为真值

$$[x]_反 = \begin{cases} x, & \text{0 ≤ x < 1 即 x为正数} \\ (2-2^{-n})+x, & \text{-1 < x ≤ 0 即 x为负数} \end{cases}$$

eg:
X1=+0.1011011 , [X1] _反 =0.1011011
X2= -0.1011011 , [X2] _反 =1.0100100
定点整数 x_nx_n-1x_n-2…..x₀，x 为真值

$$[x]_反 = \begin{cases} x, & \text{0 ≤ x < }2^n 即 x为正数 \\ (2^{n+1}-1)+x, & \text{-2}^n<x≤ 0 {即x为负数} \end{cases}$$

反码表示有正 0 和负 0 之分！！

# 3、补码表示法

定义
正数的补码就是正数的本身，负数的补码是原负数加上模（原负数除符号位外取反，再加 1）。 计算机运算受字长限制，属于有模运算。补码最大的优点就是将减法运算转换成加法运算。
定点小数 x_nx_n-1x_n-2…..x₀，以 2 为模

$$[x]_补 = \begin{cases} x, & \text{0 ≤ x < 1 即 x为正数} \\ 2+x, & \text{-1 < x ≤ 0 即 x为负数} \end{cases}$$

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 ，以 2ⁿ⁺¹ 为模

$$[x]_补 = \begin{cases} x, & \text{2}^n {＞x ≥ 0 即 x为正数} \\ 2^{n+1}+x, & \text{0 ≥ x > -2}^n {即x为负数} \end{cases}$$

补码性质:

• 高位表明正负
• 正数补码，尾数与原码相同
• 范围 - 2ⁿ~2ⁿ-1 (定点整数）
• 无正零和负零之分！！

# 4、移码表示法

用在阶码中，特点是移码和补码尾数相同，符号位相反
范围:-2ⁿ~2ⁿ-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]_补 (mod 2^{n+1}) \
|x|<(2n-1) , |y|<(2n-1) , |x+y|<(2n-1) $$ 公式表明：在 2ⁿ⁺¹ 模意义下，任意两数的补码之和等于该两数之和的补码。
证明：
（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] _补 = 2ⁿ⁺¹+y
[x] _补 +[y] _补 = (x+y)+2ⁿ⁺¹ = [x+y] _补 (mod 2ⁿ⁺¹)

（3）x <0，y> 0，则 x+y > 0 或 x+y < 0
[x] _补 = 2ⁿ⁺¹+x，[y] _补 = y
[x] _补 +[y] _补 = (x+y)+2ⁿ⁺¹ = [x+y] _补 (mod 2ⁿ⁺¹)

（4）x < 0，y < 0，则 x+y < 0
[x] _补 = 2ⁿ⁺¹+x，[y] _补 = 2ⁿ⁺¹+y
[x] _补 +[y] _补 = 2ⁿ⁺¹+x + 2ⁿ⁺¹+y
= 2ⁿ⁺¹+( 2ⁿ⁺¹+x+y)
= [x+y] _补 (mod 2ⁿ⁺¹)

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]_补 (mod 2^{n+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 2ⁿ⁺¹)

由 [X] _补求 [-X] _补：连符号位一起各位求反，末位加 1

# 3、定点数的乘除运算

# 乘法运算

# 除法运算

恢复余数法：将被除数－除数，
结果大于 0，商 1，余数左移一位。
结果小于 0，商 0，恢复余数，余数左移一位。
重复上述操作，直至商的精度满足要求为止。

不恢复余数法（ 加减交替法）

• 第一次： 若被除数与除数同号，做被除数减除；若被除数与除数异号，做被除数加除数
• 若余数与除数同号，商 1，余数左移一位，减除数；若余数与除数异号，商 0，余数左移一位，加除数
• 商的末位恒置 1（误差 2-n），余数可以是负的，不需要恢复余数。
  
  eg:p44
  

# 4、溢出概念和判别方法

# 溢出的概念

在定点整数机器中，数的表示范围 |x| < (2ⁿ-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] _补 = 2ⁿ⁺²+x (mod 2ⁿ⁺²)
[x+y] _补 =[x] _补 +[y] _补 (mod 2ⁿ⁺²)

• 两个符号位都参与运算
• 在 2ⁿ⁺² 模意义下相加，即最高符号位产生的进位要丢掉
  Sf1　SF2
  0　　 0　　　正确（正数）
  0 　1　　　上溢
  1 　　0　　　下溢
  1　　 1　　　正确（负数）
  两符号位相异时，表示溢出；相同时，没有溢出。 无论是否溢出，Sf1 (即最高位) 表示结果正确的符号

# 练习题

# 2.3 浮点数的表示和运算

# 一、浮点数的表示

浮点数的表示范围

# 二、IEEE754 标准。

# 三、浮点数的加减运算

1. 0 操作数的检查，看有无简化操作的可能；
2. 比较阶码大小并完成对阶（小阶向大阶对齐）；
3. 尾数进行加或减运算；
4. 结果规格化并进行舍入处理。

# 对阶

实现使两数阶码相同的过程
对阶原则：阶码小的数向阶码大的数对齐
对阶过程：首先应求出两数阶码 E_x 和 E_y 之差，看是否相等。若不等，要通过尾数的移动以改变 E_x 和 E_y，即对阶，使之相等。即小阶的尾数向右移动（相当于小数点左移），每右移一位，其阶码加 1，直到两数的阶码相等为止，右移的位数等于阶差。

# 尾数求和

方法和定点加减运算完全一样

# 规格化

浮点数的规格化要求尾数域的最高有效位应为 1，将运算结果右移以实现规格化称为右规，将运算结果左移以实现规格化称为左规

规格化数的判断方法（单符号法）

• 原码：不论正数还是负数，第一数位为 1
• 反码、补码：符号位和第一数位不同

# 舍入处理

舍入处理的目的：在对阶或向右规格化时，尾数要向右移位，被右移的低位部分会被丢掉，造成一定误差。为了减小误差。
IEEE754 标准的舍入处理

• 就近舍入 (0 舍 1 入): 类似” 四舍五入”, 丢弃的最高位为 1，进 1
• 朝 0 舍入：简单的截尾
• 朝＋∞舍入：正数多余位不全为”0”, 进 1; 负数，截尾
• 朝－∞ 舍入：负数多余位不全为”0”, 进 1; 正数，截尾
  
  
  

# 2.4 算术逻辑单元 ALU

# 一、串行加法器和并行加法器

一位全加器的逻辑表达式如下：
F_i = A_i ⊕ B_i ⊕ C_n+i
C_n+i+1 = A_iB_i + A_iC_n+i + B_iC_n+i
C 为进位
串行加法器

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

并行加法器

• 并行加法器由多个全加器组成，其位数与机器的字长相同，各位数据同时运算。
• 并行加法器的最长运算时间主要是由进位信号的传递时间决定的
• 并行加法器的每个全加器都有一个从低位送来的进位输入和一个传送给高位的进位输出
• 并行加法器的进位通常分为串行进位与并行进位。

# 二、算术逻辑单元 ALU 的功能和结构

ALU 的逻辑图如上
F_i = X_i ⊕ Y_i ⊕ C_n+1
C_n+i+1 = X_iY_i + Y_iC_n+1 + X_iC_n+1
不同的控制参数可以得到不同的组合函数，从而能够实现多种算术运算和逻辑运算。

Xi 和 Yi 与控制参数和输入量的关系构造如下真值表