第三章 運(yùn)算方法和運(yùn)算部件

第一講

不同層次程序員看到的運(yùn)算及ALU

第二講定點(diǎn)數(shù)運(yùn)算及其運(yùn)算部件

第三講浮點(diǎn)數(shù)運(yùn)算及其運(yùn)算部件Ch3:ArithmeticandLogicOperateandALU

運(yùn)算方法和運(yùn)算部件第一講：不同層次程序員看到的運(yùn)算及ALU主要內(nèi)容高級(jí)語(yǔ)言程序中涉及的運(yùn)算（以C語(yǔ)言為例）整數(shù)算術(shù)運(yùn)算、浮點(diǎn)數(shù)算術(shù)運(yùn)算按位、邏輯、移位、位擴(kuò)展和位截?cái)嘀噶罴猩婕暗降倪\(yùn)算（以MIPS為例）涉及到的定點(diǎn)數(shù)運(yùn)算算術(shù)運(yùn)算帶符號(hào)整數(shù)運(yùn)算：取負(fù)/符號(hào)擴(kuò)展/加/減/乘/除/算術(shù)移位無(wú)符號(hào)整數(shù)運(yùn)算：0擴(kuò)展/加/減/乘/除邏輯運(yùn)算邏輯操作：與/或/非/…移位操作：邏輯左移/邏輯右移涉及到的浮點(diǎn)數(shù)運(yùn)算：加、減、乘、除基本運(yùn)算部件ALU的設(shè)計(jì)為什么房子里要有廚房、衛(wèi)生間、臥室？CPU中需提供哪些運(yùn)算部件？Why？人的需要!

程序的需要！我們從程序?qū)\(yùn)算的需求開(kāi)始分析。浮點(diǎn)數(shù)有沒(méi)有移位操作和擴(kuò)展操作？為什么？C語(yǔ)言程序中涉及的運(yùn)算算術(shù)運(yùn)算（最基本的運(yùn)算）無(wú)符號(hào)數(shù)、帶符號(hào)整數(shù)、浮點(diǎn)數(shù)的+、-、*、/運(yùn)算等按位運(yùn)算用途對(duì)位串實(shí)現(xiàn)“掩碼”（mask）操作或相應(yīng)的其他處理（主要用于對(duì)多媒體數(shù)據(jù)或狀態(tài)/控制信息進(jìn)行處理）操作按位或：“|”按位與：“&”按位取反：“~”按位異或：“^”問(wèn)題：如何從16位采樣數(shù)據(jù)y中提取高位字節(jié)，并使低字節(jié)為0？可用“&”實(shí)現(xiàn)“掩碼”操作：y&0xFF00例如，當(dāng)y=0x2C0B時(shí)，得到結(jié)果為：0x2C00C語(yǔ)言程序中涉及的運(yùn)算邏輯運(yùn)算用途用于關(guān)系表達(dá)式的運(yùn)算例如，if（x>yandi<100）then……中的“and”運(yùn)算操作“‖”表示“OR”運(yùn)算“&&”表示“AND”運(yùn)算

例如，if((x>y)&&(i<100))then……“!”表示“NOT”運(yùn)算與按位運(yùn)算的差別符號(hào)表示不同：&~&&；|~‖；……運(yùn)算過(guò)程不同：按位~整體結(jié)果類型不同：位串~邏輯值C語(yǔ)言程序中涉及的運(yùn)算移位運(yùn)算用途提取部分信息擴(kuò)大或縮小數(shù)值的2、4、8…倍操作左移:：x<<k;右移：x>>k不區(qū)分是邏輯移位還是算術(shù)移位，由x的類型確定無(wú)符號(hào)數(shù)：邏輯左移、邏輯右移高（低）位移出，低（高）位補(bǔ)0，可能溢出！問(wèn)題：何時(shí)可能發(fā)生溢出？如何判斷溢出？若高位移出的是1，則左移時(shí)發(fā)生溢出帶符號(hào)整數(shù)：算術(shù)左移、算術(shù)右移左移：高位移出，低位補(bǔ)0?？赡芤绯?！

溢出判斷：若移出的位不等于新的符號(hào)位，則溢出。右移：低位移出，高位補(bǔ)符，可能發(fā)生有效數(shù)據(jù)丟失。如何從16位采樣數(shù)據(jù)y中提取高位字節(jié)？某字長(zhǎng)為8的機(jī)器中，x、y和z都是8位帶符號(hào)整數(shù)(char型)，已知x=-81，則y=x/2=？z=2x=？(y>>8)送8位寄存器[x]補(bǔ)=10101111y=-40？z=-162?x思考題：因?yàn)楫?dāng)帶符號(hào)整數(shù)不能整除2k時(shí)右移的結(jié)果不對(duì)，編譯器該如何處理？C語(yǔ)言程序中涉及的運(yùn)算位擴(kuò)展和位截?cái)噙\(yùn)算用途類型轉(zhuǎn)換時(shí)可能需要數(shù)據(jù)擴(kuò)展或截?cái)嗖僮鳑](méi)有專門(mén)操作運(yùn)算符，根據(jù)類型轉(zhuǎn)換前后數(shù)據(jù)長(zhǎng)短確定是擴(kuò)展還是截?cái)鄶U(kuò)展：短轉(zhuǎn)長(zhǎng)無(wú)符號(hào)數(shù)：0擴(kuò)展，前面補(bǔ)0帶符號(hào)整數(shù)：符號(hào)擴(kuò)展，前面補(bǔ)符截?cái)啵洪L(zhǎng)轉(zhuǎn)短

強(qiáng)行將高位丟棄，故可能發(fā)生“溢出”例1（擴(kuò)展操作）：在大端機(jī)上輸出si,usi,i,ui的十進(jìn)制和十六進(jìn)制值是什么？shortsi=-32768;unsignedshortusi=si;inti=si;unsingned

ui=usi;si=-327688000usi=327688000i=-32768FFFF8000ui=3276800008000例2（截?cái)嗖僮鳎篿和j是否相等？inti=32768;shortsi=(short)i;intj=si;不相等！i=3276800008000si=-327688000j=-32768FFFF8000原因：對(duì)i截?cái)鄷r(shí)發(fā)生了“溢出”，即：32768截?cái)酁?6位數(shù)時(shí)，因其超出16位能表示的最大值，故無(wú)法截?cái)酁檎_的16位數(shù)！如何實(shí)現(xiàn)高級(jí)語(yǔ)言源程序中的運(yùn)算？總結(jié)：C語(yǔ)言程序中的基本數(shù)據(jù)類型及其基本運(yùn)算類型基本數(shù)據(jù)類型無(wú)符號(hào)數(shù)、帶符號(hào)整數(shù)、浮點(diǎn)數(shù)、位串、字符（串）基本運(yùn)算類型算術(shù)、按位、邏輯、移位、擴(kuò)展和截?cái)?、匹配?jì)算機(jī)如何實(shí)現(xiàn)高級(jí)語(yǔ)言程序中的運(yùn)算？將各類表達(dá)式編譯（轉(zhuǎn)換）為指令序列計(jì)算機(jī)直接執(zhí)行指令來(lái)完成運(yùn)算例：C語(yǔ)言賦值語(yǔ)句“f=(g+h)–(i+j);”中變量i、j、f、g、h由編譯器分別分配給MIPS寄存器$t0~$t4。寄存器$t0~$t7的編號(hào)對(duì)應(yīng)8~15，上述程序段對(duì)應(yīng)的MIPS機(jī)器代碼和匯編表示（#后為注釋）如下：00000001011

