计算机组成原理·2 数据的表示和运算

考纲内容

• 数制与编码：进位计数制及其转换、定点数编码表示
• 定点数的表示和运算：加减乘除运算、溢出判别
• 浮点数的表示和运算：IEEE 754 标准、加减运算
• 算术逻辑单元 ALU：串行/并行加法器、进位方式

一、数制与编码

1. 进位计数制及其相互转换

计算机内部使用二进制的原因如下：

1. 使用有两个稳定状态的物理器件就可以二进制两种状态，制造成本比较低
2. 二进制位 1 和 0 正好与逻辑值“真”和“假”对应，为实现逻辑运算和程序中的逻辑判断提供了便利条件
3. 二进制的编码和运算规则都很简单，通过逻辑门电路能方便地实现算术运算

进位计数法

十进制数是日常生活中最常使用的，而计算机中通常使用二进制数、八进制数和十六进制数

在进位计数法中，每个数位所用到的不同数码的个数称为基数，如十进制的基数为 10（0~9）

一个 r 进制数（$K_n\cdots K_0{K}_{-1}\cdots K_{-m}$）的数值可表示为 ${\displaystyle \sum _{i=n}^{-m}{K}_i{r}^i}$ 其中 r 是基数；$r^i$ 是第 i 位的位权，整数位的最低位规定为第 0 位；$K_i$ 的取值范围是 $0\sim r-1$ 共 r 个数码中的任意一个

1. 二进制：计算机中用得最多的是基数为 2 的计数制，二进制只有 0 和 1 两种数字符号，计数逢二进一
2. 八进制：基数为 8，有 0~7 共 8 个不同的数字符号，计数逢八进一
3. 十六进制：基数为16，逢十六进个数位可取 0～9、A、B、C、D、E、F 中的任意一个，其中 A～F 分别表示10～15

不同进制数之间的相互转换

二进制转八和十六进制

转八进制：小数点分开， 3 个二进制一组，不够加零，转完后再和起来

转十六进制差不多，4 个一组

任意进制转十进制

将任意进制数的各位数码与它们的权值相乘，再把乘积相加，就得到了一个十进制数

如，$(11011.1{)}_2=1\times 2^4+1\times 2^3+0\times 2^2+1\times 2^1+1\times 2^0+1\times 2^{-1}=27.5$

十进制转任意进制

这里需要对整数部分和小数部分分开转换，使用除基取余法转换整数部分，使用乘基取整法转换小数部分

使用 123.6875 作为例子转换为 2 进制

除基取余法：123 = 0b1111011

乘基取整法：0.6875= 0b0.1011

因此 123.6875 = 0b1111011.1011

注意：在计算机中，小数和整数不一样，整数可以连续表示，但小数是离散的，所以并不是每个十进制小数都可以准确地用二进制表示

注意：关于十进制数转换为任意进制数为何采用除基取余法和乘基取整法，以及所取之数放置位置的原理，请结合 r 进制数的数值表示公式思考，而不应死记硬背

2. 真值和机械数

这种带“+”或“-”符号的数称为真值，真值是机器数所代表的实际值

通常采用数的符号和数值一起编码的方法来表示数据，通常用 0 表示正，用 1 表示负

如 0101 是 +5，这种把符号“数字化”的数称为机器数

3. *BCD 码

二进制编码的十进制数（Binary-Coded Decimal,BCD）通常采用 4 位二进制数来表示一位十进制数中的0～9这10 个数码

1. 8421 码（最常用）：是一种有权码，它表示的十进制数是 $D=8b_3+4b_2+2b_1+1b_0$

   如 9 $\to$ 1001，再相加时大于 9 需要再加 6 来进行修正，并向高位进位，然后查看高位是否要修正

   

2. 余 3 码：是一种无权码，是在 8421 码的基础上加 3 形成的

3. 2421 码：是一种有权码，它表示的十进制是 $D=2b_3+4b_2+2b_1+1b_0$，特点是大于等于 5 的 4 位二进制中最高位为 1，小于 5 的最高位为 0，如 5 $\to$ 1011

4. 字符与字符串

字符编码 ASCII 码

ASCII 码是 7 位二进制编码，每个字节的最高位为 0，包含 10 个数字 52 个英文字母，和一些符号共 128 个字符

在ASCII码中，编码值 0～31 为控制字符，用于通信控制或设备的功能控制；编码值 127 是 DEL 码；编码值 32 是空格SP；编码值32～126共95个字符称为可印刷字符

注意：0x30 是 0，0x20 是空格，0x41 是 A，0x61 是 a

汉字的表示和编码

汉字的编码包括汉字的输入编码、汉字内码、汉字字形码三种，它们是计算机中用于输入、内部处理和输出三种用途的编码

区位码用两字节表示一个汉字，每字节用七位码，区位码是 4 位十进制数，前 2 位是区码，后 2 位是位码，所以称为区位码

国标码将十进制的区位码转换为十六进制数后，再在每字节上加上 20H，国标码和区位码都是输入码

汉字和图形符号排列在一个 94 行 94 列的二维代码表中（汉字字形码）

为了方便计算机区分中文字符和英文字符，将国标码两字节的最高位都改为 1，这就是汉字内码

5. *校验码

由若干位代码组成的一个字叫码字，将两个码字逐位进行对比，具有不同的位的个数称为两个码字间的距离

一种编码方案可能有若干个合法码字，各合法码字间的最小距离称为码距

码距不小于 2 的数据校验码，开始具有检错的能力；码距大于等于 3 时可能有纠错能力

校验码是指能够发现或能够自动纠正错误的数据编码，也称检错纠错编码

校验码的原理是通过增加一些冗余码，通过增加码距的方法来检验或纠错编码

奇偶校验码

在原编码上加一个校验位，它的码距等于 2，可以检测出奇数位错误，但不能确定出错的位置，也不能够检测出偶数位错误，增加的冗余位称为奇偶校验位

奇偶校验实现的方法：由若干位有效信息再加上一个二进制位（校验位）组成校验码，校验位的取值（0 或 1）将使整个校验码中 1 的个数为奇数或偶数，所以有两种可供选择的校验规律：

1. 奇校验码：整个校验码（有效信息位和校验位）中 1 的个数为奇数
2. 偶校验码：整个校验码（有效信息位和校验位）中 1 的个数为偶数

如 10101 他有奇数个 1 也就足够了，所以奇校验码为 0；但要令 1 的个数为偶数个还差一点，所以偶校验码为 1

海明校验码

海明码（Hamming Code，也译为汉明码）是广泛采用的一种有效的校验码

实现原理是在有效信息位中加入几个校验位形成海明码，并把海明码的每个二进制位分配到几个奇偶校验组中

当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错位，还能指出错位的位置

根据纠错理论得 L - 1 = D + C 且 $D\ge C$ 即编码最小码距 L 越大，其检测错误的位数 D 越大，纠正错误的位数 C 也越大

下面用一个例子来介绍求海明码的步骤，求 1010：

1. 确定海明码的位数：

   设 n 为有效信息的位数，k 为校验位的位数，则有关系 n + k ≤ $2^k$ - 1，若要检测两位错，则需再增加 1 位校验位

   海明码位数为 $n+k=7<2^3-1$ 成立，则信息位为 $D_4{D}_3{D}_2{D}_1$（1010）；校验位为 $P_3{P}_2{P}_1$，海明码为 $H_7\sim H_1$

