运算方法和运算部件

Chapter 3: Arithmetic Methods and Components

高级语言与机器语言涉及的运算及ALU

高级语言程序中涉及的运算(以C语言为例)

在C语言中除了基本的加、减、乘、除运算之外，还有以下几类运算:

• 按位运算:

  • 用途: 对位串实现"掩码"(mask)操作或相应的其他处理
  • 操作: 按位与: &
             按位或: |
             按位取反: ~
             按位异或: ^

• 逻辑运算:

  • 用途: 用于关系表达式的运算
  • 操作: 逻辑与: &&
             逻辑或: ||
             逻辑非: !

• 移位运算:

  • 用途: 提取部分信息
             扩大或缩小数值的2、4、8$\cdots 2^n$倍
  • 操作: 左移: x<<k; 右移: x>>k;
             不区分是逻辑移位还是算术移位，由x的类型确定。
    1. x为无符号数: 逻辑左移时，高位移出，低位补0，当移出位为1时发生了溢出。算术左移时，低位移出，高位补0，当移出位为1时发生了有效数据丢失。
    2. x为带符号数: 逻辑左移时，高位移出，低位补0，当移出位为1时发生了溢出。算术左移时，低位移出，高位补符号位，当移出位为1时发生了有效数据丢失。

• 位扩展和位截断运算:

  • 用途: 完成不同类型数据间转换时可能会出现的数据扩展或截断操作
  • 操作: 高级语言没有提供运算符，而是在编译器层面解决
  • 扩展:
    1. 无符号数: 无符号数采用0扩展的方式进行扩展
    2. 带符号数: 带符号数采用符号位扩展的方式进行扩展
  • 截断: 强行将高位丢弃，故可能发生"溢出"
    说明: 截断后再扩展可能造成数据的错误。

  int i = 32768; // i = 00 00 80 00
  short si = (short)i; // si = 80 00
  int ii = (int)si; // ii = FF FF 80 00 = -32768

指令集中涉及到的运算(以MIPS为例)

本节会介绍需要掌握含义和用法的MIPS指令集，在后面指令系统中也会用到这里的指令，因此需要记忆大部分指令的含义。

基本运算部件ALU的设计

加法器(串行、并行)

• 串行加法器: 由多个全加器串行连接而成。
  
  全加器的A和B均为1位bit的输入，sum为1位bit的输出，CarryIn为上一个全加器的进位，而CarryOut为本位的进位。
  
  C0为0，Cn为溢出被截断了。
  串行加法器的缺点: 进位按串行方式传递，速度慢！例如: n位串行加法器从C0到Cn的延迟时间为2n级门延迟！最后一位和数的延迟时间为2n+1级门延迟！
  (假设与/或门的延迟时间为1级门延迟，异或门的延迟时间为3级门延迟)

• 并行加法器: 串行进位加法器采用串行逐级传递进位，电路延迟与位数成正比关系。因此，现代计算机采用一种先行进位(Carry look ahead)方式。因此并行加法器比串行加法器快的原因即是串行加法器的进位需要逐级传达而并行加法器的进位之间不等待，相互独立并同时产生。

  1. 全先行进位加法器:
     
     全先行进位加法器是将所有输入同时传输到进位生成部件中，再通过进位生成结果与输入数据在求和部件中计算得到结果。
  2. 局部先行进位加法器
     
     局部先行进位加法器则是采用了串行和并行两种方式的结合，将输入分为多个不同的部分，同时将这些部分分别传输到进位生成部件，然后将这些全先行进位加法器进行串联行成一个大的局部先行进位加法器。
  3. 多级先行进位加法器
     
     多级先行进位加法器是局部先行加法器的更高级形式，多级先行进位加法器采用的是组内并行但组间是串行的形式，而多级先行进位加法器是实现了不同组之间的并行进位(实现方法是BCLA部件即多引入一组新的传递函数可以直接进行不同组的并行进位)。

ALU的功能说明

• A、B为n位的输入，C为n位的输出
• ALUop为ALU的控制信号，用来说明本次计算的类型(&,|,+,-等)
• Zero为计算结果是否为0的标志，如果结果为0，则Zero为1，否则为0
• CarryOut为进位或者借位信号，如果有进位或借位发生则为1
• Overflow为溢出标志，如果溢出则为1

这里只是ALU功能的示意图，并非真实的ALU结构图。
这是1位基本ALU的逻辑电路图:

MUX为多路选择器。

定点数运算及其运算部件

补码加/减运算及其运算部件

首先由数据的机器级表示章我们可以知道，定点数在现代计算机中的表示方法均为补码。对于加减运算由于补码的特性我们可以知道:

$[A+B]_{补}=[A]_{补}+[B]_{补}$