011000110100000100000add$t5,$t3,$t4#g+h00000001000010010111000000100000add$t6,$t0,$t1#i+j00000001101011100101000000100010sub$t2,$t5,$t6#f=(g+h)–(i+j)下面以MIPS為例，看指令中會(huì)提供哪些運(yùn)算？能否完全支持高級(jí)語(yǔ)言需求？MIPS定點(diǎn)算術(shù)運(yùn)算指令I(lǐng)nstruction Example Meaning Commentsadd add$1,$2,$3 $1=$2+$3 3operands;exceptionpossiblesubtract sub$1,$2,$3 $1=$2–$3 3operands;exceptionpossibleaddimmediate addi$1,$2,100 $1=$2+100 +constant;exceptionpossibleaddunsigned addu$1,$2,$3 $1=$2+$3 3operands;noexceptionssubtractunsigned subu$1,$2,$3 $1=$2–$3 3operands;noexceptionsaddimm.unsign. addiu$1,$2,100 $1=$2+100 +constant;noexceptionsmultiply mult$2,$3 Hi,Lo=$2x$3 64-bitsignedproductmultiplyunsigned multu$2,$3 Hi,Lo=$2x$3 64-bitunsignedproductdivide div$2,$3 Lo=$2÷$3, Lo=quotient,Hi=remainder Hi=$2mod$3divideunsigned divu$2,$3 Lo=$2÷$3, Unsignedquotient&remainder Hi=$2mod$3涉及到的操作數(shù)：32/16位無(wú)符號(hào)數(shù)，32/16位帶符號(hào)整數(shù)涉及到的操作：（帶符號(hào)整數(shù)/無(wú)符號(hào)數(shù)）加/減/乘/除問(wèn)題：IA-32指令如何區(qū)分無(wú)符號(hào)數(shù)加（減）法和帶符號(hào)數(shù)加（減）法？例如，若(AH)=A0H,(BH)=7EH,則ADDAH,BH的值為多少？

無(wú)符：160+126=30（循環(huán)隊(duì)列指針時(shí)正確）；帶符：-96+126=30（正確）硬件不區(qū)分，由軟件處理。問(wèn)題：為什么加減運(yùn)算可以不區(qū)分無(wú)符和帶符數(shù)，而乘除運(yùn)算一定要區(qū)分？MIPS邏輯運(yùn)算指令涉及到的操作數(shù)：32/16位邏輯數(shù)（位串）涉及到的操作：按位與/按位或/按位或非/左移/右移MIPS定點(diǎn)比較和分支指令涉及到的操作數(shù)：32/16位無(wú)符號(hào)數(shù)，32/16位帶符號(hào)整數(shù)涉及到的操作：大小比較和相等比較（帶符號(hào)/無(wú)符號(hào)）通過(guò)減法運(yùn)算實(shí)現(xiàn)“比較”操作!MIPS定點(diǎn)數(shù)據(jù)傳送指令涉及到的操作數(shù)：32/16位帶符號(hào)整數(shù)（偏移量可以是負(fù)數(shù)）涉及到的操作：加/減/符號(hào)擴(kuò)展/0擴(kuò)展問(wèn)題：IA-32指令如何區(qū)分裝入/存儲(chǔ)？如何區(qū)分傳送不同寬度數(shù)據(jù)？

體會(huì)不同ISA的不同做法，以比較各自的優(yōu)缺點(diǎn)！

如果你來(lái)設(shè)計(jì)一臺(tái)機(jī)器時(shí)，你也可以有你的做法！MIPS中的浮點(diǎn)算術(shù)運(yùn)算指令涉及到的浮點(diǎn)操作數(shù)：32位單精度/64位雙精度浮點(diǎn)數(shù)涉及到的浮點(diǎn)操作：加/減/乘/除

MIPS提供專門(mén)的浮點(diǎn)數(shù)寄存器：32個(gè)32位單精度浮點(diǎn)數(shù)寄存器：$f0,$f1,……,$f31連續(xù)兩個(gè)寄存器（一偶一奇）存放一個(gè)雙精度浮點(diǎn)數(shù)MIPS中的浮點(diǎn)數(shù)傳送指令涉及到的浮點(diǎn)操作數(shù)：32位單精度浮點(diǎn)數(shù)涉及到的浮點(diǎn)操作：傳送操作（與定點(diǎn)傳送一樣）還涉及到定點(diǎn)操作：加/減（用于地址運(yùn)算）例：將兩個(gè)浮點(diǎn)數(shù)從內(nèi)存取出相加后再存到內(nèi)存的指令序列為：

lwc1$f1,x($s1)lwc1$f2,y($s2)

add.s$f4,$f1,$f2swc1$f4,z(s3)MIPS中的浮點(diǎn)數(shù)比較和分支指令涉及到的浮點(diǎn)操作數(shù)：32位單精度浮點(diǎn)數(shù)/64位雙精度浮點(diǎn)數(shù)涉及到的浮點(diǎn)操作：比較操作（用

減法來(lái)實(shí)現(xiàn)比較）還涉及到的定點(diǎn)操作：加/減（用于地址運(yùn)算）

有一個(gè)專門(mén)的浮點(diǎn)標(biāo)志cond，無(wú)需在指令中明顯給出condMIPS指令考察的結(jié)果涉及到的操作數(shù)：無(wú)符號(hào)整數(shù)、帶符號(hào)整數(shù)邏輯數(shù)（位串）浮點(diǎn)數(shù)涉及到的運(yùn)算定點(diǎn)數(shù)運(yùn)算帶符號(hào)整數(shù)運(yùn)算：取負(fù)/符號(hào)擴(kuò)展/加/減/乘/除/算術(shù)移位無(wú)符號(hào)數(shù)運(yùn)算：0擴(kuò)展/加/減/乘/除邏輯運(yùn)算邏輯操作：與/或/非/…移位操作：邏輯左移/邏輯右移浮點(diǎn)數(shù)運(yùn)算：加、減、乘、除實(shí)現(xiàn)MIPS定點(diǎn)和浮點(diǎn)運(yùn)算指令的思路：先實(shí)現(xiàn)一個(gè)能進(jìn)行基本算術(shù)運(yùn)算（加/減）和基本邏輯運(yùn)算，并生成基本條件碼（ZF/OF/CF/NF）的ALU，再由ALU和移位器實(shí)現(xiàn)乘、除、浮點(diǎn)運(yùn)算器。ALU是運(yùn)算部件的核心！以下介紹ALU的實(shí)現(xiàn)。完全能夠支持高級(jí)語(yǔ)言對(duì)運(yùn)算的需求?。?wèn)題：計(jì)算機(jī)是如何實(shí)現(xiàn)各種運(yùn)算功能的？這就是本章后面將要介紹的內(nèi)容！ALU的功能說(shuō)明ALUControlLines(ALUop)Function000 And001 Or010 Add110 Subtract111 Set-on-less-thanALUNNNABResultOverflowZero3ALUopCarryOutALU可進(jìn)行基本的加/減算術(shù)運(yùn)算和邏輯運(yùn)算。其核心部件是加法器。有關(guān)串行加法器和并行加法器的原理在數(shù)字邏輯電路課已講過(guò)，在此僅簡(jiǎn)單回顧?；仡櫍捍羞M(jìn)位加法器假定與/或門(mén)延遲為1ty，異或門(mén)3ty，則“和”與“進(jìn)位”的延遲為多少？FA全加器符號(hào)：串行加法器的缺點(diǎn)：進(jìn)位按串行方式傳遞，速度慢！問(wèn)題：n位串行加法器從C0到Cn的延遲時(shí)間為多少？最后一位和數(shù)的延遲時(shí)間為多少？2n+1級(jí)門(mén)延遲！2n級(jí)門(mén)延遲！Sum延遲為6ty；Carryout延遲為2ty。FAFAFAn位串行(行波)加法器：C0Cn回顧：并行進(jìn)位加法器（CLA加法器）為什么用先行進(jìn)位方式？串行進(jìn)位加法器采用串行逐級(jí)傳遞進(jìn)位，電路延遲與位數(shù)成正比關(guān)系。

因此，現(xiàn)代計(jì)算機(jī)采用一種先行進(jìn)位(Carrylookahead)方式。如何產(chǎn)生先行進(jìn)位？定義輔助函數(shù)：Gi=AiBi…進(jìn)位生成函數(shù)Pi=Ai+Bi…進(jìn)位傳遞函數(shù)（或Pi=Ai⊕Bi

）

通常把實(shí)現(xiàn)上述邏輯的電路稱為進(jìn)位生成/傳遞部件

全加邏輯方程：Si=Pi⊕CiCi+1=Gi+PiCi

(i=0,1,…n)

設(shè)n=4,則：C1=G0+P0C0C2=G1+P1C1=G1+P1G0+P1P0C0

C3=G2+P2C2=G2+P2G1+P2P1G0+P2P1P0C0

