计算机组成原理(三) —— 补码的定点数运算规则

这篇的话主要算是上一篇浮点数的前传吧，补充一下补码的定点数运算规则(加减乘除)，然后会在上一篇浮点数里加一些例子

文章目录

定点数表示
定点数加法
定点数减法
溢出判断
- 单符号位法
- 双符号位法
定点数乘法
定点数除法
- 恢复余数法
- 加减交替法
参考资料

定点数表示

定点数表示小数算是很直观地一种表示形式吧，类比于十进制表示的小数 $d_md_{m-1}...d_1d_0.d_{-1}d_{-2}...d_{-n}$ ，这里 $d_i$ 的取值范围是 0~9，那么二进制相似的表示 $b_mb_{m-1}...b_1b_0.b_{-1}b_{-2}...b_{-n-1}b_{-n}$ 就是定点数表示法了，这里 $b_i$ 的取值范围是 0 和 1。
那么小数点左边的位的权就是 2 的正幂，而右边的位的权是 2 的负幂。例如， $101.11_2$ 表示数字 $\times 2^2 +0 \times 2^1 + 1 \times 2^0 + 1 \times 2 ^ {-1} + 1 \times 2^{-2}=4+0+1+\frac{1}{2}+\frac{1}{4}=5\frac{3}{4}$ 。
我们知道在有限长度的编码下，十进制表示法不能准确地表达像 $\frac{1}{3}$ 和 $\frac{5}{7}$ 这样的数。类似，小数的二进制表示法只能表示那些能够被写成 $\times 2^y$ 。其他的值只能够被近似地表示，例如，数字 $\frac{1}{5}$ 可以用十进制小数 $0.20$ 精确表示，但是，我们不能把它准确地用二进制小数来表示，只能近似地表示它。
当然，增加二进制表示的长度可以提高表示的精度：

上面讨论的情况因为是正数，所以其原码形式可以看作是和补码形式是一致的，那么对于负数，其实和非小数的补码表示也是一致的，我们在前面加上符号位(0 表示正数，1 表示负数)，后面的位就是原码取反+1。

定点数加法

首先给定两个规则：

规则 1： $和]_{补}=[加数]_{补}+[加数]_{补}$
规则 2： $y]_{补}=[y]_{补}整体取反再+1$

那么对于规则 1，我们可以引申出如下的扩展规则：

$x+y]_{补} = [x]_{补} + [y]_{补}$
$x-y]_{补} = [x]_{补} + [-y]_{补}$
$x+y]_{补} = [-x]_{补} + [y]_{补}$
$x-y]_{补} = [-x]_{补}+[-y]_{补}$

对于规则 2，这里整体取反是包括符号位(毕竟加了个负号，符号位肯定要改变呀)，举一个例子： $Y]_{补} = 0, 1 1 0 0 0 1 0 B$ $Y]_{补}=1, 0 0 1 1 1 1 0 B$

从一个例子入手，已知 X、Y 为两个带符号定点整数，它们的原码为 $X]_{原}=0, 0011001B$ ， $Y]_{原}=1, 0000100B$ ，求 $X+Y]_原$

首先从原码得到X、Y各自的补码 $X]_{补}=0, 0011001B$ ， $Y]_{补}=1, 1111100B$
那么得到补码之后就可以直接相加， $X+Y]_{补}=(1)0, 0010101B$ ，括号里的 1 是符号位的进位，舍去即可
符号位是 0，说明是正数，那么其原码就和补码是一样的， $X+Y]_{原}=0, 0010101B$

定点数减法

从上面定点数加法的规则 1 的扩展规则中，我们知道 $x-y]_补=[x]_补+[-y]_补$ ，那么实际就是把减法转化为加法去做。

还是举一个例子：
已知 $X]_补=0, 1110111B$ ， $Y]_补=0, 1100100B$ ，求 $X-Y]_补$

首先求出 $Y]_补 = 1，0011100B$
将 $X]_补$ 和 $Y]_补$ 相加，得到 $X-Y]_补 = 0, 0010011$

