原碼一位乘法的實(shí)現(xiàn)算法(一)

　　用原碼實(shí)現(xiàn)乘法運(yùn)算是十分方便的。原碼表示的兩個(gè)數(shù)相乘，其乘積的符號(hào)為相乘兩數(shù)符號(hào)的異或值，數(shù)值則為兩數(shù)絕對(duì)值之積。
假定 [X]_原 = X_SX₁ X₂… X_n
　　　　 [Y]_原 = Y_SY₁Y₂… Y_n
　　　則 [X*Y]_原 = [X]_原 * [Y]_原
　　　　　　　　 = (X_S⊕Y_S) (X₁X₂ … X_n) * (Y₁ Y₂ … Y_n)
　　結(jié)果是把符號(hào)位和數(shù)值鄰接起來。

　　為了引出在計(jì)算機(jī)中實(shí)現(xiàn)定點(diǎn)原碼一位乘法的具體方案，先看手工乘法運(yùn)算的實(shí)際執(zhí)行步驟。
　　假定： 　　X= 0.1101 　　Y= 0.1011
　　　　　　　0. 1 1 0 1
　　　　　　* 0. 1 0 1 1
　　　　　
　　　　　　　　 1 1 0 1 　　　　　X*Y = 0.10001111，符號(hào)為正
　　　　　　　 1 1 0 1
　　　　　　 0 0 0 0
　　　　　 1 1 0 1
　　　　
　　0. 1 0 0 0 1 1 1 1

　　在手工計(jì)算時(shí)，其算法與執(zhí)行步驟：
　?、?依乘數(shù)每一位上的取值為1還是為0，決定相加數(shù)取被乘數(shù)的值還是取零值；
　　② 各相加數(shù)從乘數(shù)的最低位求起，逐位變高并將相加數(shù)逐個(gè)左移一位，最后一步一次求和；
　?、?符號(hào)位按正乘正、負(fù)乘負(fù)結(jié)果的符號(hào)位為正，正乘負(fù)、負(fù)乘正結(jié)果的符號(hào)為負(fù)的方案求出乘積的符號(hào)。

　　在計(jì)算機(jī)內(nèi)實(shí)現(xiàn)原碼乘法運(yùn)算，則不能簡(jiǎn)單照搬上述方法，主要表現(xiàn)在以下諸方面。

　　首先，在運(yùn)算器內(nèi)是很難實(shí)現(xiàn)多個(gè)數(shù)據(jù)同時(shí)相加的，通常只能完成對(duì)兩數(shù)的求和操作。這一點(diǎn)比較容易解決，可以每求得一個(gè)相加數(shù)，就同時(shí)完成與上一次部分積相加的操作；

　　其次是在手工計(jì)算時(shí)，各相加數(shù)逐個(gè)左移一位，最終相加數(shù)的位數(shù)為相乘二數(shù)位數(shù)的兩倍，而在計(jì)算機(jī)中，加法器的位數(shù)一般與寄存器的位數(shù)相同，而不是寄存器位數(shù)的兩倍。這實(shí)際上也可以用另外的辦法加以解決。手工計(jì)算時(shí)，各相加數(shù)是逐位左移一位，但很容易發(fā)現(xiàn)，在計(jì)算機(jī)內(nèi)，在每次計(jì)算本次部分積之和時(shí)，前一次部分積的最低一位是不再參與相加計(jì)算的。這就意味著，若采用每求得一次部分積之后使其右移一位，則可以只用N位的加法器就能實(shí)現(xiàn)兩個(gè)N位的數(shù)相乘，并有可能求得雙倍位數(shù)的乘積。顯而易見，若前一次部分積已經(jīng)右移一位，就可以用其高位部分，再用加被乘數(shù)或加零的方法求得本次的部分積。