C4=G3+P3C3=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0由上式可知:各進(jìn)位之間無(wú)等待，相互獨(dú)立并同時(shí)產(chǎn)生。通常把實(shí)現(xiàn)上述邏輯的電路稱為4位CLA部件由此，根據(jù)Si=Pi⊕Ci，可并行求出各位和。通常把實(shí)現(xiàn)Si=Pi⊕Ci的電路稱為求和部件CLA加法器由“進(jìn)位生成/傳遞部件”、“CLA部件”和“求和部件”構(gòu)成。

回顧：8位全先行進(jìn)位加法器進(jìn)位生成/傳遞部件A7A0B7B0P7P1P0G7G1G08位CLA部件C0求和部件P7P1P0C0C1C7C8S7S0S11ty(或3ty)2ty3ty和的總延遲多少？進(jìn)位C8的延遲多少？和的總延遲：1+2+3=6ty；進(jìn)位C8的延遲：1+2=3tyPi=Ai+Bi------1ty

Pi=Ai⊕Bi----3ty回顧：局部（單級(jí)）先行進(jìn)位加法器問(wèn)題：所有和數(shù)產(chǎn)生的延遲為多少？或稱單級(jí)先行進(jìn)位加法器3+2+2+5=12ty

多級(jí)先行進(jìn)位加法器單級(jí)(局部)先行進(jìn)位加法器的進(jìn)位生成方式：“組內(nèi)并行、組間串行”所以，單級(jí)先行進(jìn)位加法器雖然比行波加法器延遲時(shí)間短，但高位組進(jìn)位依賴低位組進(jìn)位，故仍有較長(zhǎng)的時(shí)間延遲通過(guò)引入組進(jìn)位生成/傳遞函數(shù)實(shí)現(xiàn)“組內(nèi)并行、組間并行”進(jìn)位方式設(shè)n=4,則：C1=G0+P0C0C2=G1+P1C1=G1+P1G0+P1P0C0

C3=G2+P2C2=G2+P2G1+P2P1G0+P2P1P0C0

G3*=G3+P3C3=G3+P3G2+P3P2G1+P3P2P1G0

P3*=P3P2P1P0所以C4=G3*+P3*C0。把實(shí)現(xiàn)上述邏輯的電路稱為4位BCLA部件。回顧：多級(jí)先行進(jìn)位加法器回顧：多級(jí)先行進(jìn)位加法器關(guān)鍵路徑長(zhǎng)度為多少？最終進(jìn)位的延遲為多少？4位成組先行進(jìn)位部件（4位BCLA部件）4位CLA加法器4位CLA加法器4位CLA加法器4位CLA加法器16位兩級(jí)先行進(jìn)位加法器3+2+3=8ty3+2=5tyA4-bitALU

1-bitALU 4-bit串行ALUABFACarryOutMuxCarryInResultA0B01-bitALUResult0CarryIn0CarryOut0A1B11-bitALUResult1CarryIn1CarryOut1A2B21-bitALUResult2CarryIn2CarryOut2A3B31-bitALUResult3CarryIn3CarryOut3MUX是什么？（數(shù)字電路課學(xué)過(guò)）關(guān)鍵路徑延遲長(zhǎng)，速度慢！2ALUop先行進(jìn)位ALU先行進(jìn)位ALU

芯片（SN74181）四位ALU芯片，中規(guī)模集成電路。在先行進(jìn)位加法器基礎(chǔ)上附加部分線路，具有基本的算術(shù)運(yùn)算和邏輯運(yùn)算功能。SN74181的邏輯圖和功能表SN74182是4位BCLA(成組先行進(jìn)位)芯片。多芯片級(jí)聯(lián)構(gòu)成先行進(jìn)位ALU（用于專用場(chǎng)合，如教學(xué)機(jī)等）1個(gè)SN74181芯片直接構(gòu)成一個(gè)4位全先行進(jìn)位ALU4個(gè)SN74181芯片串行構(gòu)成一個(gè)16位單級(jí)先行進(jìn)位ALU4個(gè)SN74181芯片與1個(gè)SN74182芯片可構(gòu)成16位兩級(jí)先行進(jìn)位ALU16個(gè)SN74181芯片與5個(gè)SN74182芯片可構(gòu)成64位先行進(jìn)位ALU現(xiàn)代主流計(jì)算機(jī)中ALU是否通過(guò)芯片級(jí)聯(lián)而成？SKIPALU的“加”運(yùn)算電路相當(dāng)于n檔二進(jìn)制加法算盤(pán)。所有其他運(yùn)算都以ALU中“加”運(yùn)算為基礎(chǔ)！無(wú)需芯片級(jí)聯(lián)！一個(gè)CPU芯片中有多個(gè)處理器核，一個(gè)核中有多個(gè)ALU!回顧：SN74181的引腳輸入端：Ai和Bi分別為第1和2操作數(shù)，Cn為低位進(jìn)位，M為功能選擇線，Si為操作選擇線，共4位，故最多有16種運(yùn)算。輸出端：Fi為運(yùn)算結(jié)果，Cn+4、P和G為進(jìn)位，“A=B”為相等標(biāo)志P輸入端輸出端回顧：SN74181正邏輯功能表BACK回顧：SN74182芯片的引腳輸入端：Pi和Gi分別為第i組的組內(nèi)進(jìn)位傳遞函數(shù)和進(jìn)位生成函數(shù)，Cn為低位進(jìn)位。輸出端：Cn+4、Cn+8、Cn+12為相應(yīng)組的組內(nèi)進(jìn)位，P*和G*分別為整個(gè)大組的組進(jìn)位傳遞函數(shù)和進(jìn)位生成函數(shù)。SN74182芯片的邏輯電路圖BACKSN74181和SN74182組成16位先行進(jìn)位ALU4位ALU4位ALU4位ALU4位ALU16位兩級(jí)先行進(jìn)位ALUBACK例：實(shí)現(xiàn)某11條MIPS指令的ALU在第6章CPU設(shè)計(jì)時(shí)詳細(xì)介紹！第一講小結(jié)高級(jí)語(yǔ)言程序中涉及的運(yùn)算（C語(yǔ)言為例）整數(shù)算術(shù)運(yùn)算、浮點(diǎn)數(shù)算術(shù)運(yùn)算按位、邏輯、移位、位擴(kuò)展和位截?cái)嘀噶罴信c運(yùn)算相關(guān)的指令（MIPS為例）涉及到的定點(diǎn)數(shù)運(yùn)算算術(shù)運(yùn)算帶符號(hào)整數(shù)：取負(fù)、符號(hào)擴(kuò)展、加、減、乘、除、算術(shù)移位無(wú)符號(hào)數(shù)：0擴(kuò)展、加、減、乘、除邏輯運(yùn)算邏輯操作：與、或、非…移位操作：邏輯左移、邏輯右移涉及到的浮點(diǎn)數(shù)運(yùn)算：加、減、乘、除基本運(yùn)算部件ALU的設(shè)計(jì)全加器、串行加法器、先行進(jìn)位加法器串行ALU、先行進(jìn)位ALU（單級(jí)/多級(jí)）MSI芯片級(jí)聯(lián)、直接做在CPU芯片內(nèi)定點(diǎn)運(yùn)算:無(wú)符號(hào)數(shù)

按位邏輯運(yùn)算邏輯移位運(yùn)算位擴(kuò)展和截?cái)噙\(yùn)算加/減/乘/除運(yùn)算帶符號(hào)整數(shù)

算術(shù)移位運(yùn)算擴(kuò)展運(yùn)算和截?cái)噙\(yùn)算

補(bǔ)碼加/減/乘/除運(yùn)算浮點(diǎn)運(yùn)算:

原碼加/減/乘/除運(yùn)算