溢出判断

单符号位法

看完简单的定点整数补码加法和减法，我们看下面这个例子：
$X]_补 = 1, 0011100$ ， $Y]_补=1, 0001100$ ，求 $X+Y]_补$

按照之前的计算规则，这里我们得到 $X+Y]_补=0, 010100$ ，问题很明显，两个负数相加结果得到一个正数，这里就是发生了溢出，如果是两个负数相加最终得到个正数，就是负溢出，如果是两个正数相加最终得到个负数，就是正溢出。

那么这里其实就是单符号位的溢出判断，根据计算前的正负性和计算后的正负性得到溢出结果。

双符号位法

这里引入双符号位：

$c_{s+1}$ ：符号位运算后是否有进位，有进位时 $c_{s+1}=1$ ，无进位时 $c_{s+1}=0$
$c_s$ ：数值位的最高位运算后是否进位，有进位时 $c_s=1$ ，无进位时 $c_s=0$

那么我们可以根据加数的正负分为三种情况讨论：

正数 + 正数：首先符号位都是 0，那么不可能有进位，即 $c_{s+1}=0$ ，而 $c_s$ 是根据数值位的最高位运算后是否有进位得到，那么如果有进位，说明结果的符号位是 1，即两个正数相加得到了负数，说明正溢出了，如果没进位，则未发生溢出。
正数 + 负数：首先我们知道正数+负数一定不会产生溢出，如果 $c_{s+1}=1$ ，则 $c_{s}=1$ ；如果 $c_{s+1}=0$ ，则 $c_{s}=0$ ，即 $c_s$ 和 $c_{s+1}$ 一定相同。
负数 + 负数：符号位都是 1，那么符号位相加一定会产生进位，即 $c_{s+1}=1$ ，而 $c_s$ 也是要根据数值位的最高位运算后是否有进位得到，如果无进位，说明结果的符号位是 0，即两个负数相加得到了正数，说明负溢出了，如果有进位，则未发生溢出。

这样我们就可以总结出规律来了，如果 $c_s = c_{s+1}$ 则未发生溢出，反之则发生溢出。

还是通过一个例子：已知 $X]_补=1, 0011100$ ， $Y]_补=0, 1110001$ ，求 $X-Y]_补$

求 $Y]_补 = 1, 0001111$
求 $X]_补+[-Y]_补 = 0, 0101011$ ，双符号位分别是 $c_s=0$ ， $c_{s+1}=1$ ，可以看到这两个符号不一致，说明产生了溢出，从单符号位法出发，两个负数相加得到了正数，说明发生了负溢出。

定点数乘法

依旧是从例子入手，这里先不把符号转化为符号位， $x = - 0.1101$ ， $y = 0.1011$ ，求 $\cdot y$ ：

那么看出规律，从 $y$ 的低位开始，与 $x$ 相乘，再向右移位，一直到 $y$ 的最高位计算完，移完位结束。

这里引入两个寄存器，ACC —— 累加器，MQ —— 乘商寄存器，则上面例子的流程如下：

初始 ACC 是全 0，MQ 里保存乘数 $y$
取出 MQ 的末位，是 1，那么 ACC 里要加上 $x$ (计算过程中不考虑符号)
右移 1 位，移到 MQ 里了一个 1(这是结果的末位)
取出 MQ 的末位，还是 1，ACC 加上 $x$
右移 1 位，移到 MQ 里一个 1
取出 MQ 的末位，是 0，那么就是加上 0 了，然后右移 1 位，移到 MQ 里一个 1
取出 MQ 的末位，是 1，那么再加上 $x$
右移 1 位，移到 MQ 里一个 1

这样我们得到最终的结果 $- 0.10001111$ 。

在此基础上引入补码的定点数乘法运算规则：
1）符号位参与运算
2）被乘数与部分积(也就是ACC里面的数)使用双符号位，乘数(MQ里的数)使用单符号位
3）乘位末位增设附加位，初始为 0
4）算术移位
5）最后一步不移位
6）乘数次低位 - 最低位，如果 =1 则 $x]_补$ ，如果 =0 则 $+ 0$ ，如果 =-1 则 $x]_补$

