[科普中国]-机器运算

机器运算通过运算器来实现，运算器也是计算机进行算术运算和逻辑运算的主要部件，运算器的逻辑结构取决于机器的指令系统、数据表示方法和运算方法等。这里主要介绍数值数据在计算机中实现算术运算和逻辑运算的方法，以及运算部件的基本结构和工作原理1。

基本算术运算的实现加法器加法器是由全加器再配以其他必要的逻辑电路组成的。

1.全加器

基本的加法单元称为全加器，它要求三个输入量：操作数Ai和Bi、低位传来的进位Ci-1，并产生两个输出量：本位和Si、向高位的进位Ci。全加器的逻辑表达式为：
Si=Ai⊕Bi⊕Ci-1
Ci=AiBi+(Ai⊕Bi)Ci-1

2.串行加法器与并行加法器

在串行加法器中，只有一个全加器，数据逐位串行送入加法器进行运算。如果操作数长n位，加法就要分n次进行，每次只能产生一位和。

并行加法器由多个全加器组成，其位数的多少取决于机器的字长，数据的各位同时运算。并行加法器虽然操作数的各位是同时提供的，但低位运算所产生的进位有可能会影响高位的运算结果。例如：11…11和00…01相加，最低位产生的进位将逐位影响至最高位。因此，并行加法器的最长运算时间主要是由进位信号的传递时间决定的。提高并行加法器速度的关键是尽量加快进位产生和传递的速度1。

进位的产生和传递进位表达式：Ci=AiBi+(Ai⊕Bi)Ci-1

Gi的含义是：若本位的两个输入均为1，必然要向高位产生进位。
Pi的含义是：当两个输入中有一个为1，低位传来的进位Ci-1将超越本位向更高的位传送。
可得：Ci=Gi+PiCi-1

把n个全加器串接起来，就可进行两个n位数的相加。串行进位又称行波进位，每一级进位直接依赖于前一级的进位，即进位信号是逐级形成的。 串行进位链的总延迟时间与字长成正比。假定，将一级门的延迟时间定为ty，从上述公式中可看出，每形成一级进位的延迟时间为2ty。在字长为n位的情况下，若不考虑Gi、Pi的形成时间，从C0→Cn的最长延迟时间为2nty1。

定点加减运算原码加减运算对原码表示的两个数进行加减运算时，符号位不参与运算，仅仅是两数的绝对值参与运算。计算机的实际操作是加还是减，不仅取决于指令的操作码，还取决于两个操作数的符号，例如：加法时可能要做减法（两数异号）；减法时又可能做加法（两数异号），所以原码加减运算的实现是比较复杂的1。

补码加减运算1.补码加法
两个补码表示的数相加，符号位参加运算，且两数和的补码等于两数补码之和，即
[X+Y]补=[X]补+[Y]补
2.补码减法
根据补码加法公式可推出：
[X-Y]补=[X+(-Y)]补=[X]补+[-Y]补
已知[Y]补求[-Y]补的方法是：将[Y]补连同符号位一起求反，末尾加“1”。 [-Y]补被称为[Y]补的机器负数，由[Y]补求[-Y]补的过程称为对[Y]补变补（求补），表示为：
[-Y]补=[[Y]补]变补

注意将“某数的补码表示”与“变补”这两个概念区分开来。一个负数由原码表示转换成补码表示时，符号位是不变的，仅对数值位的各位变反，末尾加“1”。而变补则不论这个数的真值是正是负，一律连同符号位一起变反，末尾加“1”。[Y]补表示的真值如果是正数，则变补后[-Y]补所表示真值变为负数，反之亦然。

3.补码加减运算规则
补码加减运算规则如下：
(1)参加运算的两个操作数均用补码表示；
(2)符号位作为数的一部分参加运算；
(3)若做加法，则两数直接相加；若做减法，则将被减数与减数的机器负数相加；
(4)运算结果用补码表示。

4.符号扩展
在计算机算术运算中，有时必须将采用给定位数表示的数转换成具有更多位数的某种表示形式。例如某个程序需要将一个8位数与另外一个32位数相加。要想得到正确的结果，在将8位数与32位数相加之前，必须将8位数转换成32位数形式，这被称为“符号扩展”。
对于补码，符号扩展方法是：原有符号位保持不变，若为正数则所有附加位都用0进行填充，若为负数则所有附加位都用1进行填充。也可以理解为是用符号位来填充附加的高位1。

补码的溢出判断与检测方法1.溢出的产生
在补码加减运算中，有时会遇到这样的情况：两个正数相加，而结果的符号位却为1（结果为负）；两个负数相加，而结果的符号位却为0（结果为正）。

设参加运算的两数为X、Y，做加法运算。
若X、Y异号，不会溢出。
若X、Y同号，运算结果为正且大于所能表示的最大正数或运算结果为负且小于所能表示的最小负数（绝对值最大的负数）时，产生溢出。将两正数相加产生的溢出称为正溢；反之，两负数相加产生的溢出称为负溢。