移碼加/減運(yùn)算是一種模運(yùn)算系統(tǒng)！下一講開(kāi)始介紹上述這些運(yùn)算算法及其運(yùn)算電路需求轉(zhuǎn)換需求轉(zhuǎn)換CPU中需提供哪些運(yùn)算？Why？第二講：定點(diǎn)數(shù)運(yùn)算及運(yùn)算部件主要內(nèi)容加/減運(yùn)算及其運(yùn)算部件補(bǔ)碼/原碼/移碼加減運(yùn)算乘法運(yùn)算及其運(yùn)算部件原碼/補(bǔ)碼乘法運(yùn)算快速乘法器除法運(yùn)算及其運(yùn)算部件原碼/補(bǔ)碼除法運(yùn)算快速除法器定點(diǎn)運(yùn)算器十進(jìn)制加減運(yùn)算注：無(wú)符號(hào)數(shù)的按位邏輯運(yùn)算可用邏輯門(mén)電路實(shí)現(xiàn)；無(wú)符號(hào)數(shù)的邏輯移位運(yùn)算可用專門(mén)的移位器或斜送結(jié)果等多種方式來(lái)實(shí)現(xiàn)；帶符號(hào)數(shù)的算術(shù)移位運(yùn)算、無(wú)符號(hào)數(shù)和帶符號(hào)整數(shù)的位擴(kuò)展運(yùn)算和截?cái)噙\(yùn)算也可用簡(jiǎn)單電路很容易地實(shí)現(xiàn)。為什么無(wú)需移碼乘、除運(yùn)算？補(bǔ)碼加/減運(yùn)算及其部件補(bǔ)碼加減運(yùn)算公式[A+B]補(bǔ)

=[A]補(bǔ)

+[B]補(bǔ)

(MOD2n)[A–B]補(bǔ)

=[A]補(bǔ)

+[–B]補(bǔ)

(MOD2n)補(bǔ)碼加減運(yùn)算要點(diǎn)和運(yùn)算部件加、減法運(yùn)算統(tǒng)一采用加法來(lái)處理符號(hào)位(最高有效位MSB)和數(shù)值位一起參與運(yùn)算直接用Adder實(shí)現(xiàn)兩個(gè)數(shù)的加運(yùn)算（模運(yùn)算系統(tǒng)）

問(wèn)題：模是多少？運(yùn)算結(jié)果高位丟棄，保留低n位，相當(dāng)于取模2n

實(shí)現(xiàn)減法的主要工作在于：求[–B]補(bǔ)問(wèn)題：如何求[–B]補(bǔ)？[–B]補(bǔ)=B+1SumAdder444AZeroCinCout4B401MuxSelSubBoverflow整數(shù)加/減運(yùn)算部件當(dāng)控制端Sub為1時(shí)，做減法當(dāng)控制端Sub為0時(shí)，做加法問(wèn)題：Adder中執(zhí)行的是什么運(yùn)算？相當(dāng)于無(wú)符號(hào)數(shù)加！B＇條件標(biāo)志位（條件碼CC）

除Zero(ZF)、Overflow(OF)，還有進(jìn)/借位(CF)、符號(hào)(SF)標(biāo)志。條件標(biāo)志（Flag）在運(yùn)算電路中產(chǎn)生，被記錄到專門(mén)的寄存器中，以便在分支指令中被用來(lái)作為條件。存放標(biāo)志的寄存器通常稱為程序/狀態(tài)字寄存器或標(biāo)志寄存器。每個(gè)標(biāo)志對(duì)應(yīng)標(biāo)志寄存器中的一個(gè)標(biāo)志位。

如，IA-32中的EFLAGS寄存器SumAdder444AZeroCinCout4B401MuxSelSubBoverflow整數(shù)加/減運(yùn)算部件SFCF問(wèn)題：OF=？ZF=？SF=？CF=？OF：若A與B’同號(hào)但與Sum不同號(hào)，則1；否則0。SF：sum符號(hào)ZF：如Sum為0，則1，否則0。CF：Cout

subB＇這就是計(jì)算機(jī)中的算盤(pán)。所有其他運(yùn)算都基于整數(shù)加/減運(yùn)算器來(lái)實(shí)現(xiàn)。標(biāo)志信息是干什么的？Ex1:-7-6=-7+(-6)=+3-3-5=-3+(-5)=-8

9-6=3

13-5=811++00011110011101111000100011Ex2:用8位機(jī)器數(shù)計(jì)算107+46=？結(jié)果錯(cuò)誤:107+46=-103.進(jìn)位是真正的符號(hào)：+15311溢出現(xiàn)象：(1)最高位和次高位的進(jìn)位不同(2)和的符號(hào)位和加數(shù)的符號(hào)位不同X√10710=0110101124610=001011102

0

10011001溢出標(biāo)志OF=1、零標(biāo)志ZF=0、符號(hào)標(biāo)志SF=1、進(jìn)位標(biāo)志CF=0做減法以比較大小，規(guī)則：Unsigned:CF=0時(shí)，大于Signed：OFNF=0時(shí)，大于OF=0、ZF=0、SF=1、借位CF=0OF=1ZF=0SF=0借位CF=0√√例子：程序的機(jī)器級(jí)表示與執(zhí)行例：

floatsum(inta[],unsigned

len){

inti，sum=0;for(i=0;i<=len–1;i++) sum+=a[i];returnsum;}當(dāng)參數(shù)len為0時(shí)，返回值應(yīng)該是0，但是在機(jī)器上執(zhí)行時(shí)，卻發(fā)生了存儲(chǔ)器訪問(wèn)異常。

Why?i在EAX中，len在EDX中EAX:0000……0000EDX:0000……0000subl

指令的執(zhí)行結(jié)果是什么？cmpl

指令的執(zhí)行結(jié)果是什么？subl$1,%edx指令的執(zhí)行結(jié)果“subl$1,%edx”執(zhí)行時(shí)：A=00000000H，B為00000001H，Sub=1，因此Result是32個(gè)1。Result加法器nnnAZFCiConBn01多路選擇器SubBOF加/減運(yùn)算部件CF=CoSubSF當(dāng)Sub為1時(shí)，做減法當(dāng)Sub為0時(shí)，做加法已知EDX中為len=0000……0000Hcpml%edx,%eax指令的執(zhí)行結(jié)果“cmpl%edx,%eax”執(zhí)行時(shí)：A=00000000H，B為FFFFFFFFH，Sub=1，因此Result是0…01,CF=1,ZF=0,OF=0,SF=0

Result加法器nnnAZFCiConBn01多路選擇器SubBOF加/減運(yùn)算部件CF=CoSubSF當(dāng)Sub為1時(shí)，做減法當(dāng)Sub為0時(shí)，做加法已知EDX中為len-1=FFFF……FFFFH

EAX中為i=0000……0000Hjb.L3指令的執(zhí)行結(jié)果指令轉(zhuǎn)移條件說(shuō)明JA/JNBElabelCF=0ANDZF=0無(wú)符號(hào)數(shù)A＞BJAE/JNBlabelCF=0ORZF=1無(wú)符號(hào)數(shù)A≥BJB/JNAElabelCF=1ANDZF=0無(wú)符號(hào)數(shù)A＜BJBE/JNAlabelCF=1ORZF=1無(wú)符號(hào)數(shù)A≤BJG/JNLElabelSF=OFANDZF=0有符號(hào)數(shù)A＞BJGE/JNLlabelSF=OFORZF=1有符號(hào)數(shù)A≥BJL/JNGElabelSF≠OFANDZF=0有符號(hào)數(shù)A＜BJLE/JNGlabelSF≠OFORZF=1有符號(hào)數(shù)A≤B“cmpl%edx,%eax”執(zhí)行結(jié)果是CF=1,ZF=0,OF=0,SF=0，說(shuō)明滿足條件，應(yīng)轉(zhuǎn)移到.L3執(zhí)行！顯然，對(duì)于每個(gè)i都滿足條件，因?yàn)槿魏螣o(wú)符號(hào)數(shù)都比32個(gè)1小，因此循環(huán)體被不斷執(zhí)行，最終導(dǎo)致數(shù)組訪問(wèn)越界而發(fā)生存儲(chǔ)器訪問(wèn)異常。例子：程序的機(jī)器級(jí)表示與執(zhí)行正確的做法是將參數(shù)len聲明為int型。

Why?len在EAX中，i在M[EBP-4]中i:0000……0000len:0000……0000subl

指令的執(zhí)行結(jié)果是什么？cmpl

指令的執(zhí)行結(jié)果是什么？例：

