第五章 计算机的运算方法

27 Mar 2022 8897字 30分
如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）

5.1 无符号数和有符号数

计算机中的数均放在寄存器中,通常称寄存器的位数为机器字长。所谓无符号数即没有符号的数,在寄存器中的每一位均可用来存放数值。当存放有符号数时,则需留出位置存放“符号”。

5.1.1 无符号数

寄存器的位数反映无符号数的表示范围

5.1.2 有符号数

对有符号数而言,符号的“正”、“负”机器是无法识别的,但由于“正”“负”恰好是两种截然不同的状态,如果用“0”表示“正”,用“1”表示“负”这样符号也被数字化了,并且规定将它放在有效数字的前面,这样就组成了有符号数。

一、机器数与真值

• 机器数:符号“数字化”的数
• 真值:带“+”或“-”符号的数

注：没有任何硬件表示小数点的位置，计算机中的小数点都以约定方式给出。小数定点器：小数点在符号位后面或整数定点器：小数点在数值位后面

二、原码

原码是机器数中最简单的一种表示形式,其符号位为0表示正数,符号位为1表示负数,数值位即真值的绝对值,故原码表示又称作带符号的绝对值表示。

为了书写方便以及区别整数和小数,约定整数的符号位与数值位之间用逗号“,”隔开;小数的符号位与数值位之间用小数点“.”隔开，计算机中没有。如上画四个数的原码分别是0.1011、1.1011、0,1100和1,1100。

• 整数的原码

• 小数的原码

三、补码

原码表示简单明了,并易于和真值转换。但用原码进行加减运算时，当两个数符号相同时做加法操作，当两个数符号不同时实际上做的是减法操作，比较麻烦。

那么能否在计算机中只设加法器,只作加法操作呢?如果能找到个与负数等价的正数来代替该负数,就可把减法操作用加法代替。而机器数采用补码时就能满足此要求。

• 正数的补码是它本身
• 负数的补码是符号位不变，每位取反再加1

以时钟为例，比如说当前在6点位置，我们想把时钟拨到3点位置，可以顺时针拨9个小时即+9，也可以逆时针拨3个小时即-3，因此在这里可以用(6+9)%12代替6-3，这就使用了加法代替了减法

由上图可知：

• 一个负数加上 “模” 即得该负数的补数-3+12=9
• 一个正数和一个负数互为补数时，它们绝对值之和即为模的大小|-3|+|9|=12

由此可以推出二进制的补码

仍然存在以下一个问题，一个负数的补码是一个正数，正数的补码是它本身，那么负数的补码和正数的补码就可能相等。 如下所示，-1011的补码是+0101，+0101的补码仍然是+0101

那么怎么区分得到的这个补码是正数的补码还是负数的补码呢？

模仿原码的表示方法，我们在正数的补码前加一个0，，如0,0101表示+0101的补码；在负数的补码前加一个1，，如1，0101表示-1011的补码

那么怎么实现在符号位部分给正数的补码添一个0，给负数的补码添一个1呢？

答案就是以$2^{n+1}$为模。例如，-1011+10000->0101,0101+10000->10101。此时n=4，以$2^{n+1}$为模则要再加一个$2^{n}$，1011+10000->0101,0101+10000->10101,0101+10000->10101。此时n=4，以$2^{n+1}$为模则要再加一个$2^{n}$，1011+10000->0101,0101+10000->10101,0101+10000->10101。此时n=4，以$2^{n+1}$为模则要再加一个$2^{n}$，1011+10000->0101,0101+10000->1,0101,0101+10000->10101,10101+10000->0,0101

然后给出补码的定义：

整数的补码：

小数的补码：

上面我们提到了负数的补码等于符号位不变，每位取反在加一，怎么来的呢？

以上是原码求补码，补码求原码也是符号位不变，每位取反在加一。

四、反码

• 正数反码是它本身
• 负数反码符号位不变，其余按位取反

整数的反码

小数的反码

五、移码

当真值用补码表示时,由于符号位和数值部分起编码,与习惯上的表示法不同,因此人们很难从补码的形式上直接判断其真值的大小

移码就是在真值上加一个常数$2^{n}$。在数轴上移码所表示的范围恰好对应与真值在数轴上的范围向轴的正方向移动2”个单元。

补码和移码的区别

• 补码中符号位0表示正数的补码，1表示负数的补码，移码中符号位1表示正数的移码，0表示负数的移码
• 一个数的补码和移码只有符号位不同，其余位完全相同，将符号位取反可完成移码和补码的相互转换

移码的特点

5.2 数的定点表示和浮点表示

5.2.1 定点表示

