搜索
在计算机中，乘法运算是一种很重要的运算，有的机器由硬件乘法器直接完成乘法运算，有的机器内没有乘法器，但可以按机器作乘法运算的方法，用软件编程实现、因此，学习乘法运算方法不仅有助于乘法器的设计，也有助于乘法编程。下面从分析笔算乘法入手，介绍机器中用到的几种乘法运算方法。(1)分析笔算乘法：设A=0.1101，B=0.1011，求A×B。笔算乘法时乘积的符号由两数符号心算而得：正正得正；其数值部分的运算如下：所以A×B=+0.10001111可见，这里包含着被乘数4的多次左移，以及四个位积的相加运算。若计算机完全模仿笔算乘法步骤，将会有两大困难：其一，将四个位积一次相加，机器难以实现；其二，乘积位数增长了一倍，这将造成器材的浪费和运算时间的增加。为此，对笔算乘法做些改进。(2)笔算乘法的改进：将A?B=A?0.1011=0.1A+0.001?A+0.0001?A=0.1A+0.00?A+0.001(A+0.1A）=0.1A+0.01[0?A+0.1(A+0.1A)]=0.1{A+0.1[0?A+0.1(A+0.1A)]}=2-1{A+2-1[0?A+2-1(A+2-1A)]}=2-1{A+2-1[0?A+2-1(A+2-1(A+0))]}由上式可见，两数相乘的过程，可视作加法和移位(乘2-1相当于做一位右移)两种运算，这对计算机来说是非常容易实现的。从初始值为0开始，对上式作分步运算，则第一步：被乘数加零A+0=0.1101+0.0000=0.1101第二步：右移一位，得新的部分积2-1(A+0)＝0.01101第三步：被乘数加部分积A+2-1(A+0)=0.1101+0.01101=1.00111第四步：右移一位，得新的部分积2-1A+2-1(A+0)=0.100111第五步：0?A+2-1[A+2-1(A+0)]=0.100111第六步：2-1{0?A+2-1[A+2-1(A+0)]}=0.0100111第七步：A+2-1{0?A+2-1[A+2-1(A+0)]}=1.0001111第八步：2-1{A+2-1[0?A+2-1(A+2-1(A+0))]}=0.10001111上述运算过程可归纳为：①乘法运算可用移位和加法来实现，当两个四位数相乘，总共需做四次加法和四次移位。②由乘数的末位值确定被乘数是否与原部分积相加，然后右移一位，形成新的部分积；同时，乘数也右移一位，由次低位作新的末位，空出最高位放部分积的最低位。③每次做加法时，被乘数仅仅与原部分积的高位相加，其低位被移至乘数所空出的高位位置。计算机很容易实现这种运算规则。用一个寄存器存放被乘数，一个寄存器存放乘积的高位，又用一个寄存器存放乘数及乘积的低位，再配上加法器及其他相应电路，就可组成乘法器。又因加法只在部分积的高位进行，故不但节省了器材，而且还缩短了运算时间。1．原码一位乘法由于原码表示与真值极为相似，只差一个符号，而乘积的符号又可通过两数符号的逻辑异或求得，因此，上述讨论的结果可以直接用于原码一位乘，只需加上符号位处理即可。上图是一个32位乘法器的结构框图，其中32位被乘数放在R2中，运算开始时32位乘数放在R1中，运算结束时64位乘积的高位放在R0中，低位放在R1中，R0和R1串联移位。完成这个定点原码一位乘法的运算规则可以用如下图所示的逻辑流程图表示。（32位+32位=64位）在该乘法过程中，每次操作是根据乘数的一位进行操作，对于32位数的乘法，需要循环32次完成一个乘法操作，因此称为一位乘法。例：用原码的乘法方法进行2×3的四位乘法。解：在乘法开始之前，R0和R1中的初始值为0000和0011，R2中的值为0010。在乘法的第一个循环中，判断R1的最低位为1，所以进入步骤1a，将R0的值加上R2的值，结果0010送人R0，然后进入第二步，将R0和R1右移一位，R0、Rl的结果为00010001，见下表的循环1，表中黑体字的数据位是乘法过程中判断的R1最低位。第二个循环过程中，判断R1的最低位为l，仍进入步骤la，加0010，结果为0011，然后在第二步中将R0和R1右移一位，结果为00011000，见下表的循环2。第三次循环中，因R1的最低位为0，进入步骤lb，R0不变，第二步移位后结果为00001100，见下表的循环3。第四次循环时仍因R1最低位为0，只作移位，结果为00000110，这就是乘法的结果6，见下表的循环4。循环步骤乘积（R0，R1）0初始值0000001111a：加0010001000112：右移1位0001000121a：加0010001100012：右移1位0001100031b：加0000110002：右移1位0000110041b：加0000011002：右移1位000001102．原码两位乘法原码两位乘与原码一位乘一样，符号位的运算和数值部分是分开进行的，但原码两位乘是用两位乘数的状态来决定新的部分积如何形成，因此可提高运算速度。两位乘数共有4种状态，对应这4种状态可得下表。乘数yn-1yn新的部分积00等于原部分积右移两位01等于原部分积加被乘数后右移两位10等于原部分积加2倍被乘数后右移两位11等于原部分积加3倍被乘数后右移两位表中2倍被乘数可通过将被乘数左移一位实现，而3倍被乘数的获得可以分两步来完成，利用3=4-1，第一步先完成减1倍被乘数的操作，第二步完成加4倍被乘数的操作。而加4倍被乘数的操作实际上是由比“11”高的两位乘数代替完成的，可以看作是在高两位乘数上加“1”。这个“1”可暂时存在Cj触发器中。机器完成置“1”Cj即意味着对高两位乘数加1，也即要求高两位乘数代替本两位乘数“11”来完成加4倍被乘数的操作。由此可得原码两位乘的运算规则如下表所示。乘数判断位yn-1yn标志位Cj操作内容000z→2,y*→2,Cj保持“0”010z+x*→2,y*→2,Cj保持“0”100z+2x*→2,y*→2,Cj保持“0”110z-x*→2,y*→2,置“1”Cj001z+x*→2,y*→2,置“0”Cj011z+2x*→2,y*→2,置“0”Cj101z-x*→2,y*→2,Cj保持“1”111z→2,y*→2,Cj保持“1”表中z表示原有部分积，x*表示被乘数的绝对值，y*表示乘数的绝对值，→2表示右移两位，当作-x*运算时，一般采用加[-x*]补来实现。这样，参与原码两位乘运算的操作数是绝对值的补码，因此运算中右移两位的操作也必须按补码右移规则完成。尤其应注意的是，乘法过程中可能要加2倍被乘数，即+[2x*]补，使部分积的绝对值大于2。为此，只有对部分积取三位符号位，且以最高符号位作为真正的符号位，才能保证运算过程正确无误。此外，为了统一用两位乘数和一位Cj共同配合管理全部操作，与原码一位乘不同的是，需在乘数（当乘数位数为偶数时）的最高位前增加两个0。这样，当乘数最高两个有效位出现“11”时，Cj需置“1”，再与所添补的两个0结合呈001状态，以完成加x*的操作（此步不必移位）。例：设x=0.111111，y=-0.111001，用原码两位乘求[x?y]原。解：①数值部分的运算如下表所示，其中x*=0.111111,[-x*]补=1.000001,2x*=1.111110,y*=0.111001。部分积乘数y*Cj说明000.000000000.111111001110010开始，部分积为0,Cj=0根据yn-1ynCj=010加x*，保持Cj=0000.111111000.001111001.111110110011100→2,得新的部分积，乘数同时→2位根据yn-1ynCj=100加2x*，保持Cj=0010.001101000.100011111.00000111011100110→2,得新的部分积，乘数同时→2位根据yn-1ynCj=110减x*，Cj置“1”111.100100111.1110010111000111001→2,得新的部分积，乘数同时→2位000.111111根据yn-1ynCj=001加x*，Cj置“0”000.111000000111形成最终结果②乘积的符号为故[x?y]原=1.111000000111。不难理解，当乘数为偶数时，需作n/2次移位，最多作n/2+1次加法。当乘数为奇数时，乘数高位前可只增加一个“0”，此时需作n/2+1次加法，n/2+1次移位（最后一步移一位）。虽然两位乘法可提高乘法速度，但它仍基于重复相加和移位的思想，而且随着乘数位数的增加，重复次数增多，仍然影响乘法速度的进一步提高t采用并行阵列乘法器可大大提高乘法速度。原码乘法实现比较容易，但由于机器都采用补码作加减运算，倘若做乘法前再将补码转换成原码，相乘之后又要将负积的原码变为补码形式，这样增添了许多操作步骤，反而使运算复杂。为此，有不少机器直接用补码相乘，机器里配置实现补码乘法的乘法器，避免了码制的转换，提高了机器效率。3．补码一位乘法一种比较好的带符号数乘法的方法是布斯(Booth)算法。它采用相加和相减的操作计算补码数据的乘积。Booth算法对乘数从低位开始判断，根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0)，移位操作是向右移动。在上例中，第一次判断被乘数0110中的最低位0以及右边的位(辅助位0)，得00；所以只进行移位操作；第二次判断0110中的低两位，得10，所以作减法操作并移位，这个减法操作相当于减去2a的值；第三次判断被乘数的中间两位，得11，于是只作移位操作；第四次判断0110中的最高两位，得01，于是作加法操作和移位，这个加法相当于加上8a的值，因为a的值已经左移了三次。一般而言，设y=y0,yly2…yn为被乘数，x为乘数，yi是a中的第i位(当前位)。根据yj与yi+1的值，Booth算法表示如下表所示，其操作流程如下图所示。在Booth算法中，操作的方式取决于表达式(yi+1-yi)的值，这个表达式的值所代表的操作为：0无操作+1加x-1减xBooth算法操作表示yiyi+1操作说明00无处于0串中，不需要操作01加x1串的结尾10减x1串的开始11无处于1串中，不需要操作实现32位Booth乘法算法的流程图乘法过程中，被乘数相对于乘积的左移操作可表示为乘以2，每次循环中的运算可表示为对于x(yi+1-yi)231-i项的加法运算(i=3l，30，…，1，0)。这样，Booth算法所计算的结果可表示为：x×(0-y31)×20+x×(y31-y30)×21+x×(y30-y29)×22…+x×(y1-y0)×231=x×(-y0×231+y1×230+y2×229+y31×20)=x×y例：用Booth算法计算2×(-3)。解：[2]补=0010，[-3]补=1101，在乘法开始之前，R0和R1中的初始值为0000和1101，R2中的值为0010。在乘法的第一个循环中，判断R1的最低位和辅助位为10，所以进入步骤1c，将R0的值减去R2的值，结果1110送人R0，然后进人第二步，将R0和Rl右移一位，R0和R1的结果为11110110，辅助位为l。在第二个循环中，首先判断Rl的最低位和辅助位为0l，所以进入步骤1b，作加法，R0+R2=1111+0010，结果0001送入R0，这时R0R1的内容为00010110，在第二步右移后变为00001011，辅助位为0。在第三次循环中，判断位为10，进入步骤lc，R0减去R2，结果1110送入R0，R1不变；步骤2移位后R0和R1的内容为111101011，辅助位为1。第四次循环时，因两个判断位为11，所以不作加减运算，向右移位后的结果为11111010，这就是运算结果(—6)。这个乘法的过程描述如下表所示，表中乘积一栏表示的是R0、R1的内容以及一个辅助位P，黑体字表示对两个判断位的判断。用Booth补码一位乘法计算2×(-3)的过程循环步骤乘积（R0,R1,P）0初始值00001101011c：减00101110110102：右移1位1111011012