floatsum(inta[],int

len){

inti，sum=0;for(i=0;i<=len–1;i++) sum+=a[i];returnsum;}subl$1,%eax指令的執(zhí)行結(jié)果“subl$1,%eax”執(zhí)行時(shí)：A=00000000H，B為00000001H，Sub=1，因此Result是32個(gè)1。Result加法器nnnAZFCiConBn01多路選擇器SubBOF加/減運(yùn)算部件CF=CoSubSF當(dāng)Sub為1時(shí)，做減法當(dāng)Sub為0時(shí)，做加法已知EAX中為len=0000……0000Hcpml-4(%ebp),%eax指令的執(zhí)行結(jié)果“cmpl-4(%ebp),%eax”執(zhí)行時(shí)A=FFFFFFFFH，B為00000000H，Sub=1，因此Result是1…11,CF=0,ZF=0,OF=0,SF=1Result加法器nnnAZFCiConBn01多路選擇器SubBOF加/減運(yùn)算部件CF=CoSubSF當(dāng)Sub為1時(shí)，做減法當(dāng)Sub為0時(shí)，做加法已知M[EBP-4]為i=0000……0000H

EAX中為len-1=FFFF……FFFFHjg.L3指令的執(zhí)行結(jié)果指令轉(zhuǎn)移條件說(shuō)明JA/JNBElabelCF=0ANDZF=0無(wú)符號(hào)數(shù)A＞BJAE/JNBlabelCF=0ORZF=1無(wú)符號(hào)數(shù)A≥BJB/JNAElabelCF=1ANDZF=0無(wú)符號(hào)數(shù)A＜BJBE/JNAlabelCF=1ORZF=1無(wú)符號(hào)數(shù)A≤BJG/JNLElabelSF=OFANDZF=0有符號(hào)數(shù)A＞BJGE/JNLlabelSF=OFORZF=1有符號(hào)數(shù)A≥BJL/JNGElabelSF≠OFANDZF=0有符號(hào)數(shù)A＜BJLE/JNGlabelSF≠OFORZF=1有符號(hào)數(shù)A≤B“cmpl-4(%ebp),%eax”執(zhí)行結(jié)果是CF=0,

ZF=0,OF=0,SF=1

，說(shuō)明不滿足條件，應(yīng)跳出循環(huán)執(zhí)行，執(zhí)行結(jié)果正常。原碼加/減運(yùn)算（（自學(xué)，不作要求）用于浮點(diǎn)數(shù)尾數(shù)運(yùn)算符號(hào)位和數(shù)值部分分開(kāi)處理僅對(duì)數(shù)值部分進(jìn)行加減運(yùn)算，符號(hào)位起判斷和控制作用規(guī)則如下：比較兩數(shù)符號(hào)，對(duì)加法實(shí)行“同號(hào)求和，異號(hào)求差”，對(duì)減法實(shí)行“異號(hào)求和，同號(hào)求差”。求和：數(shù)值位相加，和的符號(hào)取被加數(shù)（被減數(shù)）的符號(hào)。若最高位產(chǎn)生進(jìn)位，則結(jié)果溢出。求差：被加數(shù)（被減數(shù)）加上加數(shù)（減數(shù)）的補(bǔ)碼。最高數(shù)值位產(chǎn)生進(jìn)位表明加法結(jié)果為正，所得數(shù)值位正確。最高數(shù)值位沒(méi)產(chǎn)生進(jìn)位表明加法結(jié)果為負(fù)，得到的是數(shù)值位的補(bǔ)碼形式，需對(duì)結(jié)果求補(bǔ)，還原為絕對(duì)值形式的數(shù)值位。差的符號(hào)位：a)情況下，符號(hào)位取被加數(shù)（被減數(shù)）的符號(hào)；

b)情況下，符號(hào)位為被加數(shù)（被減數(shù)）的符號(hào)取反。原碼加/減運(yùn)算（自學(xué)，不作要求）例1：已知[X]原

=1.0011，[Y]原

=1.1010，要求計(jì)算[X+Y]原解：由原碼加減運(yùn)算規(guī)則知：同號(hào)相加，則求和，和的符號(hào)同被加數(shù)符號(hào)。所以：和的數(shù)值位為：0011+1010=1101（ALU中無(wú)符號(hào)數(shù)相加）和的符號(hào)位為：1

[X+Y]原

=1.1101例2：已知[X]原

=1.0011，[Y]原

=1.1010，要求計(jì)算[X–Y]原

解：由原碼加減運(yùn)算規(guī)則知：同號(hào)相減，則求差（補(bǔ)碼減法）

差的數(shù)值位為：0011+(1010)求補(bǔ)

=0011+0110=1001

最高數(shù)值位沒(méi)有產(chǎn)生進(jìn)位，表明加法結(jié)果為負(fù)，需對(duì)1001求補(bǔ)，還原為絕對(duì)值形式的數(shù)值位。即：(1001)補(bǔ)=0111差的符號(hào)位為[X]原的符號(hào)位取反，即：0

[X–Y]原

=0.0111思考題：如何設(shè)計(jì)一個(gè)基于加法器的原碼加/減法器？求和：直接加，有進(jìn)位則溢出，符號(hào)同被求差：加補(bǔ)碼，不會(huì)溢出，符號(hào)分情況移碼加/減運(yùn)算（自學(xué)，不作要求）用于浮點(diǎn)數(shù)階碼運(yùn)算符號(hào)位和數(shù)值部分可以一起處理運(yùn)算公式（假定在一個(gè)n位ALU中進(jìn)行加法運(yùn)算）

[E1]移+[E2]移=2n-1+E1+2n-1+E2=2n+E1+E2=[E1+E2]補(bǔ)（mod2n）

[E1]移–[E2]移=[E1]移+[–[E2]移]補(bǔ)=2n-1+E1+2n–[E2]移

=2n-1+E1+2n–2n-1–E2=2n+E1–E2=[E1–E2]補(bǔ)（mod2n）

結(jié)論：移碼的和、差等于和、差的補(bǔ)碼！運(yùn)算規(guī)則①加法：直接將[E1]移和[E2]移進(jìn)行模2n加，然后對(duì)結(jié)果的符號(hào)取反。②減法：先將減數(shù)[E2]移求補(bǔ)（各位取反，末位加1），然后再與被減數(shù)[E1]移進(jìn)行模2n相加，最后對(duì)結(jié)果的符號(hào)取反。③溢出判斷：進(jìn)行模2n相加時(shí)，如果兩個(gè)加數(shù)的符號(hào)相同，并且與和數(shù)的符號(hào)也相同，則發(fā)生溢出。補(bǔ)碼和移碼的關(guān)系：符號(hào)位相反、數(shù)值位相同！移碼加/減運(yùn)算（不作要求）例1：用四位移碼計(jì)算“–7+（–6）”和“–3+6”的值。解：[–7]移

=0001[–6]移=0010 [–3]移=0101 [6]移=1110[–7]移+[–6]移

=0001+0010=0011（兩個(gè)加數(shù)與結(jié)果符號(hào)都為0，溢出）[–3]移

+[6]移

=0101+1110=0011，符號(hào)取反后為1011，其真值為+3

問(wèn)題：[–7+(–6)]移=?[–3+(6)]移

=？

例2：用四位移碼計(jì)算“–7–（–6）”和“–3–5”的值。解：[–7]移

=0001[–6]移=0010 [–3]移=0101 [5]移=1101 [–7]移

–[–6]移

=0001+1110=1111，符號(hào)取反后為0111，其真值為–1。[–3]移

–[5]移

=0101+0011=1000，符號(hào)取反后為0000，其真值為–8。思考題：如何設(shè)計(jì)一個(gè)基于加法器的移碼加/減法器？在補(bǔ)碼加/減法器結(jié)果的最高位（MSB）加一個(gè)反相器！無(wú)符號(hào)數(shù)的乘法運(yùn)算Paperandpencilexample: Multiplicand1000

Multiplierx1001

1000

0000

0000

1000Product(積)0.1001000假定：[X]原=x0.x1xn，[Y]原=y0.y1yn

，求[x×Y]原數(shù)值部分z1z2n=(0.x1xn)×(0.y1yn)(小數(shù)點(diǎn)位置約定，不區(qū)分小數(shù)還是整數(shù))X×y4×2-4X×y3×2-3X×y2×2-2X×y1×2-1

4X×Y=(X×yi×2-i)i=1整個(gè)運(yùn)算過(guò)程中用到兩種操作：加法+左移因而，可用ALU和移位器來(lái)實(shí)現(xiàn)乘法運(yùn)算n=4無(wú)符號(hào)數(shù)的乘法運(yùn)算手工乘法的特點(diǎn)：每步計(jì)算：X×yi，若yi=0，則得0；若yi=1，則得X把①求得的各項(xiàng)結(jié)果X×yi