5.2.2 浮点表示

一、浮点数的表示形式

为了提高数据精度以及便于浮点数的比较,在计算机中规定浮点数的尾数用纯小数形式,故上例中$0.110101×2^{10}$和$0.00110101×2^{10}$形式是可以采用的。此外,将尾数最高位为1的浮点数称作规格化数,即$0.110101×2^{10}$为浮点数的规格化形式。浮点数表示成规格化形式后,其精度最高。

浮点数在在计算机中的表示

二、浮点数的取值范围

三、浮点数的规格化形式

四、浮点数的规格化

• 浮点数的规格化

• 零的表示

• IEEE 754 标准

5.3 定点运算

5.3.1 移位运算

移位运算又叫移位操作,对计算机来说,有很大的实用价值。例如,当某计算机没有乘(除)法运算线路时,可以采用移位和加法相结合,实现乘(除)运算。

移位：小数点不动，数据相对于小数点移动几位。在计算机中，移位与加减配合，能够实现乘除运算。

一、算术移位

算术移位：对有符号数的移位。符号位保持不变，对移位产生的空位填0或填1

所有的反码、补码结果转换成原码后都应和原来的原码移位结果相同。

• 正数的移位
  • 正数的原码、反码、补码相同，所以其中的0和1意义相同，所以对于正数的反码或补码移位产生的空位都应填0
• 负数的移位
  • 对于原码来说，无论左移或右移都应对空位填0。
  • 对于反码来说，除符号位反码的每位都与原码相反，在反码中0对应原码的1，1对应原码的0，所以对反码的移位空位应填1。
  • 对于补码来说分为左移和右移。将补码分为两个部分，左移填0，右移填1。

二、逻辑移位

逻辑移位：无符号移位

• 逻辑左移：低位添0，高位丢掉
• 逻辑右移：高位添0，低位丢掉

5.3.2 加减法运算

一、补码加法运算公式

(1) 加法

\[\begin{split}整数\quad [A]\_{补} + [B]\_{补} = [A+B]\_{补}(mod\enspace2^{n+1})\\ 小数\quad [A]\_{补} + [B]\_{补} = [A+B]\_{补}(mod\enspace2) \end{split}\]

(2) 减法 \(\begin{split} 整数\quad \[A-B]_\{补} = \[A+(-B)]\_{补} = [A]\_{补} + [-B]\_{补}(mod\enspace2^{n+1})\\ 小数\quad [A-B]\_{补} = [A+(-B)]\_{补} = [A]\_{补} + [-B]\_{补}(mod\enspace2) \end{split}\)

连同符号位一起相加，符号位产生的进位自然丢掉

二、溢出判断

溢出：运算的结果超出了机器字长所能表示的范围。由于减法运算在机器中是用加法器实现的,因此可得出如下结论:不论是作加法还是减法,只要实际参加操作的两个数(减法时即为被减数和“求补以后的减数)符号相同,结果又与原操作数的符号不同,即为溢出。

• 对于加法,只有在正数加正数和负数加负数两种情况下才可能出现溢出,符号不同的两个数相加是不会出现溢出的。
• 对于减法,只有在正数减负数或负数减正数两种情况下才可能出现溢出,符号相同的两个数相减是不会出现溢出的。

(1) 用一位符号位判断

计算机中采用一位符号位判断时,为了节省时间,通常用符号位产生的进位与最高有效位产生的进位异或操作后,按其结果进行判断。若异或结果为1,即为溢出;异或结果为0,则无溢出。

(2) 用两位符号位判断

用两位符号位判断采用两位符号位的补码，即变形补码,以4为模

在用变形补码作加法时,两位符号位要连同数值部分一起参加运算,而且高位符号位产生的进位自动丢失,便可得正确结果。即

\(\begin{split} [A]\_{补} + [B]\_{补} = [A+B]\_{补}(mod\enspace4)\\ \[A-B]_\{补} = \[A+(-B)]\_{补} = [A]\_{补} + [-B]\_{补}(mod\enspace 4)\) \end{split}$$

变形补码判断溢出的原则是:当两位符号位不同时,表示溢出,否则无溢出。不论是否发生溢出,高位(第一位)符号位水远代表真正的符号。

(3)补码定点加减法的硬件配置