　　最后一點(diǎn)，手工計(jì)算時(shí)，乘數(shù)每一位的值是0還是1都能直接看見，而在計(jì)算機(jī)內(nèi)，若采用放乘數(shù)的寄存器的每一位來直接決定本次相加數(shù)是被乘數(shù)還是零，實(shí)現(xiàn)起來是不方便的，若均采用該寄存器的最低一位來執(zhí)行這種判別就簡(jiǎn)便多了。為此，可以在每求一次部分積，使放乘數(shù)的寄存器執(zhí)行一次右移操作即可實(shí)現(xiàn)。若移位時(shí)，使其最高一位數(shù)值位接收加法器最低位的移位輸出，則完成乘法運(yùn)算后，該寄存器中保存的將是乘積的低位部分，而原來的乘數(shù)在逐位移位過程中已經(jīng)丟失。

　　計(jì)算機(jī)內(nèi)求乘積的符號(hào)，很容易用求相乘二數(shù)符號(hào)的半加和(異或值)實(shí)現(xiàn)。
　　有了上述說明,我們就可以得到如圖2.6所示的實(shí)現(xiàn)原碼一位乘法的邏輯電路框圖。


圖2.6 實(shí)現(xiàn)原碼一位乘法運(yùn)算的邏輯線路框圖

　　乘法開始時(shí),A寄存器被清為零,作為初始部分積。被乘數(shù)放在B寄存器中,乘數(shù)放在C寄存器中。實(shí)現(xiàn)部分積和被乘數(shù)相加是通過給出A→F命令和B→F命令實(shí)現(xiàn)的,部分積右移一位送A寄存器是通過把 F右斜一位的命令F/2→A來控制完成的，用F A命令完成把運(yùn)算器的輸出直接（不移位）送到A寄存器。

　　C寄存器是用移位寄存器實(shí)現(xiàn)的,本身能在移位命令C/2→C控制下自行移位,其最低位的值可用作B→F的控制命令。請(qǐng)注意,加法器最低一位的值,右移時(shí)將移入C寄存器的最高數(shù)值位,使相乘之積的低位部分保存進(jìn)C寄存器中,原來的乘數(shù)在逐位右移過程中丟失了。
圖上還給出了一個(gè)計(jì)數(shù)器T,用來控制逐位相乘的次數(shù)。它的初值經(jīng)常放乘數(shù)位數(shù)的補(bǔ)碼值,以后每完成一位乘計(jì)算就使其計(jì)數(shù)一次,待計(jì)數(shù)到0時(shí),給出結(jié)束乘運(yùn)算的控制信號(hào)。

　　圖上未畫出求結(jié)果的符號(hào)的電路,可以通過對(duì)相乘兩數(shù)的符號(hào)執(zhí)行異或操作完成。

原碼一位乘法的實(shí)現(xiàn)算法(二)

　　用原碼實(shí)現(xiàn)乘法運(yùn)算是十分方便的。原碼表示的兩個(gè)數(shù)相乘，其乘積的符號(hào)為相乘兩數(shù)符號(hào)的異或值，數(shù)值則為兩數(shù)絕對(duì)值之積。

下面是恢復(fù)余數(shù)除法的一個(gè)例子。
　　假定 X=0.1011 , Y=0.1101, 則有 [X]_補(bǔ) = 00 1011
　　　　　　　　 [Y]_補(bǔ) = 00 1101 , [-Y]_補(bǔ) = 11 0011

　　除法計(jì)算結(jié)束,二數(shù)符號(hào)異或?yàn)?,商是 +0.1101,余數(shù)為0.0111 * 2-4 ,余數(shù)0111是左移4次后得到的結(jié)果,所以真正的結(jié)果為這個(gè)值乘上2-4。若最后一次的余數(shù)為負(fù),正確的余數(shù)應(yīng)為 +Y 恢復(fù)后的正余數(shù)乘上2-4 。