逐次左移，可表示為X×yi×2-i

對(duì)②中結(jié)果求和，即

(X×yi×2-i)，這就是兩個(gè)無(wú)符號(hào)數(shù)的乘積計(jì)算機(jī)內(nèi)部稍作以下改進(jìn)：每次得X×yi后，與前面所得結(jié)果累加，得到Pi，稱之為部分積。因?yàn)椴坏鹊阶詈笠淮吻蠛?，減少了保存各次相乘結(jié)果X×yi的開(kāi)銷。每次得X×yi后，不將它左移與前次部分積Pi相加，而將部分積Pi右移后與X×yi相加。因?yàn)榧臃ㄟ\(yùn)算始終對(duì)部分積中高n位進(jìn)行。故用n位加法器可實(shí)現(xiàn)二個(gè)n位數(shù)相乘。對(duì)乘數(shù)中為“1”的位執(zhí)行加法和右移，對(duì)為“0”的位只執(zhí)行右移，而不執(zhí)行加法運(yùn)算。無(wú)符號(hào)乘法運(yùn)算的算法推導(dǎo)上述思想可寫(xiě)成如下數(shù)學(xué)推導(dǎo)過(guò)程： X×Y=X×(0.y1y2…yn) =X×y1×2-1+X×y2×2-2+……+X×yn-1×2-(n-1)+X×yn×2-n

=2-n×X×yn+2-(n-1)×

X×yn-1+……+2-2×X×y2+2-1×X×y1=2-1(2-1(2-1…2-1(2-1(0+X×yn)+X×yn-1)+……+X×y2)+X×y1)n個(gè)2-1上述推導(dǎo)過(guò)程具有明顯的遞歸性質(zhì)，因此，無(wú)符號(hào)數(shù)乘法過(guò)程可歸結(jié)為循環(huán)計(jì)算下列算式的過(guò)程：設(shè)P0=0，每步的乘積為：

P1=2-1(P0+X×yn)P2=2-1(P1+X×yn-1)…………

Pn=2-1(Pn-1+X×y1)其遞推公式為：Pi+1=2-1(Pi+X×yn-i)(i=0,1,2,3,…,n-1)最終乘積Pn=X×Y迭代過(guò)程從乘數(shù)最低位yn和P0=0開(kāi)始，經(jīng)n次“判斷–加法–右移”循環(huán)，直到求出Pn為止。寫(xiě)使能控制邏輯右移32位ALU被乘數(shù)寄存器X乘積寄存器P3264位323232加計(jì)數(shù)器Cn時(shí)鐘C乘數(shù)寄存器Y32位乘法運(yùn)算的硬件實(shí)現(xiàn)被乘數(shù)寄存器X：存放被乘數(shù)乘積寄存器P：開(kāi)始置初始部分積P0=0；結(jié)束時(shí)，存放的是64位乘積的高32位乘數(shù)寄存器Y：開(kāi)始時(shí)置乘數(shù)；結(jié)束時(shí)，存放的是64位乘積的低32位進(jìn)位觸發(fā)器C：保存加法器的進(jìn)位信號(hào)循環(huán)次數(shù)計(jì)數(shù)器Cn：存放循環(huán)次數(shù)。初值32，每循環(huán)一次，Cn減1，Cn=0時(shí)結(jié)束ALU：乘法核心部件。在控制邏輯控制下，對(duì)P和X的內(nèi)容“加”，在“寫(xiě)使能”控制下運(yùn)算結(jié)果被送回P，進(jìn)位位在C中每次循環(huán)都要對(duì)進(jìn)位位C、乘積寄存器P和乘數(shù)寄存器實(shí)現(xiàn)同步邏輯“右移”

Example：無(wú)符號(hào)整數(shù)乘法運(yùn)算舉例說(shuō)明：若需計(jì)算z=x*y;x、y和z都是unsigned類型。設(shè)x=1110y=1101應(yīng)用遞推公式：Pi=2-1(x*yi+Pi-1)C乘積P乘數(shù)R000001101+1110011101101001110110000111011+1110100011011010001101+1110101101101010110110可用一個(gè)雙倍字長(zhǎng)的乘積寄存器；也可用兩個(gè)單倍字長(zhǎng)的寄存器。部分積初始為0。保留進(jìn)位位。右移時(shí)進(jìn)位、部分積和剩余乘數(shù)一起進(jìn)行邏輯右移。驗(yàn)證：x=14,y=13,z=x*y=182當(dāng)z取4位時(shí)，結(jié)果發(fā)生溢出，因?yàn)楦?位不為全0！原碼乘法算法用于浮點(diǎn)數(shù)尾數(shù)乘運(yùn)算符號(hào)與數(shù)值分開(kāi)處理：積符異或得到，數(shù)值用無(wú)符號(hào)乘法運(yùn)算例：設(shè)[x]原=0.1110，[y]原=1.1101，計(jì)算[x×y]原

解：數(shù)值部分用無(wú)符號(hào)數(shù)乘法算法計(jì)算：1110×1101=10110110符號(hào)位：01=1，所以：[x×y]原=1.10110110原碼一位乘法：每次只取乘數(shù)的一位判斷，需n次循環(huán)，速度慢。原碼兩位乘法：每次取乘數(shù)兩位判斷，只需n/2次循環(huán)，快一倍。原碼兩位乘法遞推公式：00：Pi+1=2-2Pi

01：Pi+1=2-2(Pi+X)10：Pi+1=2-2(Pi+2X)11：Pi+1=2-2(Pi+3X)=2-2(Pi+4X-X)=2-2(Pi-X)+Xyi-1

yi

T操作迭代公式0000010100111001011101110T+X0T+X0T+2X0T+2X0T–X1T–X1T1T

2-2(Pi)2-2(Pi+X)2-2(Pi+X)2-2(Pi+2X)2-2(Pi+2X)2-2(Pi–X)2-2(Pi–X)2-2(Pi

)T觸發(fā)器用來(lái)記錄下次是否要執(zhí)行“+X”“–X”運(yùn)算用“+[-X]補(bǔ)”實(shí)現(xiàn)！3X時(shí)，本次-X，下次+X！部分積右移兩位，相當(dāng)于4XP.94表3.3原碼兩位乘法舉例（自學(xué)，不作要求）已知[X]原=0.111001，[Y]原=0.100111，用原碼兩位乘法計(jì)算[X×Y]原解：先用無(wú)符號(hào)數(shù)乘法計(jì)算111001×100111，原碼兩位乘法過(guò)程如下：若用模4補(bǔ)碼，則P和Y同時(shí)右移2位時(shí)，得到的P3是負(fù)數(shù)，這顯然是錯(cuò)誤的！需要再增加一位符號(hào)。采用補(bǔ)碼算術(shù)右移，與一位乘法不同，Why？為模8補(bǔ)碼形式(三位符號(hào)位)，Why？速度快，但代價(jià)也大補(bǔ)碼乘法運(yùn)算（自學(xué)，不作要求）用于對(duì)什么類型數(shù)據(jù)計(jì)算？帶符號(hào)整數(shù)！如int型假定：[X]補(bǔ)=xn-1xn-2……

x1x0，

[Y]補(bǔ)=yn-1yn-2……

y1y0，求：[XxY]補(bǔ)=？基于以下補(bǔ)碼性質(zhì)：

Y=-yn-1.2n-1+yn-2.2n-2+

……

y1.21+

y0.20令：y-1

=0，則：當(dāng)n=32時(shí)，Y=-y31.231+y30.230+

……

y1.21+

y0.20

+

y-1.20

-y31.231+(y30.231-y30.230)+……+(y0.21-y0.20)+y-1.20

(y30-y31).231+(y29-y30).230+……+(y0–y1).21+(y-1-y0).20

部分積公式：Pi=2-1(Pi-1+

(yi-1-yi)X)Booth’sAlgorithm推導(dǎo)如下：因?yàn)閇XxY]補(bǔ)

[X]補(bǔ)x[Y]補(bǔ)，故不能直接用無(wú)符號(hào)數(shù)乘法計(jì)算。例如，若x=-5,求x*x=？2-32.[XxY]補(bǔ)=

(y30-y31)X.2-1+(y29-y30)X.2-2+……+(y0–y1)X.2-31+(y-1-y0)X.2-32=