图中寄存器A、X、加法器的位数相等,其中A存放被加数(或被减数的补码,Ⅹ存放加数(或减数)的补码。当作减法时,由“求补控制逻辑”将送全加法器,并使加法器的最末位外来进位为1,以达到对减数求补的目的运算结果溢出时,通过溢出判断电路置“1”溢出标记V。$G_{A}$为加法标记,$G_{S}$为减法标记。

5.3.3 乘法运算

一、笔算乘法分析

笔算中符号单独运算，计算机中可以用一个异或电路实现。除去符号位的乘法运算可以改写成被乘数的加法运算和移位运算。当乘数的末尾为1时，结果与被乘数做一次加法运算，当乘数末尾为0时，结果与0做一次加法运算，乘数右移移位，直到乘数为0。

①乘法运算可用移位和加法来实现,当两个四位数相乘,总共需做四次加法和四次移位。
②由乘数的末位值确定被乘数是否与原部分积相加,然后右移一位,形成新的部分积;同时,乘数也右移一位,由次低位作新的末位,空出最高位放部分积的最低位。
③每次做加法时,被乘数仅仅与原部分积的高位相加,其低位被移至乘数所空出的高位位置。

用一个寄存器存放被乘数,一个寄存器存放乘积的高位,另一个寄存器存放乘数及乘积的低位,再配上加法器及其他相应电路,就可组成乘法器。又因加法只在部分积的高位进行,故不但节省了器材,而且还缩短了运算时间。

二、原码乘法

原码乘去掉符号位运算即为无符号数乘法
整数乘法与小数乘法过程完全相同

• 原码乘法规则

• 原码乘法递推

• 原码乘法例子

• 原码一位乘的硬件配置

图中A、X、Q均为n+1位的寄存器,其中X存放被乘数的原码,Q存放乘数的原码。移位和加控制电路受末位乘数$Q_{n}$的控制(当$Q_{n}=1$时,A和x内容相加后,A、Q右移一位;当$Q_{n}=0$时,只作A、Q右移一位的操作)。计数器C用于控制逐位相乘的次数。S存放乘积的符号。$G_{M}$为乘法标记。

乘法运算前,A寄存器被清零,作为初始部分积,被乘数原码在X中乘数原码在Q中,计数器C中存放乘数的位数n。乘法开始后,首先通过异或运算,求出乘积的符号并存于S,接着将被乘数和乘数从原码形式变为绝对值。然后根据$Q_{n}$的状态决定部分积是否加上被乘数,再逻辑右移位,重复n次,即得运算结果。

三、补码乘法

补码乘法中的加法和移位均按补码规则运算，即算术移位

• 以小数补码乘法为例，整数补码乘法相同

\[\begin{align} ① y_{0}=0时， \[x·y]_{补} &=\[x]_{补}·\[x]_{补}\\ &=\[x]_{补}·{0.y_{1}...y_{n}}\\ ② y_{0}=1时，\[x·y]_{补} &=\[x]_{补}·{0.y_{1}...y_{n}}+\[-x]_{补}\\ &=\[x]_{补}·{0.y_{1}...y_{n}}-\[x]_{补} \end{align}\]

为方便计算机处理，通过公式变换可以将以上两种情况统一起来

\[\begin{align} \[x·y]_{补} &=\[x]_{补}·{0.y_{1}...y_{n}}\\ &=\[x]_{补}·{0.y_{1}...y_{n}} + 0 \\ &=\[x]_{补}·{0.y_{1}...y_{n}} + y_{0}·\[-x]_{补}\\ &=\[x]_{补}·{0.y_{1}...y_{n}} - y_{0}·\[x]_{补} \end{align}\]

• Booth算法（被乘数、乘数符号任意）

• 补码乘法例子

• Booth算法硬件配置

图中A、X、Q均为n+2（添加了个附加位）位寄存器,其中X存放被乘数的补码(含两位符号位),Q存放乘数的补码(含最高一位符号位和最末一位附加位),移位和加控制逻辑受Q寄存器末2位乘数控制。当其为01时,A、X内容相加后AQ右移一位;当其为10时,A、X内容相减后A、Q右移一位。计数器C用于控制逐位相乘的次数,$G_{M}$为乘法标记

5.3.4 除法运算

一、笔算除法分析

• 笔算除法分析

• 笔算除法和机器除法的比较

二、原码除法

• 约定

• 恢复余数法

在恢复余数法中，先做减法操作，通过减法操作的结果正负判断商0还是商1，商1时结果正确继续向下操作，但是商0时余数应该减0，但是我们提前使用余数减去了除数，所以应该恢复余数。

• 加减交替法

加减交替法是对恢复余数法的改进。加减交替法将恢复余数法中上商为0时恢复余数的操作与下一步操作和二为一，从而取消了恢复余数操作。当上商为1时，下一步操作余数左移一位后减去除数的绝对值。上商为0时，下一步操作余数左移一位后加上除数的绝对值

• 原码加减交替除法硬件配置

图中A、X、Q均为n+1位寄存器,其中A存放被除数的原码,X存放除数的原码。移位和加控制逻辑受Q的末位$Q_{n}$控制。($Q_{n}=1$作减法,$Q_{n}=0$作加法),计数器C用于控制逐位相除的次数n,$G_{D}$为除法标记,V为溢出标记S为商符。

三、补码除法

待补充…

5.4 浮点四则运算

5.4.1加减运算

设两个浮点数

\[\begin{align} x & = S_{x} \cdot 2^{j_{x}} \\ y & = S_{y} \cdot 2^{j_{y}} \end{align}\]

由于浮点数尾数的小数点均固定在第一数值位前,所以尾数的加减运算规则与定点数完全相同。但由于其阶码的大小又直接反映尾数有效值的小数点位置,因此当两浮点数阶码不等时,因两尾数小数点的实际位置不一样,尾数部分无法直接进行加减运算。因此,浮点数加减运算必须按以下几步进行：

①对阶,使两数的阶码相同
②尾数求和,将对阶后的两尾数技定点加减运算规则求和(差)
③规格化,为增加冇效数字的位数,提高运算精度,必须将求和(差)后的尾数规格化
④舍入,为提高精度,要考虑尾数右移时丢失的数值位。
⑤判断结果,即判断结果是否溢出。

一、对阶

对阶的目的是使两操作数的小数点位置对齐,即使两数的阶码相等。为此,首先要求出阶差,再按小阶向大阶看齐的原则,使阶小的尾数向右移位（采用左移时可能会使数据丢失）,每右移一位,阶码加1,直到两数的阶码相等为止。右移的次数正好等于阶差。尾数右移时可能会发生数码丢失,影响精度。

二、尾数求和

对阶之后阶码相同，运算只需要对尾数按照定点数运算规则运算即可

三、规格化

将尾数求和后的结果通过左规或右规进行浮点数规格化操作，使其符合浮点数规格化形式

左规:尾数左移一位，阶码减 1，直到数符和第一数位不同为止
右规:当 尾数溢出（>1）时，需右规,即尾数出现01.××…×或 10.××…×时尾数右移一位，阶码加1

四、舍入

在对阶和右规过程中，可能出现尾数末位丢失引起误差，需考虑舍入

（1）0舍1入法

“0舍1入”法类似于士进制运算中的“四舍五入”法,即在尾数右移时被移去的最高数值位为0,则舍去:被移去的最高数值位为1,则在尾数的末位加1。这样做可能使尾数又溢出,此时需再做一次右规。

（2）恒置“1”法

尾数右移时,不论丢掉的最高数值位是“1”或“0”,都使右移后的尾数末位恒置“1”。这种方法同样有使尾数变大和变小的两种可能

五、溢出判断

与定点加减法一样,浮点加减运算最后一步也需判溢出。在浮点规格化中已指出,当尾数之和(差)出现01.××…×或10.××…×时,并不表示溢出,只有将此数右规后,再根据阶码来判断浮点运算结果是否溢出

设机器数为补码，尾数为规格化形式，并假设阶符取2位，阶码的数值部分取7位，数符取2 位，尾数取n位，则该补码在数轴上的表示为

5.4.2 乘除运算

待补充…

5.5 算术逻辑单元

5.5.1 ALU电路

ALU框图：

图中$A_{i}$和$B_{i}$为输入变量;$k_{i}$为控制信号,$k_{i}$的不同取值可决定该电路作哪一种算术运算或哪一种逻辑运算;$F_{i}$是输出函数。

5.5.2 快速进位链

一、并行加法器

并行加法器由若干个全加器组成。n+1个全加器级联,就组成了一个n+1位的并行加法器。

$C_{i}$是$A_{i}$、$B_{i}$、$C_{i-1}$相加产生的进位；$S_{i}$是两个输$A_{i}$、$B_{i}$、$C_{i-1}$相加的和。 记$d_{i}=A_{i}B_{i}$，$d_{i}为本地进位，与低位无关；$(A_{i}+B_{i})C_{i-1}$为传递进位，与低位有关，称$t_{i}=A_{i}+B_{i}$为传递条件。 则$C_{i}=d_{i}+t_{i} C_{i-1}$。

由$C_{i}$的组成可以将逐级传递进位的结构,转换为以进位链的力式实现快速进位。目前进位链通常采用串行和并行两种。

二、串行进位链

串行进位链是指并行加法器中的进位信号采用串行传递 进位链：传送进位的电路

以4位全加器为例，每一位的进位表达式为：

\[\begin{array}{l} C_{0}=d_{0}+t_{0} C_{-1}=\overline{\overline{d_{0}} \cdot \overline{t_{0} C_{-1}}} \\ C_{1}=d_{1}+t_{1} C_{0} \\ C_{2}=d_{2}+t_{2} C_{1} \\ C_{3}=d_{3}+t_{3} C_{2} \end{array}\]

进位链可以由多个与非电路完成

若设与非门的级延迟时间为$t_{y}$,那么当$d_{i}$、$t_{i}$形成后,共需$8t_{y}$便可产生最高位的进位。实际上每增加一位全加器,进位时间就会增加$2t_{y}$,n位全加器的最长进位时间为$2nt_{y}$。

三、并行进位链

并行进位链是指并行加法器中的进位信号是同时产生的,又称先行进位、跳跃进位等。

以四位加法器为例

\[\begin{array}{l} C_{0}=d_{0}+t_{0} C_{-1} \\ C_{1}=d_{1}+t_{1} C_{0}=d_{1}+t_{1} d_{0}+t_{1} t_{0} C_{-1} \\ C_{2}=d_{2}+t_{2} C_{1}=d_{2}+t_{2} d_{1}+t_{2} t_{1} d_{0}+t_{2} t_{1} t_{0} C_{-1} \\ C_{3}=d_{3}+t_{3} C_{2}=d_{3}+t_{3} d_{2}+t_{3} t_{2} d_{1}+t_{3} t_{2} t_{1} d_{0}+t_{3} t_{2} t_{1} t_{0} C_{-1} \end{array}\]

设与或非门的延迟时间为$1.5t_{y}$,与非门的级延迟时间仍为$1t_{y}$,则$d_{i}$、$t_{i}$形成后,只需$2.5t_{y}$就可产生全部进位。

理想的并行进位链是n位全加器的n位进位同时产生,但实际实现有困难。通常并行进位链有单重分组和双重分组两种实现方案。

（1）单重分组跳跃进位链

单重分组跳跃进位链中n位全加器分若干小组，小组中的进位同时产生， 小组与小组之间采用串行进位。

以16位全加器为例

当$d_{i}$、$t_{i}$ 形成后,经$2.5t_{y}$产生$C_{3}~C_{0}$,经$5t_{y}$产生$C_{7}~C_{4}$,经$7.5t_{y}$产生$C_{11}~C_{8}$,经$10t_{y}$产生$C_{15}~C_{12}$

（2）双重分组跳跃进位链

双重分组跳跃进位链中n位全加器分若干大组，大组中又包含若干 小组。每个大组中小组的最高位进位同时产生。 大组与大组之间采用串行进位。

以32位全加器为例

以第 8 小组为例

\[C_{3}=d_{3}+t_{3} C_{2}=d_{3}+t_{3} d_{2}+t_{3} t_{2} d_{1}+t_{3} t_{2} t_{1} d_{0}+t_{3} t_{2} t_{1} t_{0} C_{-1}\]

令

\[\begin{array}{c} D_{8}=d_{3}+t_{3} d_{2}+t_{3} t_{2} d_{1}+t_{3} t_{2} t_{1} d_{0}\\ T_{8}=t_{3} t_{2} t_{1} t_{0} \end{array}\]

则

\[C_{3}=D_{8}+T_{8}C_{-1}\]

$D_{8}$是小组的本地进位，与外来进位无关；$T_{8}$是小组的传送条件，与外来进位无关，传递外来进位。

同理

\[\begin{array}{c} 第 7 小组 C_{7}=D_{7}+T_{7} C_{3} \\ 第 6 小组 C_{11}=D_{6}+T_{6} C_{7} \\ 第 5 小组 C_{15}=D_{5}+T_{5} C_{11} \end{array}\]

进一步展开得

\[\begin{array}{l} C_{3}=D_{8}+T_{8} C_{-1} \\ C_{7}=D_{7}+T_{7} C_{3}=D_{7}+T_{7} D_{8}+T_{7} T_{8} C_{-1} \\ C_{11}=D_{6}+T_{6} C_{7}=D_{6}+T_{6} D_{7}+T_{6} T_{7} D_{8}+T_{6} T_{7} T_{8} C_{-1} \\ C_{15}=D_{5}+T_{5} C_{11}=D_{5}+T_{5} D_{6}+T_{5} T_{6} D_{7}+T_{5} T_{6} T_{7} D_{8}+T_{5} T_{6} T_{7} T_{8} C_{-1} \end{array}\]

以第二大组为例

以第8小组为例只产生低3位的进位和本小组的$D_{8}$、$T_{8}$

32位双重分组跳跃进位链