2.溢出检测方法
设：被操作数为：[X]补=Xs,X1X2…Xn
操作数为：[Y]补=Ys,Y1Y2…Yn
其和（差）为：[S]补=Ss,S1S2…Sn
(1)采用一个符号位
两正数相加，结果为负表明产生正溢；两负数相加，结果为正表明产生负溢。因此可得出采用一个符号位检测溢出的方法：
当Xs=Ys=0，Ss=1时，产生正溢。
当Xs=Ys=1，Ss=0时，产生负溢。

(2)采用进位位
两数运算时，产生的进位为Cs,C1C2…Cn，其中：Cs为符号位产生的进位，C1为最高数值位产生的进位。
两正数相加，当最高有效位产生进位（C1=1）而符号位不产生进位（Cs=0）时，发生正溢。
两负数相加，当最高有效位没有进位（C1=0）而符号位产生进位（Cs=1）时，发生负溢。

(3)采用变形补码（双符号位补码）
在双符号位的情况下，把左边的符号位Ss1叫做真符，因为它代表了该数真正的符号，两个符号位都作为数的一部分参加运算。这种编码又称为变形补码。
双符号位的含义如下：
Ss1Ss2=00 结果为正数，无溢出；
Ss1Ss2=01 结果正溢；
Ss1Ss2=10 结果负溢；
Ss1Ss2=11 结果为负数，无溢出。

当两位符号位的值不一致时，表明产生溢出。溢出=Ss1⊕Ss21。

定点乘法运算原码一位乘法用原码实现乘法运算是十分方便的。原码一位乘法是从手算演变而来的，即用两个操作数的绝对值相乘，乘积的符号为两操作数符号的异或值（同号为正，异号为负）。

原码一位乘法的规则为：
(1)参加运算的操作数取其绝对值；
(2)令乘数的最低位为判断位，若为“1”，加被乘数，若为“0”，不加被乘数（加0）；
(3)累加后的部分积右移一位；
(4)重复n次(2)和(3)；
(5)符号位单独处理，同号为正，异号为负1。

补码一位乘法比较法－Booth乘法
设：被乘数[X]补=Xs.X1X2…Xn，乘数[Y]补=Ys.Y1Y2…Yn。
在乘数的最低位之后增加一位附加位Yn+1，它的初值为0，增加附加位不会影响运算结果。
每次运算取决于乘数相邻两位Yi、Yi+1的值，把它们称为乘法的判断位。根据校正法的统一表达式推出：由乘数相邻两位的比较结果（Yi+1-Yi）来确定运算操作。

Booth乘法规则如下：
(1)参加运算的数用补码表示；
(2)符号位参加运算；
(3)乘数最低位后面增加一位附加位Yn+1，其初值为0；
(4)由于每求一次部分积要右移一位，所以乘数的最低两位Yn、Yn+1的值决定了每次应执行的操作；

(5)移位按补码右移规则进行；
(6)共需做n+1次累加，n次移位，第n+1次不移位1。

补码两位乘法为了提高乘法的执行速度，可以选用两位乘法的方案。所谓两位乘法，就是每次处理乘数中的两位，从而使乘法的速度提高了一倍。两位乘法又可分为原码两位乘法和补码两位乘法，在此只讨论补码两位乘法。
根据前面介绍的Booth乘法方便地推导出补码两位乘法，即把补码两位乘理解为将Booth乘法的两次合并为一次来做。

补码两位乘法规则如下：
(1)参加运算的数用补码表示；
(2)符号位参加运算；
(3)乘数最低位后增加一位附加位Yn+1，初值为0；
(4)根据乘数的最低三位Yn-1YnYn+1的值决定每次应执行的操作；
(5)移位按补码右移规则进行1。

定点除法运算原码除法运算1.原码比较法和恢复余数法
(1) 比较法
比较法类似于手工运算，只是为了便于机器操作，将除数右移改为余数左移。
比较法要对两个操作数进行比较，这就需要设置比较线路，从而增加了硬件的代价。

(2)恢复余数法
恢复余数法是直接作减法试探方法，不管被除数（或余数）减除数是否够减，都一律先做减法。若余数为正，表示够减，该位商上“1”；若余数为负，表示不够减，该位商上“0”，并要恢复原来的被除数（或余数）。

由于余数的正、负是根据不同的操作数组合随机出现的，这就使得除法运算的实际操作次数不固定，从而导致控制电路比较复杂。而且在恢复余数时，要多作一次加法，降低了执行速度。因此，原码恢复余数法在计算机中一般很少采用。

2.原码不恢复余数法（原码加减交替法）
原码不恢复余数法是对恢复余数法的一种改进。在恢复余数法中，若第i-1次求商的余数为ri-1，则第i次求商操作为：ri=2ri-1-Y
若够减，ri=2ri-1-Y>0，商1。若不够减，ri=2ri-1-Y0，Y>0，X-Y>0

X0X+Y