2-1(2-1…(2-1(y-1-y0)X)+

(y0–y1)X)+…+

(y30-y31)X)符號(hào)與數(shù)值統(tǒng)一處理SKIP如何求補(bǔ)碼的真值（自學(xué)，不作要求）根據(jù)補(bǔ)碼各位上的“權(quán)”，可以求出一個(gè)補(bǔ)碼的值真值范圍：

令：[A]補(bǔ)=an-1an-2……

a1a0則：A=-an-1.2n-1+an-2.2n-2+

……

a1.21+

a0.20

符號(hào)為0，則為正數(shù)，數(shù)值部分同符號(hào)為1，則為負(fù)數(shù)，數(shù)值各位取反，末位加1例如：補(bǔ)碼“11010110”的真值為：-0101010=-(32+8+2)=-42BACKBooth’s算法實(shí)質(zhì)（自學(xué)，不作要求）當(dāng)前位

右邊位 操作 Example 1 0 減被乘數(shù) 0001111000 1 1 加0(不操作) 0001111000 0 1 加被乘數(shù) 0001111000 0 0 加0(不操作) 0001111000在“1串”中，第一個(gè)1時(shí)做減法，最后一個(gè)1做加法，其余情況只要移位。最初提出這種想法是因?yàn)樵贐ooth的機(jī)器上移位操作比加法更快！同前面算法一樣，將乘積寄存器右移一位。（這里是算術(shù)右移）0

1111

0beginningofrunendofrunmiddleofrun布斯算法舉例（自學(xué)，不作要求）已知[X]補(bǔ)

=1101，[Y]補(bǔ)

=0110，計(jì)算[X×Y]補(bǔ)

驗(yàn)證：當(dāng)X×Y取8位時(shí)，結(jié)果-0010010B=-18；為4位時(shí)，結(jié)果溢出！[-X]補(bǔ)

=00111111X

=-3，Y

=6，X×Y=-18，[X×Y]補(bǔ)應(yīng)等于11101110或結(jié)果溢出

如何判斷結(jié)果是否溢出？高4位是否全為符號(hào)位！補(bǔ)碼兩位乘法（自學(xué)，不作要求）補(bǔ)碼兩位乘可用布斯算法推導(dǎo)如下：[Pi+1]補(bǔ)

=2-1([Pi]補(bǔ)

+(yi-1–yi)[X]補(bǔ))[Pi+2]補(bǔ)

=2-1([Pi+1]補(bǔ)

+(yi–yi+1)[X]補(bǔ))=2-1(2-1([Pi]補(bǔ)

+(yi-1–yi)[X]補(bǔ))+(yi–yi+1)[X]補(bǔ))=2-2([Pi]補(bǔ)+(yi-1+yi–2yi+1)[X]補(bǔ))開(kāi)始置附加位y-1為0，乘積寄存器最高位前面添加一位附加符號(hào)位0。最終的乘積高位部分在乘積寄存器P中，低位部分在乘數(shù)寄存器Y中。因?yàn)樽珠L(zhǎng)總是8的倍數(shù)，所以補(bǔ)碼的位數(shù)n應(yīng)該是偶數(shù)，因此，總循環(huán)次數(shù)為n/2。yi+1

yi

yi-1操作迭代公式0000010100111001011101110+[X]補(bǔ)+[X]補(bǔ)+2[X]補(bǔ)+2[-X]

補(bǔ)+[-X]補(bǔ)+[-X]補(bǔ)02-2[Pi]補(bǔ)2-2{[Pi]補(bǔ)+[X]補(bǔ)}2-2{[Pi]補(bǔ)+[X]補(bǔ)}2-2{[Pi]補(bǔ)+2[X]補(bǔ)}2-2{[Pi]補(bǔ)+2[-X]補(bǔ)}2-2{[Pi]補(bǔ)+[-X]補(bǔ)}2-2{[Pi]補(bǔ)+[-X]補(bǔ)}2-2[Pi]補(bǔ)補(bǔ)碼兩位乘法舉例（自學(xué)，不作要求）已知[X]補(bǔ)

=1101，[Y]補(bǔ)

=0110，用補(bǔ)碼兩位乘法計(jì)算[X×Y]補(bǔ)。解：[–X]補(bǔ)=0011，用補(bǔ)碼二位乘法計(jì)算[X×Y]補(bǔ)的過(guò)程如下。

PnPYy-1

說(shuō)明

0000001100

開(kāi)始，設(shè)y-1=0，[P0]補(bǔ)

=0+00110y1y0y-1=100，+2[-X]補(bǔ)00110P和Y同時(shí)右移二位0000110011得[P2]補(bǔ)+11010y3y2y1=011，+2[X]補(bǔ)11011P和Y同時(shí)右移二位111101110得[P4]補(bǔ)因此[X×Y]補(bǔ)=11101110

，與一位補(bǔ)碼乘法（布斯乘法）所得結(jié)果相同，但循環(huán)次數(shù)減少了一半。驗(yàn)證：-3×6=-18（-10010B）22快速乘法器（自學(xué)，不作要求）前面介紹的乘法部件的特點(diǎn)通過(guò)一個(gè)ALU多次做“加/減+右移”來(lái)實(shí)現(xiàn)一位乘法：約n次“加+右移”兩位乘法：約n/2次“加+右移”所需時(shí)間隨位數(shù)增多而加長(zhǎng)，由時(shí)鐘和控制電路控制設(shè)計(jì)快速乘法部件的必要性大約1/3是乘法運(yùn)算快速乘法器的實(shí)現(xiàn)（由特定功能的組合邏輯單元構(gòu)成）流水線方式硬件疊加方式（如：陣列乘法器）流水線方式的快速乘法器（自學(xué)，不作要求）為乘數(shù)的每位提供一個(gè)n位加法器每個(gè)加法器的兩個(gè)輸入端分別是：本次乘數(shù)對(duì)應(yīng)的位與被乘數(shù)相與的結(jié)果（即：0或被乘數(shù)）上次部分積每個(gè)加法器的輸出分為兩部分：和的最低有效位(LSB)作為本位乘積進(jìn)位和高31位的和數(shù)組成一個(gè)32位數(shù)作為本次部分積1組合邏輯電路！無(wú)需控制器控制陣列乘法器的實(shí)現(xiàn)（自學(xué)，不作要求）手算乘法過(guò)程陣列乘法器全加器被乘數(shù)X部分積輸入AiBi進(jìn)位輸入進(jìn)位輸出

部分積輸出B00P7P6P5P4P3P2P1P0B10B20B30A3A2A1A00000速度僅取決于邏輯門(mén)和加法器的傳輸延遲

無(wú)符號(hào)陣列乘法器增加符號(hào)處理電路、乘前及乘后求補(bǔ)電路，即可實(shí)現(xiàn)帶符號(hào)數(shù)乘法器。Divide:Paper&Pencil

1001 Quotient(商)Divisor1000

1001010 Dividend(被除數(shù))

-1000

10

101

1010

-1000

10 Remainder(余數(shù))手算除法的基本要點(diǎn)①被除數(shù)與除數(shù)相減，夠減則上商為1；不夠減則上商為0。②每次得到的差為中間余數(shù)，將除數(shù)右移后與上次的中間余數(shù)比較。用中間余數(shù)減除數(shù)，夠減則上商為1；不夠減則上商為0。③重復(fù)執(zhí)行第②步，直到求得的商的位數(shù)足夠?yàn)橹?。中間余數(shù)定點(diǎn)除法運(yùn)算除前預(yù)處理①若被除數(shù)=0且除數(shù)≠0，或定點(diǎn)整數(shù)除法時(shí)|被除數(shù)|<|除數(shù)|，則商為0，不再繼續(xù)②若被除數(shù)≠0、除數(shù)=0，則發(fā)生“除數(shù)為0”異常③若被除數(shù)和除數(shù)都為0，則有些機(jī)器產(chǎn)生一個(gè)不發(fā)信號(hào)的NaN，即“quietNaN”

當(dāng)被除數(shù)和除數(shù)都≠

0，且商≠

0時(shí)，才進(jìn)一步進(jìn)行除法運(yùn)算。計(jì)算機(jī)內(nèi)部無(wú)符號(hào)數(shù)除法運(yùn)算與手算一樣，通過(guò)被除數(shù)（中間余數(shù)）減除數(shù)來(lái)得到每一位商

