计算机组成原理——关于原码、补码、移码运算及浮点数运算的总结
一、数的表示法
1.1 原码
[X]原码={X0≤X≤2n−1−12n−1+∣X∣−(2n−1−1)≤X≤0[X]_{原码}= \left\{ \begin{array}{lcl} X & 0\leq X\leq2^{n-1}-1 \\ 2^{n-1}+|X| & -(2^{n-1}-1)\leq X\leq 0 \end{array}\right. [X]原码={X2n−1+∣X∣0≤X≤2n−1−1−(2n−1−1)≤X≤0
对于一个n位的二进制数,最大可以表示的无符号数为2n−12^n-12n−1,即为全1,最大可以表示的有符号数是最高为0,其余为1,即比最大的无符号数少一位2n−1−12^{n-1}-12n−1−1 。同理,最小的负数应当为−(2n−1−1)-(2^{n-1}-1)−(2n−1−1)。
缺点:0的表示存在两种可能,一种为最高位为1其余为0(负0),另一种是全0(正0),0的表示出现了二义性
1.2 反码
[X]反码={X0≤X≤2n−1−12n−1−∣X∣−(2n−1−1)≤X≤0[X]_{反码}= \left\{ \begin{array}{lcl} X & 0\leq X\leq2^{n-1}-1 \\ 2^{n}-1-|X| & -(2^{n-1}-1)\leq X\leq 0 \end{array}\right. [X]反码={X2n−1−∣X∣0≤X≤2n−1−1−(2n−1−1)≤X≤0
同原码表示的数的范围一致,但表示形式发生了变化,原码中正负数的区别仅仅是最高位的符号位不同,而在反码中,正负数的所有位都正好相反。这里的2n−12^n-12n−1其实正好是所有位都为1,减去∣X∣|X|∣X∣ 表示的意思就是对应的位置为1的地方会变为0,对应的位置为0的地方会变为1,这就达到了“取反”的效果
缺点:0的表示仍然存在两种可能,一种为全1(负0),另一种是全0(正0),0的表示出现了二义性
1.3 补码
[X]补码={X0≤X≤2n−1−12n−∣X∣−(2n−1)≤X<0[X]_{补码}= \left\{ \begin{array}{lcl} X & 0\leq X\leq2^{n-1}-1 \\ 2^{n}-|X| & -(2^{n-1})\leq X<0 \end{array}\right. [X]补码={X2n−∣X∣0≤X≤2n−1−1−(2n−1)≤X<0
注意到负数的补码仅仅是在原码的基础上加1,如果从2n2^n2n来考虑,其代表的是将n位数扩展一位,然后来减去∣X∣|X|∣X∣ 。对于正0来说,其补码为全0,而对于负0来说,如果从其反码的角度来考虑,其补码应为(2n−1)+1=2n(2^n-1)+1=2^n(2n−1)+1=2n ,由于数位一共只有n位,第n+1位被舍弃了,所以其应当为全0,与正0的表示方法相同;如果直接用2n−∣X∣2^n-|X|2n−∣X∣也能得到一样的结果,所以使用补码成功的解决了0的二义性问题。
如果我们稍微观察就会发现,补码表示的最小负数是比原码和反码要小1的。这是为什么呢?
首先对于一个n位数,如果没有数的表示是重复的,那么我们显然可以表示2n2^n2n个数,如果最大的正数为2n−1−12^{n-1}-12n−1−1,而最小的负数时−(2n−1−1)-(2^{n-1}-1)−(2n−1−1),这其中一共可以表示的数的个数是(2n−1−1+2n−1−1+1)=2n−1(2^{n-1}-1+2^{n-1}-1+1)=2^n-1(2n−1−1+2n−1−1+1)=2n−1,这样显然会少了一个数,那么这个数去哪里了呢?
我们很容易想到在原码中负0的表示——最高位为1,其他全为0。那么在我们的补码体系中,显然这个数应是一个负数,那么我们对其求原码,∣X∣=2n−[X]补码|X|=2^n-[X]_{补码}∣X∣=2n−[X]补码 ,得到的结果仍然是最高位为1,其他位全为0,这个数在原码中表示的值为2n−12^{n-1}2n−1,由于其为负,所以我们可以表示的最小的负数为−2n−1-2^{n-1}−2n−1
1.4 移码
[X]移码=2n−1+X−2n−1≤X<2n−1[X]_{移码}= 2^{n-1}+X \\ -2^{n-1}\leq X < 2^{n-1}[X]移码=2n−1+X−2n−1≤X<2n−1
这里的2n−12^{n-1}2n−1 直观来说就是最高位为1,那么我们很容易发现对正数来说最高位为1,负数的最高位为0,0的表示为最高位为1,其余位为0。
对于全0来说其表示的数X应为 -2n−12^{n-1}2n−1
移码同补码一样,解决了0的二义性问题,且表示数的范围相同,没有数的浪费。我们可以对比移码和补码数的表示的不同。
对于正数来说,移码和补码的区别仅仅在于最高位不同,正数的补码最高位为0,而移码的最高位为1.
对于负数来说,我们也惊奇的发现仅仅是最高位不同,因为[X]补码=2n+X,[X]移码=2n−1+X[X]_{补码}=2^n+X, [X]_{移码}=2^{n-1}+X[X]补码=2n+X,[X]移码=2n−1+X,在补码中负数的最高位为1,而在移码中最高位再加1就变为了0
二、 定点数运算
2.1 定点加减运算
加法直接相加即可,减法需要把减数变成其相反数的补码再进行加法运算
2.1.1 溢出判别
当运算的结果超过允许的表示范围,则产生溢出;其中包含正溢出和负溢出,正溢出是两个正数相加,范围超过了2n−1−12^{n-1}-12n−1−1,而负溢出是两个负数相加,范围超过了−(2n−1−1)-(2^{n-1}-1)−(2n−1−1) ,一个正数和负数相加不会发生溢出。
注:这里只讨论加法运算,减法运算是同理的。
主要有三种判别方法:
ab‾c+abc‾=1\overline{ab}c+ab \overline{c}=1abc+abc=1 (其中aaa表示加数符号位,bbb表示被加数符号位,ccc表示运算和符号位)这里正好代表了溢出的两种情况,前者代表正溢出,两个正数的符号位是0,相加和c却为1,代表正溢出,后者代表负溢出,两个负数的符号位为1,相加和c却为0,代表负溢出Cf⨁C=1C_f \bigoplus C=1Cf⨁C=1 (这里CfC_fCf代表符号位运算产生的进位,CCC代表最高有效位产生的进位),对于两个正数相加,符号位不会产生进位,永远为0,而当最高有效位发生进位即为1时,发生溢出;对于两个负数相加,符号位始终产生进位1,而当最高有效位不发生进位时,发生溢出,以4位举例:1000+1001 即发生溢出.这里我们还会发现一个比较有趣的现象,即对于负数的补码来说,如果除去符号位的1不看,数值绝对值的大小正好同我们平时的认知反过来,比如1111其实代表的是绝对值最小的负数-1,而1000代表的是绝对值最大的负数扩展符号位 用两位符号位来避免符号位语义紊乱
[X]变形补={X0≤X≤2n−1−12n+1−∣X∣−(2n−1)≤X<0[X]_{变形补}= \left\{ \begin{array}{lcl} X & 0\leq X\leq2^{n-1}-1 \\ 2^{n+1}-|X| & -(2^{n-1})\leq X< 0 \end{array}\right. [X]变形补={X2n+1−∣X∣0≤X≤2n−1−1−(2n−1)≤X<0
对于正数来说,不发生变化,但对于负数来说,会多一位符号位1
那么对于运算结果便有四种情况
00——结果为正,不溢出11——结果为负,不溢出01——结果为负,正溢出10——结果为正,负溢出
即 Fs1⨁Fs2=1F_{s1}\bigoplus F_{s2}=1Fs1⨁Fs2=1代表溢出
2.2 定点原码一位乘法
原码相乘不考虑符号位,直接将符号位的正负值保存下来,对数的绝对值进行乘法运算
整个过程类似于我们平时使用的竖式计算方式,但是我们在竖式计算的过程中是从最低位开始乘起,接下来每次乘的时候会把当次乘的结果保留下来左移一位,最后把所有结果相加。
于是我们仿照这种做法,但我们不是把每位相乘的结果左移,而是把当前得到的整个部分积右移,其实原理是一样的,只是相对问题而已。
在这种情况下,如果乘数是n位,我们需要进行n次累加和移位
整个过程如下图所示:
X=0.1101 Y=-0.1011 求X*Y
2.3 定点补码一位乘法
设 [x]补=x0.x1⋯xn,[y]补=y0.y1⋯yn,[x]_{补}=x_0.x_1\cdots x_n, [y]_{补}=y_0.y_1\cdots y_n,[x]补=x0.x1⋯xn,[y]补=y0.y1⋯yn,
则 [x∗y]补=[x]补(0.y1y2⋯yn)−y0∗[x]补[x*y]_{补}=[x]_{补}(0.y_1y_2\cdots y_n)-y_0*[x]_{补}[x∗y]补=[x]补(0.y1y2⋯yn)−y0∗[x]补
上述结论易证,只需要对yyy进行讨论即可
而整个乘法主要采用Booth乘法,具体操作为
原理:设正乘数Y=(y0.y1⋯yn)2Y=(y_0.y_1 \cdots y_n)_2Y=(y0.y1⋯yn)2 ,故y0=0y_0=0y0=0,
如果取yn+1=0y_{n+1}=0yn+1=0,那么每项都可以表示为yi+1−yiy_{i+1}-y_iyi+1−yi的形式,这样也就得到了我们上面的表格
对于负数的补码来说,我们由上面的公式有 [x∗y]补=[x]补(0.y1y2⋯yn)−[x]补[x*y]_{补}=[x]_{补}(0.y_1y_2\cdots y_n)-[x]_{补}[x∗y]补=[x]补(0.y1y2⋯yn)−[x]补
如果该数的前两位是11,那么在Booth乘法中不会有操作(最后一次操作不右移),而直接用公式计算时得到的结果也一样
同理如果该数前两位为10,两种方式的结果也一致,所以综上Booth乘法成立。
下面以一个具体的例子来实现Booth 一位乘法:
2.4 定点原码一位除法
同前面的方式一样,先处理符号位
接下来我们常常使用的是加减交替法(可以不用恢复余数)
规则如下:
被除数先减除数,结果为正,商上1;结果为负,商上0.
若上次商为1,左移一位,减除数。
若上次商为0,左移一位,加除数。
注意:若最后余数为负,还需要再加上除数来恢复
原理:
在恢复余数的除法过程中,如果我们记某次结果为a,且a<0,那么根据恢复余数的做法,我们应当加上除数b,得到结果为(a+b),然后左移一位得到2(a+b),再减去除数b进行下一轮操作,得到的结果数是2*(a+b)-b=2*a+b,这样以来我们发现,如果某次余数为负,我们只需要将余数左移一位,下次操作加上除数即可,这样不需要我们每次恢复余数,加快了效率。
举例如下:
2.5 定点补码一位除法
形式和过程同定点原码一位除法相似,但判断的条件变成了(被除数/余数)和除数的符号是否相同而不是余数是否为正,符号位也需要参数运算
另外末位商恒置为1(保证误差在2−n2^{-n}2−n之内)
举例如下:
三、 浮点数运算
3.1 浮点数的加减法运算
3.1.1 “对阶”规则
阶码小的数向阶码大的数对齐,阶码小的数的尾数需要右移
注意:无符号数尾数右移高位补0,有符号数尾数右移高位补符号位
3.1.2 规格化操作
规格化的目的是使尾数部分的绝对值尽可能以最大值的形式出现。也就是说所有尾数的绝对值应大于12\frac{1}{2}21。
右规:如果运算结果出现两个符号位不一致的情况比如 10.XXX⋯X,01.XXX⋯X10.XXX\cdots X,01.XXX\cdots X10.XXX⋯X,01.XXX⋯X 前者代表下溢出,后者代表上溢出,需要将尾数向右移动一位,阶码+1
左规:如果运算结果没有溢出,但符号位和最高有效位相同,为了保证浮点数的规格化,需要将尾数向左移动,直到满足规格数的条件,阶码需要减去移动的位数
舍入:在右规或对阶的过程中,尾数向右移动会损失精度,经常用0舍1入法,即舍去的最高位如果为1则将最低位变为1
检查阶码是否溢出:在规格化和舍入时,阶码均可能溢出。(如右规时可能发生阶码上溢,左规可能发生阶码下溢)当阶码上溢,则置上溢标志,阶码下溢,则置机器0
举例如下:
3.2 浮点数的乘除法运算
两浮点数相乘,其乘积的阶码为相乘两数阶码之和,尾数为相处两数的尾数之积
两浮点数相除,其商的阶码为相乘两数阶码之差,尾数为相处两数的尾数之商
3.2.1 浮点数的阶码运算
由于浮点数的阶码使用的是移码,所以浮点数的阶码不能直接相加
举例说明:
若 [X]移=2n+X,[Y]移=2n+Y[X]_{移}=2^n+X ,[Y]_{移}=2^n+Y[X]移=2n+X,[Y]移=2n+Y
则有 [X]移+[Y]移=2n+(2n+X+Y)=2n+[X+Y]移[X]_{移}+[Y]_{移}=2^n+(2^n+X+Y)=2^n+[X+Y]_{移}[X]移+[Y]移=2n+(2n+X+Y)=2n+[X+Y]移
我们易见移码对于加法并不closed(封闭),所以我们考虑其他的途径
我们注意到 [Y]补=2n+1+Y[Y]_{补}=2^{n+1}+Y[Y]补=2n+1+Y(这里的Y代表其数值)
[X]移+[Y]补=2n+1+2n+X+Y=2n+1+[X+Y]移[X]_{移}+[Y]_{补}=2^{n+1}+2^n+X+Y=2^{n+1}+[X+Y]_{移}[X]移+[Y]补=2n+1+2n+X+Y=2n+1+[X+Y]移
而一共其实只有n+1位(n位数据位,1位符号位),2n+1是第n+2位2^{n+1}是第n+2位2n+1是第n+2位,所以在此情况下的运算是封闭的
3.2.2 判断溢出的方法
采用双符号位的方式进行计算,并且规定移码的最高符号位为0,如果运算结果移码的最高符号位为1代表溢出,若低位符号位为0代表上溢出(正数相加),若低位符号位为1代表下溢出(负数相加)
举例说明:(1位符号位+4位数据位)
01 1111 (移码)+ 00 1001(补码)=10 1000 上溢出
00 0000 (移码)+ 11 0000 (补码)=11 0000 下溢出
3.2.3 乘法运算步骤
检测操作数是否为0阶码相加,求出积的阶码尾数相乘,求出积的尾数尾数乘积规格化判断阶码有无溢出举例如下:
3.2.4 除法运算步骤
检测操作数是否为0尾数调整,使得被除数的绝对值大于除数尾数的绝对值被除数阶码减除数阶码,得到商的阶码被除数尾数除以除数尾数,得到商的尾数尾数规格化判断阶码有无溢出举例如下:数值同上
四、总结
对于定点补码的一位除法的原理还不是很明晰,需要继续学习
另外对于图片只能横排是没想到的。。下次改进