$[A-B]_{补}=[A]_{补}+[-B]_{补}$

由上面等式可以知道，ALU只需要实现补码的加法功能和求补(求出$[-B]_{补}$称为求补)功能即可完成定点数的加减运算。而求补功能其实是比较好实现的，其公式如下:

$[-B]_{补}=\overline{[B]}_{补}+1$

在求补运算中的取反是对补码的所有位进行的(包括符号位)。

• Sub: 减法信号位，当为1时表示减法，当为0时表示加法，在MUX的作用下会影响B输入到加法器的值
• Cin: 前一加法器的进位或借位信息
• Cout: 为本位加法器的进位或借位信息
• 溢出标志OF(Overflow Flag): $OF=C_n\oplus C_{n-1}$($C_n$为符号位进位, $C_{n-1}$为最高数值位进位)
• 符号位标志SF(Sign Flag): $SF=F_{n-1}$(即最高位MSB)
• 零标志ZF(Zero Flag): ZF=1当且仅当Sum=0
• 进位/借位标志CF(Carry Flag): $CF=Cout\oplus Sub$或$CF=Cout\oplus Cin$

条件标志位(OF、SF、ZF、CF)的产生公式需要掌握!并且条件标志会保存到寄存器中。

原码加/减运算

原码加/减运算是浮点数运算的基础之一，因为浮点数的尾数由原码表示，在进行浮点数运算时一定会涉及到原码的加减运算。
原码加/减运算思路为将符号位和数值部分分开处理，对数值部分进行加减运算，符号位起判断和控制作用。

1. 比较两数符号，对加法执行"同号求和，异号求差"，对减法执行"异号求和，同号求差"。
2. 求和：数值位相加，和的符号取被加数(或被减数)的符号。若最高位产生进位，则结果溢出。
3. 求差：加数(或减数)求补后与被加数(被减数)相加。
4. 1. 最高位产生进位(Cout=1)则无借位(CF=0)，表示够减结果为正，该结果即为“差”的数值位的原码。
   2. 最高位无进位(Cout=0)则CF=1，结果为负，它是“差”的数值位的补码形式，需对结果求补，还原为原码形式的数值位。
   3. 差的符号位：对于a)情况，符号位取被加数（被减数）的符号； 对于b)情况，符号位为被加数（被减数）的符号取反。

移码加/减运算

移码同样是浮点数运算的基础之一，因为浮点数的阶码由移码表示，在进行浮点数运算时一定会涉及到移码的加减运算。
但是移码加/减运算符号位和数值部分可以一起处理。

$[E1]_{移}+[E2]_{移}=[E1+E2]_{补}$

$[E1]_{移}-[E2]_{移}=[E1-E2]_{补}$

**移码的和/差等于和/差的补码！**再根据标准移码和补码的关系可以得到结果的移码: 将符号位取反，其余位不变。
运算规则:

1. 加法：直接将$[E1]_移$和$[E2]_移$进行模$2^n$加，然后对结果的符号取反。
2. 减法: 先将减数$[E2]_移$求补(各位取反，末位加1)，然后再与被减数$[E1]_移$进行模$2^n$相加，最后对结果的符号取反。
3. 溢出判断：进行模$2^n$相加时，如果两个加数的符号相同，并且与和数的符号也相同，则发生溢出。(因为和是补码，加数是移码)

乘法运算及其运算部件

无符号数乘法

设: $[X]_{原}=x_0.x_1\cdots x_n,\ [Y]_{原}=y_0.y_1\cdots y_n$求$[X\times Y]_{原}$
观察人手算乘法过程:

发现在整个运算过程中一直重复加法运算和移位运算两种运算，因此在计算机中可以通过ALU和移位器来实现乘法运算。
无符号数乘法的机器实现基本步骤:

1. 每次得$X\times y_i$后，与前面所得结果累加，得到$P_i$称之为部分积。
2. 每次得$X\times y_i$后，不是左移与前次部分积Pi相加，而是将部分积$P_i$右移后与$X\times y_i$相加。
3. 对乘数中为"1"的位执行加法和右移，对为"0"的位只执行右移，而不执行加法运算。

乘法运算硬件实现

32位$\times$32位=64位，因此结果需要64位寄存器来保存。而结果在乘法开始时乘数可以利用结果暂时未产生的空间来存储，因此结果的低32位作为乘数寄存器。当运算开始后，没计算出一位结果就需要右移一位，同时乘数寄存器也需要右移一位，但此时丢失的数据已经在本次运算中被保存了。

原码乘法算法和MIPS中的乘除法运算处理

原码乘法算法