夠減上商1；不夠減上商0（從msb→lsb得到各位商）基本操作為減法和移位，故可與乘法合用同一套硬件兩個(gè)n位數(shù)相除的情況：(1)定點(diǎn)正整數(shù)（即無(wú)符號(hào)數(shù)）相除：在被除數(shù)的高位添n個(gè)0(2)定點(diǎn)正小數(shù)（即原碼小數(shù)）相除：在被除數(shù)的低位添加n個(gè)0

這樣，就將所有情況都統(tǒng)一為：一個(gè)2n位數(shù)除以一個(gè)n位數(shù)第一次試商為1時(shí)的情況問(wèn)題：第一次試商為1，說(shuō)明什么？若是2n位除以n位的無(wú)符號(hào)整數(shù)運(yùn)算，則說(shuō)明將會(huì)得到多于n+1位的商，因而結(jié)果“溢出”（即：無(wú)法用n位表示商）。若是兩個(gè)n位數(shù)相除，則第一位商為0，且肯定不會(huì)溢出，為什么？若是浮點(diǎn)數(shù)中尾數(shù)原碼小數(shù)運(yùn)算，第一次試商為1，則說(shuō)明尾數(shù)部分有“溢出”，可通過(guò)浮點(diǎn)數(shù)的“右規(guī)”消除“溢出”。所以，在浮點(diǎn)數(shù)運(yùn)算器中，第一次得到的商“1”要保留。最大商為:00001111/0001=1111商有n+1位數(shù)，因而溢出！例：0.11110000/0.1000=+1.1110例：11111111/1111=10001無(wú)符號(hào)數(shù)除法算法的硬件實(shí)現(xiàn)除數(shù)寄存器Y：存放除數(shù)。余數(shù)寄存器R：初始時(shí)高位部分為高32位被除數(shù)；結(jié)束時(shí)是余數(shù)。余數(shù)/商寄存器Q：初始時(shí)為低32位被除數(shù)；結(jié)束時(shí)是32位商。循環(huán)次數(shù)計(jì)數(shù)器Cn：存放循環(huán)次數(shù)。初值是32，每循環(huán)一次，Cn減1，當(dāng)Cn=0時(shí)，除法運(yùn)算結(jié)束。ALU：除法核心部件。在控制邏輯控制下，對(duì)于寄存器R和Y的內(nèi)容進(jìn)行“加/減”運(yùn)算，在“寫(xiě)使能”控制下運(yùn)算結(jié)果被送回寄存器R。

R和Q同步“左移”，Q空出位上“商”，商的各位逐次左移到Q中。由控制邏輯根據(jù)ALU結(jié)果的符號(hào)決定商為0還是1。減----試商，加----恢復(fù)余數(shù)。DivideAlgorithmexample

D:0010 R:00000111ShlR D:0010 R:00001110R=R–D D:0010 R:11101110+D,slR,0 D:0010 R:00011100R=R–D D:0010R:11111100+D,slR,0 D:0010 R:00111000R=R–D D:0010 R:00011000slR,1D:0010 R:00110001R=R–DD:0010R:00010001slR,1 D:0010 R:00100011Shr

R(rh) D:0010 R:00010011驗(yàn)證：7/2=3余1從例子可看出：每次上商為0時(shí)，需做加法以“恢復(fù)余數(shù)”。所以，稱為“恢復(fù)余數(shù)法也可在下一步運(yùn)算時(shí)把當(dāng)前多減的除數(shù)補(bǔ)回來(lái)。這種方法稱為“不恢復(fù)余數(shù)法”，又稱“加減交替法”。–D=1110

開(kāi)始余數(shù)先左移了一位，故最后余數(shù)需向右移一位。這里是兩個(gè)n位無(wú)符號(hào)數(shù)相除，肯定不會(huì)溢出，故余數(shù)先左移而省略判斷溢出過(guò)程。不恢復(fù)余數(shù)除法(加減交替法)根據(jù)恢復(fù)余數(shù)法(設(shè)B為除數(shù)，Ri為第i次中間余數(shù))，有：若Ri<0,則商上“0”，并做加法恢復(fù)余數(shù)，即：Ri+1=2(Ri+2n|B|)-2n|B|=2Ri

+

2n|B|

(“負(fù)，０，加”)若Ri>=0,則商上“1”，不需恢復(fù)余數(shù)，即：Ri+1=2Ri

-

2n|B|

(“正，１，減”)省去了恢復(fù)余數(shù)的過(guò)程注意：最后一次上商為“0”的話，需要“糾余”處理，即把試商時(shí)被減掉的除數(shù)加回去，恢復(fù)真正的余數(shù)。不恢復(fù)余數(shù)法也稱為加減交替法恢復(fù)余數(shù)法可進(jìn)一步簡(jiǎn)化為“加減交替法”帶符號(hào)數(shù)除法原碼除法商符和商值分開(kāi)處理商的數(shù)值部分由無(wú)符號(hào)數(shù)除法求得商符由被除數(shù)和除數(shù)的符號(hào)確定：同號(hào)為0，異號(hào)為１余數(shù)的符號(hào)同被除數(shù)的符號(hào)補(bǔ)碼除法方法1：同原碼除法一樣，先轉(zhuǎn)換為正數(shù)，先用無(wú)符號(hào)數(shù)除法，然后修正商和余數(shù)。方法2：直接用補(bǔ)碼除法，符號(hào)和數(shù)值一起進(jìn)行運(yùn)算，商符直接在運(yùn)算中產(chǎn)生。兩個(gè)n位補(bǔ)碼整數(shù)除法運(yùn)算，被除數(shù)需要進(jìn)行符號(hào)擴(kuò)展。若被除數(shù)為2n位，除數(shù)為n位，則被除數(shù)無(wú)需擴(kuò)展。原碼除法舉例已知[X]原

=0.1011[Y]原

=1.1101用恢復(fù)余數(shù)法計(jì)算[X/Y]原解：商的符號(hào)位：01=1

減法操作用補(bǔ)碼加法實(shí)現(xiàn)，是否夠減通過(guò)中間余數(shù)的符號(hào)來(lái)判斷，所以中間余數(shù)要加一位符號(hào)位。

[|X|]補(bǔ)

=0.1011[|Y|]補(bǔ)

=0.1101[–|Y|]補(bǔ)

=1.0011小數(shù)在低位擴(kuò)展0思考：若實(shí)現(xiàn)無(wú)符號(hào)數(shù)相除，即1011除以1101，則有何不同？結(jié)果是什么？被除數(shù)高位補(bǔ)0，1011除以1101，結(jié)果等于0用于判斷是否溢出若求[Y/X]原結(jié)果如何？原碼除法舉例已知[X]原

=0.1011[Y]原

=1.1101用加減交替法計(jì)算[X/Y]原解：[|X|]補(bǔ)

=0.1011[|Y|]補(bǔ)

=0.1101[–|Y|]補(bǔ)

=1.0011

“加減交替法”的要點(diǎn)：負(fù)、0、加正、1、減得到的結(jié)果與恢復(fù)余數(shù)法一樣！問(wèn)題：用被除數(shù)（中間余數(shù)）減除數(shù)試商時(shí)，怎樣確定是否“夠減”？中間余數(shù)的符號(hào)?。ㄕ龜?shù)-正數(shù)）補(bǔ)碼除法能否這樣來(lái)判斷呢？不能，因?yàn)榉?hào)可能不同！補(bǔ)碼除法（自學(xué)，不作要求）補(bǔ)碼除法判斷是否“夠減”的規(guī)則（1）當(dāng)被除數(shù)（或中間余數(shù)）與除數(shù)同號(hào)時(shí)，做減法，若新余數(shù)的符號(hào)與除數(shù)符號(hào)一致表示夠減，否則為不夠減；（2）當(dāng)被除數(shù)（或中間余數(shù)）與除數(shù)異號(hào)時(shí)，做加法，若得到的新余數(shù)的符號(hào)與除數(shù)符號(hào)一致表示不夠減，否則為夠減。中間余數(shù)R的符號(hào)除數(shù)Y的符號(hào)同號(hào)：新中間余數(shù)=R–Y（同號(hào)為正商）異號(hào)：新中間余數(shù)=R+Y（異號(hào)為負(fù)商）010100110