那么对于上面的例子，我们有 $x]_补=11.0011$ ， $x]_补=00.1011$ ，对应相乘过程如下：

初始 ACC 和 MQ 里的数如下
次低位 - 最低位为 1，那么 $x]_补$
算术右移，移到 MQ 一个 1
次低位 - 最低位为 0，那么 $+ 0$ ，那么直接右移，移到 MQ 一个 0
次低位 - 最低位为 -1，那么 $x]_补$
算术右移，移到MQ一个0
次低位 - 最低位 1，那么 $x]_补$
算术右移，移到MQ一个0
次低位 - 最低位 -1，那么 $x]_补$ ，最后一步不需要再右移了

最终得到双符号位补码 $11, 01110001$

定点数除法

恢复余数法

首先看下原码形式下的定点数除法，假设被除数 $x]_原 = 0.1011$ ，除数 $y]_原 = 0.1101$ ：

(按照十进制除法的方式) 首先尝试取 1，发现不行
那么只能取 0，再尝试取 1，除数相当于右移了一位，可行
再尝试取 1，除数相当于右移一位，可行
尝试取 1，除数相当于右移一位，不可行，取 0
尝试取 1，除数相当于右移一位，可行，此时得到商 $0.1101$ ，余数 $0.00000111$

上面方法很直观，但实际应用中，我们不希望占用寄存器的位数是逐渐增加的，这里引入恢复余数法。

看这个例子： $x = 0.1011$ ， $y = 0.1101$ ，求 $x / y$ ：
1） $x| - |y| = |x| + (-|y|)=[x]+[-|y|]_补$ ， $x]_原=0.1011$ ， $y]_原=0.1101$ ,， $∣ x ∣ = 0.1011$ ， $∣ y ∣ = 0.1101$ ， $y|]_补=1.0011$
2）和上面的方法一样，先尝试取 1，减去 $∣ y ∣$ ，相当于加上 $y|]_补$ ，得到一个负数，说明取 1 是不可行的，那么这里需要把减掉的 $∣ y ∣$ 加回来。

3）下面我们左移余数，那么就相当于我们之前右移了除数，然后再尝试取 1，即减去 $y$ ，是正数，说明可行

4）左移余数，再尝试取 1，是正数，说明可行

5）左移余数，再尝试取 1，是负数，不可行，把 $∣ y ∣$ 加回来

6）左移余数，再尝试取 1，是正数，说明可行，至此，得到商 $0.1101$ ，余数 $0.00000111$ ，这里因为左移了四次余数，所以最后余数要右移回去。

有恢复余数法，也相应地有不恢复余数法，规则如下：

余数 < 0，余数左移再 $+ ∣ y ∣$
余数 > 0，余数左移再 $- ∣ y ∣$

加减交替法

上面的恢复余数法中符号位是单独计算的，而在加减交替法中，符号位是参与到计算中的，其规则如下：

数据都用补码表示，符号位参与运算。
初始时观察被除数与除数的符号，同号做减法，异号做加法。
若余数与除数同号，则商 1，余数左移一位减去除数；若异号，则商 0，余数左移一位加上除数。
重复第三步操作直到得到 n 位商 (不包含符号位)。
商的末尾恒置 1。

看一个例子： $x = - 0.1001$ ， $y = 0.1101$ ，求 $x/y]_补$ ：

$x]_补=1.0111$ ， $y]_补=0.1101$ ， $y]_补=1.0011$
初始被除数与除数的符号是异号，做加法
可以看到余数与除数同号，商 1，余数左移一位减去除数
余数与除数异号，商 0，余数左移一位加上除数
余数与除数同号，商 1，余数左移一位减去除数
余数与除数异号，商 0，这样我们就得到了商 $1.0101$ ，因为商的末位要恒置 1，那么余数左移一位加上除数再算术右移4位就是最终的余数 $1.11111111$