2. 确定校验码的分布：校验码 $P_i$ 在海明位号为 $2^{i-1}$ 位置上，$P_1{P}_2{P}_3$ 的位号为 $H_1{H}_2{H}_4$ 其余的是信息位

   在 $H_7{H}_6{H}_5{H}_4{H}_3{H}_2{H}_1$ 的数据是 $D_4{D}_3{D}_2{P}_3{D}_1{P}_2{P}_1$

3. 分组以形成校验关系：把信息位的海明位号化成二进制

   如 $D_4$ 在 $H_7$ 上，二进制为 0b111，$D_3$=0b110，$D_2$=0b101，$D_1$=0b11

4. 校验位取值：$P_i$ 是第 3 步得到的二进制的第 i 位为 1 的信息位的异或

   第 3 步得到的二进制的第 1 位为 1 的是 $D_1{D}_2{D}_4$ 所以 $P_1=D_1⨁D_2⨁D_4=0$

   同理 $P_2=D_1⨁D_3⨁D_4=1$，$P_3=D_2⨁D_3⨁D_4=0$

   所以 1010 对应的海明码为 1010010 下划线为校验位

5. 海明码的验证原理：

   把每个检验位和参与生成该校验位的信息位进行异或，构成 k 个校验方程

   

   若 $S_3{S}_2{S}_1$ 的值位 000，则无错；否则这个数就是错误位的位号，如 $S_3{S}_2{S}_1=001$ 说明 $H_1$ 出错了

循环冗余校验码（CRC）

CRC 的基本思想是：在 K 位信息码后再拼接 R 位的校验码，整个编码的长度为 N 位，因此，这种编码又称（$N,K$）码

CRC 码基于线性编码理论，在发送端，将要传送的 K 位二进制信息码左移 R 位，将它与生成多项式 $G(x)$ 做模 2 除法，生成一个 R 位校验码，并附在信息码后，构成一个新的二进制码（CRC 码)，共 K + R 位

在接收端，利用生成多项式对接收到的编码做模 2 除法，以检测和确定出错的位置，如整除则无错，其中生成多项式是接收端和发送端的一个约定

任意一个二进制数码都可用一个系数仅为 0 或 1 的多项式与其对应，生成多项式 $G(x)$ 的最高幂次为 R，转换成对应的二进制数有 R + 1 位

选择题：在大量数据传送过程中，常用且有效的校验方法是 CRC

模 2 除法

1. 用除数对被除数最高几位做异或
2. 除数向右移一位，若余数最高位为 1，商为 1 转第 1 步；若最高位为零 0，商为 0 转第 2 步
3. 循环直到余数位小于除数位时，该余数位最终余数

例子

问题：设生成多项式位 $G(x)=x^3+x^2+1$，信息码为 101001，求对应的 CRC 码

初始信息分析：

R = 生成多项式最高次幂 = 3，K = 信息码长度 = 6，N = K + R = 9

生成多项式 $G(x)$ 对应的二进制码为 1101

解题：

1. 将原信息左移 R 位，得到 101001000

2. 使用模 2 除法得到余数 001，则 CRC 码为 101001001

3. 接收端收到的 CRC 码，用生成多项式 $G(x)$ 做模 2 除法，若余数为 0，则码字无错

   若接收端将受到的 CRC 码 $C_9{C}_8{C}_7{C}_6{C}_5{C}_4{C}_3{C}_2{C}_1$ 进行模 2 除法，得到的余数为 010 不为零，则说明有错误

   特别的，当 n + R ≤ $2^R$ - 1 时，有纠错功能，如上面的余数 010 就表示 $C_2$ 出错了

二、定点数的表示与运算

1. 定点数的表示

无符号数和有符号数的表示

• 无符号数：指整个机械字长都是数值位，没有符号位，若机械字长为 n 则范围为 $0\sim 2^n-1$
• 有符号数：使用最高位表示符号，0 为正 1 为负，除最高位的是数值位

有符号数的机器表示有原码、补码、反码和移码，用 X 表示真值，用 $[X{]}_{\mathrm{原}}$ 表示原码，$[X{]}_{\mathrm{补}}$ 表示补码，$[X{]}_{\mathrm{反}}$ 表示反码，$[X_{\mathrm{移}}]$ 表示移码

机械数的定点表示

定点表示即约定机器数中的小数点位置是固定不变的，小数点的位置固定在数据的最高位之前，或固定在最低位之后

定点小数

定点小数是纯小数，不含有整数部分，小数点在符号位后再最高数值位前，存放如 0.xxxxx 的数据

定点小数的数据形式为 $x_0.x_1{x}_2\cdots x_n$，其中 $x_0$ 为符号位，$x_1\sim x_n$ 为数值位，$x_1$ 为最高有效位

定点整数

定点整数是纯整数，不含有小数部分，小数点在最低位之后，存放如 xxxxxx 的数据

定点整数的数据形式为 $x_0{x}_1{x}_2\cdots x_n$，其中 $x_0$ 为符号位，$x_1\sim x_n$ 为数值位，$x_n$ 为最高有效位

原码、补码、反码、移码

原码表示法

原码是一种比较简单、直观的机器数表示法，用机器数的最高位表示符号，其余位表示数的绝对值