　　這種方法的缺點(diǎn)是明顯的，當(dāng)某一次 -Ｙ的差值為負(fù)時(shí)，要多一次＋Y恢復(fù)正余數(shù)的操作,降低了執(zhí)行速度,又使控制線路變得復(fù)雜,因此在計(jì)算機(jī)中很少采用。在計(jì)算機(jī)中普遍采用的是不恢復(fù)余數(shù)的除法方案,它是對(duì)恢復(fù)余數(shù)除法的一種修正措施,即當(dāng)某一次減得的差值為負(fù)時(shí),不是恢復(fù)它為正差值后再繼續(xù)運(yùn)算,而是設(shè)法直接用這個(gè)負(fù)的差值直接求下一位商,其實(shí)現(xiàn)原理敘述如下:

　　在恢復(fù)余數(shù)的除法運(yùn)算中,若第i-1次求商時(shí)的余數(shù)為 +R_i-1 ,本次上商為1，下一次求商用的辦法是
　　　　R_i= 2R_i-1 - Y

　　當(dāng)Ri < 0時(shí),第i位的商上0,而恢復(fù)余數(shù)的操作結(jié)果應(yīng)為Ri + Y,下一次,即第i+1次求商的減法操作是
　　　　R_i+1= 2 (R_i+ Y ) - Y = 2 R_i + 2Y - Y = 2R_i+ Y

　　上述公式表明,當(dāng)某一次求商,其減得的差值為負(fù),即R<0時(shí),本次上商為0,繼續(xù)求下一位商時(shí),可以不必恢復(fù)正余數(shù),而是直接將負(fù)的差值左移一位(得2R)后,再采用加上除數(shù)的辦法來完成,即通過判別2R+Y運(yùn)算的結(jié)果為正還是為負(fù)。由此可得出不恢復(fù)余數(shù)的除法運(yùn)算規(guī)則為:
　
　　當(dāng)余數(shù)為正時(shí),商上1,求下一位商的辦法,是正余數(shù)左移一位,用減去除數(shù)的辦法得到;
　　余數(shù)為負(fù)時(shí),商上0,求下一位商的辦法,是負(fù)余數(shù)左移一位,用加上除數(shù)的辦法得到。即在本方案中,在求得本位商值的同時(shí),還要影響到用減去還是用加上除數(shù)的操作繼續(xù)求下一位商,所以不恢復(fù)余數(shù)除法又叫加減交替除法。

　　下面給出不恢復(fù)余數(shù)除法執(zhí)行除運(yùn)算過程的一個(gè)例子。用的還是X=0.1011,Y=0.1101這兩個(gè)值, [X]_補(bǔ) = 00 1011 , [Y]_補(bǔ) = 00 1101 , [-Y]_補(bǔ) = 11 0011。


　　運(yùn)算結(jié)果,商的數(shù)值位為1101,符號(hào)位為相除二數(shù)符號(hào)的異或值0,結(jié)果為+0.1101。
原碼一位除的不恢復(fù)余數(shù)的運(yùn)算過程的詳細(xì)控制流程如圖2.9所示。

圖2.9 不恢復(fù)余數(shù)除法的運(yùn)算的控制過程

　　至此,我們可把定點(diǎn)原碼一位除的實(shí)現(xiàn)方案小結(jié)如下:
　　(1) 對(duì)定點(diǎn)小數(shù)除法,首先要比較除數(shù)和被除數(shù)的絕對(duì)值的大小,需要防止出現(xiàn)數(shù)值溢出的錯(cuò)誤。
　　(2) 商的符號(hào)為相除二數(shù)的符號(hào)的半加和。
　　(3) 計(jì)算機(jī)中用加減交替法實(shí)現(xiàn)除法運(yùn)算時(shí),被除數(shù)的位數(shù)可以是除數(shù)的兩倍,其低位的數(shù)值部分，開始時(shí)放在用于保存商的寄存器中。運(yùn)算過程中,放被除數(shù)和商的寄存器同時(shí)左移一位。
　　(4) 在計(jì)算機(jī)中,求差和移位是在同一個(gè)操作步驟中完成的,而不是像我們書面寫的那種形式用兩個(gè)步驟完成。