用于浮点数尾数乘法运算，符号与数值分开处理: 积符由异或得到，数值用无符号乘法运算。
例: $[x]_{原}=01110, [y]_{原}=11101$
符号位: $0 \oplus 1 = 1, 1110\times 1101=100110110$，因此$[x\times y]_{原}=1100110110$

MIPS中的乘除法运算处理

指令: mult, multu, div, divu。MIPS中有一对32位寄存器Hi与Lo，Hi与Lo结合起来实现64位运算器。

• 乘法: Hi中存放高32位积，Lo中存放低32位积(与上面图硬件实现相同)。
• 除法: Hi中存放余数，Lo中存放商

mflo/mfhi指令用来把Lo/Hi中的32位数据取到通用寄存器，两种乘法指令都忽略overflow, 而由软件自行处理溢出，并且不检测除数为零的异常。

定点运算器

所有运算都可通过"加"和"移位"操作实现，以一个或多个ALU(或加法器)为核心，加上移位器和存放中间临时结果的若干寄存器，在相应控制逻辑的控制下，可以实现各种运算。
运算部件通常指ALU、移位器、寄存器组，加上用于数据选择的多路选择器和实现数据传送的总线等构成的一个运算数据通路。

浮点数运算及其运算部件

首先直接给出浮点数运算的通用公式:
设: $x=M_x\cdot 2^{E_x}, y=M_y\cdot 2^{E_y}$
则:

$x \pm y = (M_x+M_y\cdot 2^{E_x-E_y}) \cdot 2^{E_x}$

$x\times y = (M_x+M_y)\cdot 2^{E_x+E_y}$

$x \div y = (M_x\div M_y)\cdot 2^{E_x-E_y}$

可能会出现的异常:

• 阶码上溢: 一个正指数超过了最大允许值 => +∞/-∞/溢出
• 阶码下溢: 一个负指数超过了最大允许值 => +0/-0
• 尾数溢出: 最高有效位有进位 =>右规 => 阶码增加
• 非规格化尾数: 数值部分高位为0 => 左规 => 阶码减少
• 右规或对阶时: 右段有效位丢失 => 尾数舍入 => 运算过程添加附加位(暂时保留右规移出的位，参加中间过程的计算最后再舍去)

浮点数加减运算

1. 通过计算$[\Delta E]_{补}$来判断两数的阶差，对于标准移码(对IEEE754移码同样成立)有$[\Delta E]_{补}=[E_x-E_y]_{补}=[E_x]_{移}-[E_Y]_{移}=[E_x]+[-[E_y]_{移}]_{补}$(但当溢出时无法通过$\Delta E$来判断阶差)
2. 对阶: 使得两数阶码相等(原则上为小阶向大阶看齐): 阶小的那个数的尾数右移，右移位数等于两个阶码差的绝对值(对单精度浮点数来说，当$\Delta E$大于24时结果直接等于大阶的数，因为尾数仅有23位，右移24位尾数为0)
3. 尾数加减，并且尾数的附加位需要参加运算
4. 将结果规格化，即尾数高位为0，则需左规;尾数最高位有进位，需右规(阶码溢出异常处理：阶码上溢，则结果溢出;阶码下溢，则结果为0)
5. 如果尾数比规定位数长，则需考虑舍入
   • 就近舍入: 舍入为最近可表示的数(即最靠近LSB位为1则进，为0则舍，若为中间值: 如100则取决于LSB，若LSB为0则舍，为1则进)
   • 朝+∞方向舍入: 舍入为右边最近可表示数(正向舍入)
   • 朝-∞方向舍入: 舍入为左边最近可表示数 (负向舍入)
   • 朝0方向舍入: 直接截取所需位，后面的位丢弃(丢弃全部附加位)
6. 若运算结果尾数是0，则需要将阶码也置0(尾数和阶码均为0时表示0，见数据的机器级表示)。

浮点数乘除运算

1. 求阶: $E_x \pm E_y \mp 127$
2. 尾数相乘除: $M_x \times M_y$或$M_x \div M_y$
3. 两数符号相同，结果为正；两数符号相异，结果为负
4. 尾数高位为0，需左规；当尾数最高位有进位，需右规
5. 如果尾数比规定的长，则需考虑舍入(与加减法舍入相同)
6. 若尾数是0，则需要将阶码也置0。
7. 阶码溢出判断

浮点数运算的精度问题

其实在上面的浮点数加减法运算和乘除法运算时可以发现，可能会出现阶码上溢、阶码下溢、尾数溢出等等溢出问题，因此浮点数运算始终存在一个精度的问题，即便是没有发生溢出的情况下也有其他的问题，如在Java语言中就会存在一个很经典的问题0.1 + 0.2 = 0.30000000000000004。因此很多bug其实就是出现在对计算机内部浮点数的实现理解不深，这里很值得思考。