• 纯小数的定义：$[x{]}_{\mathrm{原}}=\{\begin{array}{cc}x& 1>x\ge 0\\ 1+|x|& 0\ge x>-1\end{array}$

  对于正小数 $x=+0.x_1{x}_2\cdots x_n$，有 $[x{]}_{\mathrm{原}}=0.x_1{x}_2\cdots x_n$；对于负小数 $x=-0.x_1{x}_2\cdots x_n$，有 $[x{]}_{\mathrm{原}}=1.x_1{x}_2\cdots x_n$

  若字长为 n + 1，则原码的表示范围为 $-(1-2^{-n})\le x\le 1-2^{-n}$

• 纯整数的源码定义：$[x{]}_{\mathrm{原}}=\{\begin{array}{cc}x& 2^n>x\ge 0\\ 2^n+|x|& 0\ge x>-2^n\end{array}$（n 是整数位数）

  若 $x_1=+1110$，$x_2=-1110$，字长为 8 位，则 $[x_1{]}_{\mathrm{原}}=0,0001110$，$[x_2{]}_{\mathrm{原}}=1,0001110$

  若字长为 n + 1，则原码的表示范围为 $-(2^n-1)\le x\le 2^n-1$

注意：真值零的原码表示不唯一，即 $[+0{]}_{\mathrm{原}}=00000$ 和 $[-0{]}_{\mathrm{原}}=10000$

补码表示法

在原码对于两个不同符号数的加法（或同符号数的减法）先要比较两个数的绝对值大小，然后用绝对值大的数减去绝对值小的数，最后还要给结果选择合适的符号；而补码的加减法则统一采用加法操作实现

• 纯小数的补码定义：$[x{]}_{\mathrm{补}}=\{\begin{array}{cc}x& 1>x\ge 0\\ 2-|x|& 0>x\ge -1\end{array}$（mod 2）可直接写成 $2+x$（mod 2）

  对于正数 $x=+0.x_1{x}_2\cdots x_n$，有 $[x{]}_{\mathrm{补}}=0.x_1{x}_2\cdots x_n$；对于负数 $x=-0.x_1{x}_2\cdots x_n$，有 $[x{]}_{\mathrm{补}}=10.00\cdots 0-0.x_1{x}_2\cdots x_n$（mod 2）

  若字长为 n + 1，则补码的表示范围为 $-1\le x\le 1-2^{-n}$（比原码多表示 -1）

• 纯整数的补码定义：$[x{]}_{\mathrm{补}}=\{\begin{array}{cc}x& 2^n>x\ge 0\\ 2^{n+1}-|x|& 0\ge x\ge -2^n\end{array}$（mod $2^{n+1}$）

  若 $x_1=+1110$，$x_2=-1110$，字长为 8 位，则 $[x_1{]}_{\mathrm{补}}=0,0001110$，$[x_2{]}_{\mathrm{补}}=2^8-0,0001101=1,1110011$

  若字长为 n + 1，则补码的表示范围为 $-2^n\le x\le 2^n-1$（比原码多表示 $-2^n$）

• 模 4 补码，又称变形补码，即有两个符号位的补码，用在完成算术运算的 ALU 部件中

• 由原码求补码、补码求原码：

  • 对于正数：补码和原码相同
  • 对于负数：符号位不变，数值位取反后加 1（互换通用）

注意：真值零的补码表示是唯一的，对于小数，补码比原码多表示一个 -1；对于整数，补码比原码多表示一个 $-2^n$

选择题：模 4 补码具有模 2 补码全部优点且更容易检测加减运算中的溢出问题

反码表示法

反码通常用来作为由原码求补码或由补码求原码的中间过渡

对于负数，由原码数值位取反，或补码减一得到；对于正数与原码一致

• 纯小数的反码定义：$[x{]}_{\mathrm{反}}=\{\begin{array}{cc}x& 1>x\ge 0\\ (2-2^{-n})+x& 0\ge x>-1\end{array}$（mod $2-2^{-n}$）

  若 $x_1=+0.0110$，$x_2=-0.0110$，字长为 8 位，则 $[x_1{]}_{\mathrm{反}}=0.0110000$，$[x_2{]}_{\mathrm{反}}=1.1111111-0,0110000=1,1001111$

  若字长为 n + 1，则原码的表示范围为 $-(1-2^{-n})\le x\le 1-2^{-n}$

• 纯整数的反码定义：$[x{]}_{\mathrm{反}}=\{\begin{array}{cc}x& 2^n>x\ge 0\\ (2^{n+1}-1)+x& 0\ge x>-2^n\end{array}$（mod $2^{n+1}-1$）

  若 $x_1=+1011$，$x_2=-1011$，字长为 8 位，则 $[x_1{]}_{\mathrm{反}}=0,0001011$，$[x_2{]}_{\mathrm{反}}=1,1111111-0,0001011=1,1110100$

  若字长为 n + 1，则原码的表示范围为 $-(2^n-1)\le x\le 2^n-1$

注意：真值零的反码表示不唯一，即 $[+0{]}_{\mathrm{反}}=0.0000$ 和 $[-0{]}_{\mathrm{反}}=1.1111$

移码表示法

移码常用来表示浮点数的阶码，它只能表示整数

移码就是在真值 X 上加上一个常数（偏置值），通常这个常数取 $2^n$，相当于向正方向偏移了若干单位，所以叫移码

移码定义为 $[x{]}_{\mathrm{移}}=2^n+x$（$2^n>x\ge -2^n$ 其中机器字长为 n + 1）

正数 $x_1=+10101$，$x_2=-10101$，字长为 8 位，则 $[x{]}_{\mathrm{移}}=2^7+10101=1,0010101$，$[x{]}_{\mathrm{移}}=2^7+(-10101)=0,1101011$

移码具有以下特点：

1. 移码中零的表示唯一，$[+0{]}_{\mathrm{移}}=2^n+0=[-0{]}_{\mathrm{移}}=2^n-0=100\cdots 0$（n 个 0）
2. 一个真值的移码和补码仅差一个符号位，$[x{]}_{\mathrm{补}}$ 的符号位取反即得 $[x{]}_{\mathrm{移}}$
3. 移码全 0 时，对应真值的最小值 $-2^n$；移码全 1 时，对应真值的最大值 $2^n-1$
4. 移码保持了数据原有的大小顺序，移码大真值就大，移码小真值就小

2. 定点数的运算

定点数的移位运算

算术移位

算术移位的对象是有符号数，在移位过程中符号位保持不变（移码是浮点数，没有移位）

对于真值，左移一位若不产生溢出，相当于乘以 2；右移一位若不产生舍去，相当于除以 2

• 正数的原码、补码、反码相同，在移位后使用 0 填充空位
• 负数的原码、补码、反码不同，所以要分开考虑：
  • 原码：移位时仅移动数值位，空位填 0
  • 反码：移位时仅移动数值位，空位填 1（与原码相反）
  • 补码：移位时仅移动数值位，左移空位填 0，右移空位填 1

注意：不论是正数还是负数，移位后其符号位均不变，且移位后都相当于对真值补 0

逻辑移位

逻辑移位将操作数视为无符号数（正数），所以移位与算术位移正数的方法一样，空位填 0

循环位移

循环移位分为带进位标志位 CF 的循环移位（大循环）和不带进位标志位的循环移位（小循环）

循环移位的主要特点是，移出的数位又被移入数据中，而是否带进位则要看是否将进位标志位加入循环位移

• 不带进位标志位：移出位即移入标志位，也移入空位
• 带进位标志位：移出位移入标志位，标志位移到空位

循环移位操作特别适合将数据的低字节数据和高字节数据互换

原码定点数的加减法运算

设 $[X{]}_{\mathrm{原}}=x_s.x_1{x}_2\cdots x_n$ 和 $[Y{]}_{\mathrm{原}}=y_s.y_1{y}_2\cdots y_n$，进行加减运算的规则如下

加法规则：

1. 先判符号位
2. 若相同，则绝对值相加，结果符号位不变
3. 若不同，则做减法，绝对值大的数减去绝对值小的数，结果符号位与绝对值大的数相同

减法规则：

1. 将减数符号取反
2. 将它们按原码加法进行运算

注意：运算时注意机器字长，当左边位出现溢出时，将溢出位丢掉

补码定点数加减法运算

补码加减运算规则简单，易于实现，因此计算机系统中普遍采用补码加减运算

1. 参与运算的两个操作数均用补码表示，符号位也要参与运算
2. 若做加法，则两数的补码直接相加；若做减法，则取减数的相反值再取补码，再相加
   • 当参加运算的数是定点小数时，模 M = 2；当参加运算的数是定点整数时，模 $M=2^n+1$
   • 公式：$[A+B{]}_{\mathrm{补}}=[A{]}_{\mathrm{补}}+[B{]}_{\mathrm{补}}$（mod M），$[A-B{]}_{\mathrm{补}}=[A{]}_{\mathrm{补}}+[-B{]}_{\mathrm{补}}$（mod M）
   • 注意：mod M 运算是为了将溢出位丢掉
3. 补码运算的结果亦为补码（符号位在计算时直接得出）

符号扩展

在计算机算术运算中，有时必须把 n 位定点数转换成 m 位定点数（m > n），这称为符号扩展

注意：符号扩展时，整数的多余部分在符号位后；小数的多余部分在末尾

正数的符号扩展：新符号位的值等于原符号位的值，多余部分使用 0 填充

负数的符号扩展：根据机械数的不同有不同的处理

• 原码：新符号位的值等于原符号位的值，多余部分使用 0 填充

• 补码：新符号位的值等于原符号位的值，多余部分整数用 1，小数用 0 填充

  整数是 $1,0101\to 1,11110101$；而小数是 $1.0101\to 1.01010000$

• 反码：新符号位的值等于原符号位的值，多余部分使用 1 填充

溢出概念和判别方法

溢出是指运算结果超过了数的表示范围，称大于机器所能表示的最大正数为上溢，称小于机器所能表示的最小负数为下溢

仅当两个符号相同的数相加或两个符号相异的数相减才可能产生溢出，补码的溢出判断有 3 种

采用一位符号位

减法运算在机器中是用加法器实现的，因此参加操作的两个数符号相同，结果又与原操作数符号不同，则表示结果溢出

设 A 的符号为 $A_S$，B 的符号为 $B_S$，运算结果的符号为 $S_S$,，则溢出逻辑表达式为 $V=A_S{B}_S\overline{S_S}+\overline{A_S{B}_S}{S}_S$

解释：在离散数学中 $ab=a\mathrm{\&}b$，$a+b=a|b$，$\bar{a}=\sim a$，式子意思是：两个负号得正号 | 两个正号得负号

若 V = 0，表示无溢出；若 V = 1，表示有溢出

根据符号和数据进位情况

若符号位的进位 $C_S$ 与最高数位的进位 $C_S$ 相同，则说明没有溢出，否则表示发生溢出

溢出逻辑判断表达式为 $V=C_S⨁C_1$，若 V = 0，表示无溢出；V = 1，表示有溢出

思路：根据补码溢出只会发生在，两个负数相加或两个正数相加的情况下，它们在单进位时都是溢出的

负数合法时，进位是双进位的；正数合法时，进位是零进位的

采用双符号位

双符号位法也称模 4 补码。这里的思路和上面的一样，也是看进位的，且会分析是什么溢出

运算结果的两个符号位 $S_{s1}{S}_{s2}$ 相同，表示未溢出；运算结果的两个符号位 $S_{s1}{S}_{s2}$ 不同，表示溢出，此时最高位符号位代表真正的符号

1. $S_{s1}{S}_{s2}=00$：表示结果为正数，无溢出（无进位）
2. $S_{s1}{S}_{s2}=01$：表示结果正溢出（单进位）
3. $S_{s1}{S}_{s2}=10$：表示结果负溢出（单进位）
4. $S_{s1}{S}_{s2}=11$：表示结果为负数，无溢出（双进位）

溢出逻辑判断表达式为 $V=S_{s1}⨁S_{s2}$，若 V = 0，表示无溢出；若 V = l，表示有溢出

定点数的乘法运算

原码一位乘法

原码一位乘法的符号位与数值位分开求，乘积符号由两个数的符号位异或形成，乘积的数值则是两个数的绝对值相乘之积

设 $[X{]}_{\mathrm{原}}=x_s.x_1{x}_2\cdots x_n$，$[Y{]}_{\mathrm{原}}=y_s.y_1{y}_2\cdots y_n$，则运算规则如下：

1. 被乘数和乘数均取绝对值参加运算，符号位为 $x_s⨁y_s$
2. 部分积的长度同被乘数，取 n + 1 位，以便存放乘法过程中绝对值大于等于 1 的值，初值为 0
3. 从乘数的最低位 y，开始判断：
   • 若 $y_n=1$，则部分积加上被乘数 |x|，然后逻辑右移一位
   • 若 $y_n=0$，则部分积加上 0，然后逻辑右移一位
4. 重复步骤 3，判断 n 次

注意：考虑到运算时可能出现绝对值大于 1 的情况，所以部分积和被乘数取双符号位（感觉可以单符号位）

原码一位乘法例子

题目：设机器字长为 5 位（含 1 位符号位，n = 4)，x = -0.1101，y = 0.1011，采用原码一位乘法求 x · y

|x| = 00.1101，|y| = 00.1011，原码一位乘法的求解过程如下

符号位 $P_s=x_s⨁y_s=1⨁0=1$，得 x · y = -0.10001111

补码一位乘法（Booth 算法）

这是一种有符号数的乘法，采用相加和相减操作计算补码数据的乘积

设 $[X{]}_{\mathrm{补}}=x_s.x_1{x}_2\cdots x_n$，$[Y{]}_{\mathrm{补}}=y_s.y_1{y}_2\cdots y_n$，则运算规则如下：

1. 符号位参与运算，运算的数均以补码表示
2. 被乘数一般取双符号位参与运算，部分积取双符号位，初值为0，乘数可取单符号位
3. 乘数末位增设附加位 $y_{n+1}$，且初值为 0
4. 根据 $(y_n,y_{n+1})$ 的取值来进行操作，见表 2.2
5. 移位按补码算术右移规则进行
6. 其中 4，5 步要进行 n 次，最后再进行一次第 4 步

补码一位乘法例子

题目：设机器字长为 5 位（含 1 位符号位，n = 4），x = -0.1101，y = 0.1011，采用 Booth 算法求 x · y

$[x{]}_{\mathrm{补}}=11.0011$，$[-x{]}_{\mathrm{补}}=00.1101$，$[y{]}_{\mathrm{补}}=0.1011$，Booth 算法求解过程如下：

所以 $[x\cdot y{]}_{\mathrm{补}}=1.01110001$，得 x · y = -0.10001111

补码一位乘法的证明

1. 设 $[X{]}_{\mathrm{补}}=x_0.x_1{x}_2\cdots x_n$

   当 $x\ge 0$ 时，$[X{]}_{\mathrm{补}}=0.x_1{x}_2\cdots x_n={\displaystyle \sum _{i=1}^n{x}_i{2}^{-i}=x}$

   当 $x<0$ 时，$[X{]}_{\mathrm{补}}=1.x_1{x}_2\cdots x_n=2+x$ 得 $x=1.x_1{x}_2\cdots x_n-2=-1+{\displaystyle \sum _{i=1}^n{x}_i{2}^{-i}}$

   综上可得 $x=-x_0+{\displaystyle \sum _{i=1}^n{x}_i{2}^{-i}}$ 真值与补码间关系

2. 然后证明 $[x\cdot y{]}_{\mathrm{补}}=[x{]}_{\mathrm{补}}\cdot y=[x{]}_{\mathrm{补}}\cdot (-y_0+{\displaystyle \sum _{i=1}^n{x}_i{2}^{-i})}$ 非常重要，证出这个基本证完

   1. 首先是 x 符号任意，y 是正的。若 x 是正的，显然上式成立；当 x 是负的：
      • $[x{]}_{\mathrm{补}}=2+x=2^{n+1}+x$（mod 2），$[y{]}_{\mathrm{补}}=y$
      • $[x{]}_{\mathrm{补}}\cdot [y{]}_{\mathrm{补}}=[x{]}_{\mathrm{补}}\cdot y=2^{n+1}\cdot y+x\cdot y=2(y_1\cdots y_n)+x\cdot y$
      • 其中 $(y_1\cdots y_n)$ 是大于 0 的正整数，根据模运算有 $2(y_1\cdots y_n)=2$（mod 2）
      • 所以有 $[x{]}_{\mathrm{补}}\cdot [y{]}_{\mathrm{补}}=2+x\cdot y=[x\cdot y{]}_{\mathrm{补}}$（mod 2）
      • 即 $[x\cdot y{]}_{\mathrm{补}}=[x{]}_{\mathrm{补}}\cdot [y{]}_{\mathrm{补}}=[x{]}_{\mathrm{补}}\cdot y$
   2. 接着证明 x 符号任意，y 是负的。
      • $[x{]}_{\mathrm{补}}=x_0.x_1{x}_2\cdots x_n$，$[y{]}_{\mathrm{补}}=1.y_1{y}_2\cdots y_n$ 即 $y=0.y_1{y}_2\cdots y_n-1$
      • $[x+y{]}_{\mathrm{补}}=2+(x+y)=4+(x+y)=(2+x)+(2+y)=[x{]}_{\mathrm{补}}+[y{]}_{\mathrm{补}}$（mod 2）
      • $x\cdot y=x(0.y_1{y}_2\cdots y_n)-x$ 代入 $[x\cdot y{]}_{\mathrm{补}}$ 得
      • $[x\cdot y{]}_{\mathrm{补}}=[x(0.y_1{y}_2\cdots y_n)-x{]}_{\mathrm{补}}=[x{]}_{\mathrm{补}}(0.y_1{y}_2\cdots y_n)+[-x{]}_{\mathrm{补}}$
   3. 综合 1 和 3 就得到 $[x\cdot y{]}_{\mathrm{补}}=[x{]}_{\mathrm{补}}(0.y_1{y}_2\cdots y_n)-[x{]}_{\mathrm{补}}\cdot y_0=[x{]}_{\mathrm{补}}\cdot (-y_0+{\displaystyle \sum _{i=1}^n{x}_i{2}^{-i})}$ 证毕

3. 最后把 2 式展开再修改一下就得出证明

   $[x\cdot y{]}_{\mathrm{补}}=[x{]}_{\mathrm{补}}(-y_0+y_1{2}^{-1}+\cdots +y_n{2}^{-n})$

   $=[x{]}_{\mathrm{补}}[(y_1-y_0)2^0+\cdots +(y_n-y_{n-1})2^{-(n-1)}+(0-y_n)2^{-n}]$

   $=[x{]}_{\mathrm{补}}\cdot {\displaystyle \sum _{i=1}^n(y_{i+1}-y_i)2^{-i}}$

   这就是为什么 $y_{n+1}-y_n=0$ 时加 0；1 时加 $[X{]}_{\mathrm{补}}$；-1 时加 $[-X{]}_{\mathrm{补}}$

这里跳了步不是很好，更加详细得证明请看这里

乘法运算总结

定点数的除法运算

*恢复余数法

恢复余数法就是被除数不够减时，恢复被除数，并设置商为 0

1. 被除数和除数均取绝对值参加运算，符号位为 $x_s⨁y_s$
2. 使用被除数减除数，若大于零商取 1，左移；若小于零，被除数恢复，商取 0，左移
3. 第 2 步进行 n + 1 次就得到结果

不恢复余数法

设 $[X{]}_{\mathrm{原}}=x_s.x_1{x}_2\cdots x_n$，$[Y{]}_{\mathrm{原}}=y_s.y_1{y}_2\cdots y_n$，则：

1. 商的符号：$Q_s=x_s⨁y_s$
2. 商的数值：$|Q|=|X|/|Y|$

求 |Q| 的不恢复余数法运算规则如下：

1. 符号位不参与运算
2. 先用被除数减去除数 $(|X|-|Y|=|X|+(-|Y|)=|X|+[-|Y|{]}_{\mathrm{补}})$
   • 当余数为正时，商上 1，余数和商逻辑左移一位，再减去除数
   • 当余数为负时，商上 0，余数和商逻辑左移一位，再加上除数
3. 当第 n + 1 步余数为负时，需要加上 |Y| 来恢复余数

思路：如果 A - B < 0 那么就应该判断 A - B / 2 来确定商，而这里的不恢复是当 A - B < 0 就使用 A - B + B / 2 = A - B / 2 来取消掉余数的恢复操作

不恢复余数法例子

题目：设机器字长为 5 位（含 1 位符号位，n = 4），x = 0.1011，y = 0.1101，采用原码加减交替除法求 x / y

|x| = 0.1011，|y| = 0.1101，$[|y|{]}_{\mathrm{补}}$= 0.1101，$[-|y|{]}_{\mathrm{补}}$ = 1.0011

因此 $Q_s=x_s⨁y_s=0$，得 $x/y=+0.1101$，余 $0.0111\times 2^{-4}$

补码一位除法（加减交替法）

补码一位除法的特点是，符号位与数值位一起参加运算，商符自然形成

1. 符号位参加运算，除数与被除数均用补码表示，商和余数也用补码表示
2. 若被除数与除数同号，则被除数减去除数；若被除数与除数异号，则被除数加上除数
3. 若余数与除数同号，则商上 1，余数逻辑左移一位减去除数；若余数与除数异号，则商上 0，余数逻辑左移一位加上除数
4. 重复执行第 3 步操作 n 次
5. 若对商的精度没有特殊要求，则一般采用末位恒置 1 法

思路：思路还是不恢复余数法的思路，但是加了补码的性质下去

• 第 2 步其实是为了使用 |X| - |Y| 确定符号位
• 第 3 中余数与除数同号就相当于不恢复余数法的正，异号就相当于负；由此得出商位

补码一位除法例子

题目：设机器字长为 5 位（含 1 位符号位，n = 4），x = 0.1000，y = -0.1011，采用补码加减交替法求 x / y $[x{]}_{\mathrm{补}}=00.1000$，$[y{]}_{\mathrm{补}}=11.0101$，$[-y{]}_{\mathrm{补}}=00.1011$

所以 $[x/y{]}_{\mathrm{补}}=1.0101$，余 $0.0111\times 2^{-4}$

除法运算总结

3. C 语言中的整数及其转换

有符号和无符号数的转换

在 C 语言中，有无符号的转换只是把机械数简单的从有符号看成无符号，里面的数值没有变

如短整型变量是 -1，它变成无符号短整型就是 $2^{16}-1=65535$

数值还是那些数值，关键看我们是如何看的，我们用有符号来看它就是有符号的；我们用指令来看，它就是指令

注意：一般代码内，int i = -1; 那么 i 的值就是 0xffffffff，即定点数一般使用补码表示

不同字长整数的转换

1. 长字节整形转换成短字节整形，会抹去高位部分

   int i = 0x12345678;
   short j = i;  // 0x5678

2. 短字节整形转换成高字节整形，会扩展符号位

   short i = 0x9123;
   int j = i;  // 0xffff9123
   unsigned int k = i;  // 0xffff9123
   
   unsigned short i = 0x9123;
   int j = i;  // 0x00009123
   unsigned int k = i;  // 0x00009123

4. 数据的存储和排列

大小端方式存储

用**最低有效字节（LSB）和最高有效字节（MSB）**来分别表示数的低位和高位；01234567H 中 MSB=01H、LSB=67H

现代计算机基本上都采用字节编址，即每个地址编号中存放 1 字节

int 和 float 型数据占 4 字节，double 型数据占 8 字节，short 型数占 2 字节，char 和 byte 和 boolean 占 1 字节

根据数据中各字节在连续字节序列中的排列顺序不同，分成大端方式和小端方式：

• 大端方式（big endian）：高位对应低地址，低位对应高地址
• 小端方式（little endian）：高位对应高地址，低位对应低地址

一行机械指令：4004d3: 01 05 64 94 04 08 add %eax, 0x8049464

可以看出里面的操作数地址是使用小端方式存储的

边界对齐方式

假设存储字长为 32 位，可按字节、半字和字寻址

对于机器字长为 32 位的计算机，数据以边界对齐方式存放，半字地址一定是 2 的整数倍，字地址一定是 4 的整数倍，这样无论所取的数据是字节、半字还是字，均可一次访存取出

存储的数据不满足上述要求时，填充空白字节使其符合要求，虽然浪费了一些存储空间，但提高取指令和取数的速度

数据不按边界对齐方式存储时，半字长或字长的指令可能会存储在两个存储字中，此时需要两次访存及调整，影响效率

typedef struct a {
    long long a;  // 0
    char b;  // 8
    short c;  // A
    int d;  // C
    long long e;  // 10
} A;

RISC 如 ARM 采用边界对齐方式，而 CISC 如 x86 都支持，因为对齐方式取指令时间相同，因此能适应指令流水

注意：长度为 $2^n$ 的数据类型，所在的地址必定也是 $2^n$ 的倍数

思考：64 位是不是内存中一个单元其实是 8 个字节，我们取地址时先根据高位地址取字，再根据低 3 位取字节

5. 硬件（来源习题）

加法器

溢出标志位 OF 表示结果是否溢出，溢出了置 1

符号标志位 SF 表示结果的符号，负数置 1

进位标志位 CF 表示加法器最高位是否有进位

乘法器

一般乘法器由 ALU、位移器、寄存器、相应的控制逻辑实现

控制逻辑的作用是控制循环次数，控制加法和位移操作

阵列乘法器器，是指不需要循环，直接列 n 个数错位相加，这样电路虽然多，但时钟周期是 1

三、浮点数的表示与运算

1. 浮点数的表示

浮点数的表示格式

浮点数表示为 $N=r^E\times M$ 其中，r 是浮点数阶码的底，与尾数的基数相同；E 和 M 都是有符号的定点数，E 称为阶码，M 称为尾数；浮点数由阶码和尾数组成

阶码是整数，阶符是阶码的符号，阶码的位数表示浮点数的表示范围；它们的数值表示浮点数小数点的位置

数符是浮点数的符号，尾数的位数反映浮点数的精度

规格化浮点数

为了提高运算的精度，需要充分地利用尾数的有效数位，即规定尾数的最高数位必须是一个有效值

规格化操作，是指调整一个非规格化浮点数的尾数和阶码的大小，令非零的浮点数在尾数的最高数位上保证是一个有效值

• 左规：将尾数算术左移一位、阶码减 1（基数为 2 时）；左归可能要进行多次；当浮点数运算的结果为非规格化时使用
• 右规：将尾数算术右移一位、阶码加 1（基数为 2 时）；只需进行一次；当浮点数运算的结果尾数出现溢出时使用

规格化浮点数的尾数 M 的绝对值应满足条件 1 / r ≤ |M| ≤ 1，规格化表示的尾数形式如下：

• 原码规格化后：

  正数为 $0.1??\cdots ?$ 的形式，其最大值表示为 $0.11\cdots 1$，最小值表示为 $0.100\cdots 0$，尾数的表示范围为 $1/2\le M\le (1-2^{-n})$ 负数为 $1.1??\cdots ?$ 的形式，其最大值表示为 $1.10\cdots 0$，最小值表示为 $1.11\cdots 1$，尾数的表示范围为 $-(1-2^{-n})\le M\le -1/2$

• 补码规格化后：

  正数为 $0.1??\cdots ?$ 的形式，其最大值表示为 $0.11\cdots 1$，最小值表示为 $0.100\cdots 0$，尾数的表示范围为 $1/2\le M\le (1-2^{-n})$

  负数为 $1.0??\cdots ?$ 的形式，其最大值表示为 $1.01\cdots 1$，最小值表示为 $1.00\cdots 0$，尾数的表示范围为 $-1\le M\le -(1/2+2^{-n})$

当浮点数尾数的基数为 2 时，原码规格化数的尾数最高位一定是 1，补码规格化数的尾数最高位一定与尾数符号位相反

当基数为 4 时，原码规格化形式的尾数最高两位不全为 0；当基数为 8 时，原码规格化形式的尾数最高 3 位不全为 0

思考：其实规格化可以是没有小数或没有整数部分，但我们常用没有整数部分的；规格化是为了保证没有浪费尾数位，如 0.0000123456 -> 0.123456

思考：当基数不为 2 时，其实也是保证没有浪费尾数位，即没有整数位，但左乘基就有整数位

*浮点数的表示范围

运算结果大于最大正数时称为正上溢，小于绝对值最大负数时称为负上溢，正上溢和负上溢统称上溢

数据一旦产生上溢，计算机必须中断运算操作，进行溢出处理

当运算结果在 0 至最小正数之间时称为正下溢，在 0 至绝对值最小负数之间时称为负下溢，正下溢和负下溢统称下溢

数据下溢时，浮点数值趋于零，计算机仅将其当作机器零处理

选择题：浮点数格式如下：7 位阶码，1 位数符，8 位尾数。若阶码用移码，尾数用补码表示，则浮点数所能表示数的范围是 $-2^{63}\sim (1-2^{-8})\times 2^{63}$；阶码最高位是 63，尾数范围是 $-1\sim 1-2^{-8}$

注意：浮点数的范围和阶码尾数的位数有关，且要注意使用的编码格式，还有浮点数的标准

IEEE 754 标准

定义

IEEE 754 标准规定常用的浮点数格式有短浮点数（单精度、float 型）、长浮点数（双精度、double 型)、临时浮点数

IEEE 754 标准的浮点数（除临时浮点数外），是尾数用采取隐藏位策略的原码表示，且阶码用移码表示的浮点数

用移码表示阶码是因为：易于比较阶码；检验特殊值容易（0 或 $\mathrm{\infty }$）

以短浮点数为例，最高位为数符位；其后是 8 位阶码，以 2 为底，用移码表示，阶码的偏置值为 $2^{8-1}-1=127$

其后 23 位是原码表示的尾数数值位，对于规格化的二进制浮点数，数值的最高位是 1（隐含掉），尾数数值实际上是 24 位

阶码是以移码形式存储的，对于短浮点数，偏置值为 127；对于长浮点数，偏置值为 1023，存储浮点数阶码部分之前，偏置值要先加到阶码真值上

IEEE 754 标准中，规格化的短浮点数的真值为 $(-1{)}^s\times 1.M\times 2^{E-127}$；规格化长浮点数的真值为 $(-1{)}^s\times 1.M\times 2^{E-1023}$

短浮点数 E 的取值为 1~254，M 为 23 位，共 32 位；长浮点数E的取值为 1~2046，M 为 52 位，共 64 位

注意：短浮点数与长浮点数采用隐含尾数最高数位法，多表示一位尾数；临时浮点数又称扩展精度浮点数，无隐含位

注意：浮点数有一些保留位：

1. +0 和 -0 的表示：阶码全为 0 尾数全为 0，正负由符号位决定
2. $+\mathrm{\infty }$ 和 $-\mathrm{\infty }$ 的表示：阶码全为 1 尾数全为 0，正负由符号位决定

思考：因为阶码全为 0 和全为 1 被占用了，所以阶码范围是 1 ~ 254；和移码相比还加了 1，如阶码 0x80 由 0 变成了 1

例题

题目：把 x = -8.25 转换成 IEEE 754 单精度浮点型格式

1. x 是负的，所以数符位取 1
2. 把 8.25 转二进制得 1000.01
3. 右移三位得 1.00001 阶码是 3
4. 阶码加上偏置值有 3 + 127 = 130 = 1000 0010
5. 1.00001 隐含掉最高位有 00001
6. 把数符、阶码、尾数拼接起来得 1 10000010 00001000000000000000000 = C104 0000H

定点、浮点表示的区别

1. 数值的表示范围：若定点数和浮点数的字长相同，则浮点数的数值范围远远大于定点数

2. 精度：

   精度，是指一个数所含有效数值位的位数

   对于字长相同的定点数和浮点数来说，浮点数虽然扩大了数的表示范围，但精度降低了

3. 数的运算：

   浮点数包括阶码和尾数两部分，运算时不仅要做尾数的运算，还要做阶码的运算，而且运算结果要求规格化，所以浮点运算比定点运算复杂

4. 溢出问题：

   在定点运算中，当运算结果超出数的表示范围时，发生溢出

   浮点运算中，只有规格化后阶码超出所能表示的范围时，才发生溢出（尾数溢出不算溢出）

2. 浮点数的加减运算

如何进行加减运算

浮点数运算的特点是阶码运算和尾数运算分开进行，浮点数的加减运算一律采用补码；IEEE 754 可能再计算完后转回原码

1. 对阶：使得两个数的阶码相等

   求阶差，然后以小阶向大阶看齐的原则，将阶码小的尾数右移一位（基数为 2）阶加 1，直到阶码相等

   尾数右移时，舍弃掉有效位会产生误差，影响精度

2. 尾数求和：将对阶后的尾数按定点数加（减）运算规则运算

3. 规格化：

   双符号位其补码规格化形式为 $[S{]}_{\mathrm{补}}=00.1xx\cdots x$；当尾数小于 0 时，其补码规格化形式为 $[S{]}_{\mathrm{补}}=11.0xx\cdots x$

   当尾数求和后不符合规格，那么就会使用左规或右规进行调整

   • 左规：当尾数出现 00.0x 或 11.1x 时，需左规，直到尾数为 00.1x 或 11.0x
   • 右规：当尾数求和结果溢出（如尾数为 10.x 或 01.x）时，需右规

4. 舍入：在对阶或右规的过程中，可能会将尾数低位丢失，引起误差，影响精度

   引入了 0 舍 1 入、和恒置 1，目的是让引起的误差更小，令平均误差为 0 有舍有入

   • 0 舍 1 入法：

     在尾数右移时，被移去的最高数值位为 0，则舍去；为 1，则在尾数的末位加 1

     这样做可能会使尾数又溢出，此时需再做一次右规

   • 恒置 1 法：

     尾数右移时，不论丢掉的最高数值位是 1 还是 0，都使右移后的尾数末位恒置 1

     这种方法同样有使尾数变大和变小的两种可能

5. 溢出判断：浮点数加减运算最后一步也需判断溢出

   在浮点数中不根据尾数判断溢出，若尾数溢出了会进行右归规，之后再根据阶码判断溢出

   浮点数的溢出与否是由阶码的符号决定的，以双符号位补码为例：

   • 当阶码的符号位出现 01 时，即阶码大于最大阶码时，表示上溢，进入中断处理
   • 当阶码的符号位出现 10 时，即阶码小于最小阶码时，表示下溢，按机器零处理

   左规可能上溢，右规可能下溢：0011 + 0001 上溢，1100 + 1111 下溢

6. C 语言中的浮点数类型及类型转换：

   C 语言中的 float 和 double 类型分别对应于 IEEE 754 单精度浮点数和双精度浮点数

   在 C 程序中等式的赋值和判断中会出现强制类型转换，以 char→int→long→double 和 float→double 最为常见，从小到大

   • 从 int 转换为 float 时，虽然不会发生溢出，但 float 数据位更少可能有数据舍入，若从 int 转换为 double 则不会出现
   • 从 int 或 float 转换为 double 时，因为 double 的有效位数更多，因此能保留精确值
   • 从 double 转换为 float 时，因为 float 表示范围更小，因此可能发生溢出；有效位数变少，因此可能被舍入
   • 从 float 或 double 转换为 int 时，因为 int 没有小数部分，所以数据仅保留整数部分，影响精度；由于 int 的表示范围更小，因此可能发生溢出

例子

题目：已知十进制数 X = -5 / 256、Y = +59 / 1024，按机器补码浮点运算规则计算 X - Y，结果用二进制表示，浮点数格式如下：阶符取 2 位，阶码取 3 位，数符取 2 位，尾数取 9 位

$X=(-101{)}_2/2^8=(-0.101)\cdot 2^{-5}$；$Y=(111011{)}_2/2^{10}=(0.111011)\cdot 2^{-4}$

1. 对阶：X 阶码小，X 右规得 $X=(-0.0101)\cdot 2^{-4}$
2. 尾数求差：使用原码相加 X + -Y，由于符号相同直接加 -0.0101 + -0.111011 = -1.001111
3. 溢出判断：尾数溢出，结果右规一次 -0.1001111 阶码加一 -3
4. 结果：结果真值为 $2^{-3}\cdot (-0.1001111)$

注意：浮点数的计算方法有很多种，如原码、补码计算；二进制表示要注意看编码是移码还是补码，符号位是单还是双

四、算术逻辑单元（ALU）

运算器承担了执行各种算术和逻辑运算的工作，运算器由算术逻辑单元（Arithmetic Logic Unit，ALU）、累加器、状态寄存器和通用寄存器组等组成

ALU 的基本功能包括加、减、乘、除四则运算，与、或、非、异或等逻辑运算，以及移位、求补等操作

计算机运行时，运算器的操作和操作种类由控制器决定

运算器处理的数据来自存储器；处理后的结果数据通常送回存储器，或暂存在运算器中

1. 串行加法器和并行加法器

一位全加器

全加器（FA）是最基本的加法单元，有三个输入：加数 $A_i$、加数 $B_i$ 与低位传来的进位 $C_{i-1}$；有两个输出：本位和 $S_i$ 与向高位的进位 $C_i$

和表达式：$S_i=A_i⨁B_i⨁C_{-1}$；进位表达式：$C_i=A_i{B}_i+(A_i⨁B_i)C_{i-1}$

串行加法器

在串行加法器中，只有一个全加器，数据逐位串行送入加法器中进行运算

若操作数长 n 位，则加法就要分 n 次进行，每次产生一位和，并且串行逐位地送回寄存器

进位触发器用来寄存进位信号，以便参与下一次运算

串行加法器具有器件少、成本低的优点，但运算速度慢，多用于某些低速的专用运算器

并行加法器

并行加法器由多个全加器组成，其位数与机器的字长相同，各位数据同时运算

虽然操作数的各位是同时提供的，但高位的运算结果依赖于低位所产生的进位

并行加法器的最长运算时间主要是由进位信号的传递时间决定的，而每个全加器本身的求和延迟只是次要因素

通常将传递进位信号的逻辑线路连接起来构成的进位网络称为进位链

进位表达式为 $C_i=G_i+P_i{C}_{i-1}$ 式中 $G_i$ 是进位产生函数，$G_i=A_i{B}_i$；$P_i$ 是进位传递函数，$P_i=A_i⨁B_i$.

并行加法器的进位通常分为串行进位与并行进位

串行进位

把 n 个全加器串接起来，就可进行两个 n 位数的相加，这种加法器称为串行进位的并行加法器

串行进位又称行波进位，每级进位直接依赖于前一级的进位，即进位信号是逐级形成的

• $C_1=A_1{B}_1+(A_1⨁B_1)C_0$ 或 $(C_1=G_1+P_1{C}_0)$
• $C_2=A_2{B}_2+(A_2⨁B_2)C_1$ 或 $(C_2=G_2+P_2{C}_1)$
• $C_n=A_n{B}_n+(A_n⨁B_n)C_{n-1}$ 或 $(C_n=G_n+P_n{C}_{n-1})$

低位运算产生进位所需要的时间将可能影响直至最高位运算的时间，所以加快进位产生和提高传递的速度是关键

并行进位

并行进位又称先行进位、同时进位，其特点是各级进位信号同时形成，其思路为：

• $C_1=G_1+P_1{C}_0$
• $C_2=G_2+P_2{C}_1=G_2+P_2{G}_1+P_2{P}_1{C}_0$
• $C_3=G_3+P_3{C}_2=G_3+P_3{G}_2+P_3{P}_2{G}_1+P_3{P}_2{P}_1{C}_0$
• $C_4=G_4+P_4{C}_3=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$

所有的进位输出仅由 $G_i$、$P_i$ 及最低进位输入 $C_0$ 决定，而不依赖于 $C_{i-1}$，因此各级进位输出可以同时产生

这种进位方式是快速的，与字长无关；随着加法器位数的增加，电路结构会变得很复杂，所以完全采用并行进位是不现实的

实际上通常采用分组并行进位方式，以 m 个为一组，把 n 位全加器分为若干小组

小组内的各位之间实行并行快速进位，小组与小组之间可以采用串行进位方式，也可以采用并行快速进位方式

单级先行进位方式

单级先行进位方式，又称组内并行、组间串行进位方式；以 16 位加法器为例，可分为 4 组，每组 4 位

组内的进位逻辑使用并行方式，进位信号 $C_1\sim C_4$ 是同时产生的，实现的电路称为 4 位先行进位电路（CLA）

把 4 个这样的 CLA 加法器串联起来，构成的 16 位单级先行进位加法器

多级先行进位公式

多级先行进位方式，又称组内并行、组间并行进位方式；以 16 位加法器为例，可分为 4 组，每组 4 位

第一小组的进位输出 $C_4$ 可以写为：

• $C_4=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=G_1^{\ast }+P_1^{\ast }{C}_0$

• $G_1^{\ast }=G_4+P_4{G}_3+P_4{P}_3{G}_2+P_4{P}_3{P}_2{G}_1$，$P_1^{\ast }=P_4{P}_3{P}_2{P}_1$

• $G_i^{\ast }$ 称为组进位产生函数，$P_i^{\ast }$ 称为组进位传递函数，这两个辅助函数只与 $P_i$、$G_i$ 有关

以此类推：$C_8=G_2^{\ast }+P_2^{\ast }{C}_4=G_2^{\ast }+P_2^{\ast }{G}_1^{\ast }+P_2^{\ast }{P}_1^{\ast }{C}_0$，$C_{12}$=......

那么 $C_4,C_8,C_{12},C_{16}$ 可以根据 $G_i^{\ast },P_i^{\ast }$ 同时产生；可以知道每个组只需要提供 $P_i^{\ast },G_i^{\ast }$ 就好了

那么就有组 1 提供 $G_1^{\ast },P_1^{\ast }$ 和 $C_1,C_2,C_3$ 需要 $C_0$，其他组类似，这种电路称为成组先行进位电路（BCLA）

16 位的两级先行进位加法器可由 4 个 BCLA 加法器和 1 个 CLA 电路构成

首先 CLA 根据 $G_i^{\ast },P_i^{\ast }$ 同时产生 $C_4,C_8,C_{12},C_{16}$ 给 BCLA 加法器内部产生其他进位，如 $C_1{C}_2{C}_3$ 等

这种方法可以扩展到多于两级的先行进位加法器，如用三级先行进位结构设计 64 位加法器

这种加法器的优点是字长对加法时间影响甚小，缺点是造价较高

2. 算术逻辑单元的功能和结构

带标志加法器

无符号数加法器只能用于两个无符号数相加，不能进行带符号整数的加/减运算

为了能进行带符号整数的加/减运算，还需要在无符号数加法器的基础上增加相应的逻辑门电路，使得加法器不仅能计算和/差，还要能生成相应的标志信息

• 溢出标志的逻辑表达式为 $OF=C_n⨁C_{n-1}$
• 符号标志就是和的符号，即 $SF=F_{n-1}$
• 零标志 ZF = 1 当且仅当 F = 0
• 进位/借位标志 $CF=C_{out}⨁C_{in}$，即当 $C_{in}=0$ 时，CF 为进位 $C_{out}$；当 $C_{in}=1$ 时，CF 为进位 $C_{out}$ 取反

注意：为了加快加法运算的速度，实际电路一定使用多级先行进位方式，上图仅为了说明标志信息的获取

算术逻辑单元

ALU 是一种功能较强的组合逻辑电路，它能进行多种算术运算和逻辑运算

由于加、减、乘、除运算最终都能归结为加法运算，因此 ALU 的核心是带标志加法器，同时也能执行与、或、非等逻辑运算

其中 A 和 B 是两个 n 位操作数输入端，$C_{in}$ 是进位输入端，ALUop 是操作控制端，用来决定 ALU 所执行的处理功能

如 ALUop 选择 Add 运算，ALU 就执行加法运算，输出的结果就是 A 加 B 之和；而且 ALUop 的位数决定了操作的种类

上图给出了能够完成 3 种运算的 ALU

• 与、或、加法（一位加法用一个全加器实现）
• 在 ALUop 的控制下，由一个多路选择器 MUX 选择输出 3 种操作结果之一
• 这里有 3 种操作，所以 ALUop 至少要有两位

补码加减运算部件

有两补码数相减 X - Y，转换成 X + (-Y) ，-Y 的补码是取反加一，那么就有 X - Y = X + ~Y + 1

无符号整数的二进制表示相当于正整数的补码表示，因此该思路同时也能实现无符号整数的加/减运算

下面根据思路来整出可实现补码加减运算的电路：

• 在原加法器的 Y 输入端加 n 个反向器以实现各位取反的功能
• 加一个 2 选 1 多路选择器，用一个控制端 Sub 来控制，以选择是将原码 Y 还是 $\bar{Y}$ 输入加法器
• 将控制端 Sub 同时作为低位进位送到加法器
• 控制端 Sub 为 1 时，做减法，实现 $X+\bar{Y}+1=[x{]}_{\mathrm{补}}+[-y{]}_{\mathrm{补}}$
• 控制端 Sub 为 0 时，做加法，实现 $X+Y=[x{]}_{\mathrm{补}}+[y{]}_{\mathrm{补}}$

可通过标志信息来区分带符号整数运算结果和无符号整数运算结果：

• 零标志 ZF = 1 表示结果为 0，不管是作为无符号数还是作为带符号整数来运算，ZF 都有意义

• 进/借位标志 CF 表示无符号数加/减运算时的进位/借位

  加法时，CF = 1 表示无符号数加法溢出，因此 CF 等于进位输出 $C_{out}$

  减法时，CF = 1 表示有借位，即不够减，故将进位输出 $C_{out}$ 取反来作为借位标志

  综合可得 $CF=Sub⨁C_{out}$，对于带符号整数运算，CF 没有意义

• 溢出标志 OF = 1 表示带符号整数运算时结果发生溢出，对于无符号整数运算，OF 没有意义

五、常见问题

1. 如何表示一个数值数据？计算机中的数值数据都是二进制数吗？

   1. 直接用二进制数表示，分为无符号数和有符号数，有符号数又分为定点数表示和浮点数表示
   2. 二进制编码的十进制数，一般都采用 8421 码（也称 NBCD 码）来表示，用来表示整数

   所以，计算机中的数值数据虽然都用二进制来编码表示，但不全是二进制数，也有用十进制数表示的

2. 长度为 n + 1 的定点数，按照不同的编码方式，表示的数值范围是多少？

   

3. 长度为 n + 1 的定点数，按照不同的编码方式，表示的数值范围是多少？