Chapter3算術(shù)運(yùn)算Chapter3—ArithmeticforComputers—2算術(shù)運(yùn)算整數(shù)運(yùn)算加減法乘除法溢出處理浮點(diǎn)運(yùn)算浮點(diǎn)表示

操作

§3.1IntroductionChapter3—ArithmeticforComputers—3整數(shù)加法例子:7+6§3.2AdditionandSubtraction結(jié)果超出表示范圍就會發(fā)生溢出(定義)正數(shù)和負(fù)數(shù)相加，不會溢出兩個正數(shù)相加符號位為1，表示發(fā)生溢出兩個負(fù)數(shù)相加符號位為0，表示發(fā)生溢出Chapter3—ArithmeticforComputers—4整數(shù)減法減法：加上加數(shù)的負(fù)值例如:7–6=7+(–6) +7: 00000000…00000111

–6: 11111111…11111010

+1: 00000000…00000001結(jié)果超出范圍就會溢出相同同符號位相減，不會溢出一個負(fù)數(shù)減去一個正數(shù)符號位為0，表示發(fā)生溢出一個正數(shù)減去一個負(fù)數(shù)符號位為1，表示發(fā)生溢出FACiAiBiSiCi+1來自低位的進(jìn)位加數(shù)加數(shù)向高位產(chǎn)生的進(jìn)位和全加器邏輯符號(不考慮進(jìn)位是半加器)輸入輸出AiBiCiCi+1Si0000000101010010111010001101101101011111如何判斷溢出在什么情況下可能產(chǎn)生溢出？例.數(shù)A有4位尾數(shù)，1位符號SA

數(shù)B有4位尾數(shù)，1位符號SB

符號位參加運(yùn)算結(jié)果符號Sf符號位進(jìn)位Cf尾數(shù)最高位進(jìn)位CA:01110B:00111S:1001111正確0001100010（1）A=3B=23+2：00101（2）A=10B=710+7：010100011110001正溢正確負(fù)溢正確正確（3）A=-3B=-2-3+(-2)：110111110111110（4）A=-10B=-7-10+(-7)：011111011011001（5）A=6B=-46+(-4)：000100011011100（6）A=-6B=4-6+4：111101101000100（2）A=10B=710+7：01010

0011110001（4）A=-10B=-7-10+(-7)：0111110110110011.硬件判斷邏輯一（SA、SB與Sf的關(guān)系）溢出=SASBSfSASfSB2.硬件判斷邏輯二（Cf與C的關(guān)系）正確0001100010（1）A=3B=23+2：00101（2）A=10B=710+7：010100011110001正溢正確負(fù)溢正確正確（3）A=-3B=-2-3+(-2)：110111110111110（4）A=-10B=-7-10+(-7)：011111011011001（5）A=6B=-46+(-4)：000100011011100（6）A=-6B=4-6+4：111101101000100Cf=0C=0Cf=0C=1Cf=1C=1Cf=1C=0Cf=1C=1Cf=0C=0111111（2）A=10B=710+7：01010

0011110001（4）A=-10B=-7-10+(-7)：0111110110110011.硬件判斷邏輯一（SA、SB與Sf的關(guān)系）溢出=SASBSfSASfSB2.硬件判斷邏輯二（Cf與C的關(guān)系）溢出=CfC3.硬件判斷邏輯三（雙符號位）（1）3+2：正確00001100001000

0101（2）10+7：001010000111010001正溢正確負(fù)溢正確正確（3）-3+(-2)：110111111101111110（4）-10+(-7)：101111110110111001（5）6+(-4)：000010000110111100（6）-6+4：11

111011

1010000100第一符號位Sf1第二符號位Sf2溢出=Sf1Sf21.硬件判斷邏輯一（SA、SB與Sf的關(guān)系）溢出=SASBSfSASfSB2.硬件判斷邏輯二（Cf與C的關(guān)系）溢出=CfC3.硬件判斷邏輯三（雙符號位）Chapter3—ArithmeticforComputers—13如何處理溢出有些高級語言不處理異常MIPS：addu,addui,subu指令不發(fā)生溢出其他語言(Ada,Fortran)溢出時會發(fā)出異常：使用MIPSadd,addi,sub指令溢出發(fā)生時，發(fā)生異常保存PC指針到EPC(ExcetionProgramCounter)寄存器跳轉(zhuǎn)到異常處理句柄mfc0(movefromcoprocessorreg)指令從EPC中恢復(fù)PC的值Chapter3—ArithmeticforComputers—14多媒體算術(shù)運(yùn)算圖像和媒體計(jì)算一般針對8位或16位的數(shù)據(jù)64位地址，分區(qū)進(jìn)位8×8-bit,4×16-bit,or2×32-bitSIMD(單指令、多數(shù)據(jù))飽和操作溢出時，結(jié)果保持為最大值E.g.,音頻的剪切，視頻中的飽和移位操作邏輯移位

：數(shù)碼位置變化，數(shù)值不變。1.移位類型算術(shù)移位

10001111循環(huán)左移：0：數(shù)碼位置變化，數(shù)值變化,符號位不變。1001111算術(shù)左移：1

001

1111011110(-15)(-30)（1）單符號位：0011101110

（2）雙符號位：001110

0001112.正數(shù)補(bǔ)碼移位規(guī)則（3）移位規(guī)則左移右移右移0011100011左移左移右移右移011100

001110000111數(shù)符不變（單：符號位不變；雙：第一符號位不變）?？瘴谎a(bǔ)0（右移時第二符號位移至尾數(shù)最高位）。（1）單符號位：1101110110

（2）雙符號位：101100

1101103.負(fù)數(shù)補(bǔ)碼移位規(guī)則（3）移位規(guī)則左移右移右移1101111101左移右移右移110110111011數(shù)符不變（單：符號位不變；雙：第一符號位不變）。左移空位補(bǔ)0（第二符號位移至尾數(shù)最高位）。右移空位補(bǔ)13.2.1.4舍入方法1.0舍1入（原碼、補(bǔ)碼）000100原

100101原

111011補(bǔ)

2.末位恒置1（原碼、補(bǔ)碼）000100原

111011補(bǔ)

100101原

00010原

10011原

11110補(bǔ)

00011原

10011原

11101補(bǔ)

10011原

11101補(bǔ)

例.保留4位尾數(shù)：例.保留4位尾數(shù)：Chapter3—ArithmeticforComputers—19乘法1000×10011000000000000001000000

1001000Lengthofproductisthesumofoperandlengths乘積的位數(shù)是乘數(shù)和被乘數(shù)之和Multiplicand被乘數(shù)Multiplier乘數(shù)Product乘積§3.3MultiplicationChapter3—ArithmeticforComputers—20乘法硬件Initially0Chapter3—ArithmeticforComputers—21改進(jìn)后的乘法器操作并行:add/shift一個時鐘完成一次積:頻率較低（1）手算0.1101×0.1011

1101110100001101

0.10001111上符號：1.10001111部分積問題：1）加數(shù)增多（由乘數(shù)位數(shù)決定）。

2）加數(shù)的位數(shù)增多（與被乘數(shù)、乘數(shù)位數(shù)有關(guān)）。改進(jìn)：將一次相加改為分步累加。（2）分步乘法每次將一位乘數(shù)所對應(yīng)的部分積與原部分積的累加和相加，并移位。設(shè)置寄存器：

A：存放部分積累加和、乘積高位

B：存放被乘數(shù)

C：存放乘數(shù)、乘積低位

設(shè)置初值：

A=00.0000B=X=00.1101C=Y=.1011

步數(shù)條件操作AC

00.0000.1011

1）Cn=1+BCn+00.110100.1101

0.1101×0.1011

1101110100001101

0.10001111BC

1101

00.01101.101

0.1101×0.10112）Cn=1+B+00.110101.001100.100111.10

0.1101×0.1011

0.1101×0.1011

1101110100001101

0.10001111BC3）Cn=0+0+00.000000.100100.0100111.14）Cn=1+B+00.110101.000100.10001111X原×Y原=1.10001111圓圈圈起來的是下一步要檢測的為迭代步驟乘數(shù)被乘數(shù)積product0初始值001①000000100000000011:1→積=積+被除數(shù)001100000010000000102：左移被乘數(shù)001100000100000000103：右移乘數(shù)000①000001000000001021:1→積=積+被除數(shù)000100000100000001102：左移被乘數(shù)000100001000000001103：右移乘數(shù)0000000010000000011031:無操作000000001000000001102：左移被乘數(shù)000000010000000001103：右移乘數(shù)0000000100000000011041：無操作000000010000000001102：左移被乘數(shù)000000100000000001103：右移乘數(shù)00000010000000000110Chapter3—ArithmeticforComputers—26快速乘法器使用多個加法器,成本/效率的折衷可以流水執(zhí)行:幾個加法可以同步執(zhí)行（不同的階段）Chapter3—ArithmeticforComputers—27MIPSMultiplication2個32位的寄存器來保存積HI:高32bitsLO:低32-bits指令multrs,rt/multurs,rt64-bitproductinHI/LOmfhird/mflord傳送HI/LO到rd可以檢查HI的值來判斷結(jié)果是否超過32位mulrd,rs,rt低32位存入rd寄存器Chapter3—ArithmeticforComputers—28除法除數(shù)判0除法步驟

除數(shù)≤被除數(shù)商添加1,執(zhí)行減法否則商添加0，從被除數(shù)中提取下一個bit恢復(fù)余數(shù)法直接執(zhí)行減法，結(jié)果小于0后再把除數(shù)加回去帶符號位的除法用絕對值進(jìn)行除根據(jù)需要調(diào)整商和余數(shù)的符號100110001001010-1000101011010-100010n-bit操作產(chǎn)生

n-bit

商和余數(shù)商被除數(shù)余數(shù)除數(shù)§3.4DivisionChapter3—ArithmeticforComputers—29除法器的硬件InitiallydividendInitiallydivisorinlefthalfChapter3—ArithmeticforComputers—30改進(jìn)后的除法器一個時鐘周期做一次減法和乘法器類似乘法和除法可以共用同樣的硬件Chapter3—ArithmeticforComputers—31MIPS除法HI/LO寄存器存儲結(jié)果HI:32位余數(shù)LO:32位商指令divrs,rt/divurs,rt不會溢出和除0檢查如果需要，軟件必須進(jìn)行檢查使用mfhi,mflo指令

訪問結(jié)果Chapter3—ArithmeticforComputers—32浮點(diǎn)數(shù)表達(dá)非整形的數(shù)可以表達(dá)很小和很大的數(shù)和科學(xué)計(jì)數(shù)法類似–2.34×1056+0.002×10–4+987.02×109二進(jìn)制表示±1.xxxxxxx2

×2yyyyC語言中的類型：float和double規(guī)格化非規(guī)格化§3.5FloatingPointChapter3—ArithmeticforComputers—33浮點(diǎn)數(shù)標(biāo)準(zhǔn)IEEE754標(biāo)準(zhǔn)-1985消除表達(dá)的不一致性科學(xué)計(jì)算中的可移植性性現(xiàn)在被普遍采用2種精度單精度(32-bit)雙精度(64-bit)

IEEE-InstituteofElectricalandElectrionicsEngineers電氣電子工程師協(xié)會，1963年1月1日，總部美國紐約Chapter3—ArithmeticforComputers—34IEEE浮點(diǎn)數(shù)標(biāo)準(zhǔn)格式S:符號位(0非負(fù)數(shù),1負(fù)數(shù))有效位的規(guī)格化:1.0≤|有效位|<2.0數(shù)前總有一個前導(dǎo)的1，此外作為隱含位可以不表示。有效位是

“1.尾數(shù)”階碼:移碼表示:真實(shí)的指數(shù)+偏移EnsuresexponentisunsignedSingle:偏移=127;Double:偏移=1203S階碼尾數(shù)單精度single:8bits

雙精度double:11bitssingle:23bits

double:52bits移碼的特點(diǎn)（字長8位，偏置值為27=128,注意IEEE的指數(shù)是偏置127）移碼最高位為0表示負(fù)數(shù)，最高位為1表示正數(shù)。移碼直觀反映真值的大小。全0時，所對應(yīng)的真值最??；全1時，所對應(yīng)的真值最大；有利于兩個浮點(diǎn)數(shù)進(jìn)行階碼的大小比較0的移碼表示形式唯一[+0]移=[-0]移=10000000移碼將真值映射到正數(shù)域，可視為無符號數(shù)同一真值的補(bǔ)碼和移碼只相差符號位。2.1數(shù)據(jù)與文字的表示方法Chapter3—ArithmeticforComputers—36單精度浮點(diǎn)數(shù)的范圍階碼00000000和11111111特殊用途最小值階碼:00000001

指數(shù)值=1–127=–126尾數(shù):000…00

有效位=1.0±1.0×2–126≈±1.2×10–38最大值階碼:11111110

指數(shù)值=254–127=+127尾數(shù):111…11

有效位≈2.0±2.0×2+127≈±3.4×10+38IEEE754標(biāo)準(zhǔn)對于階碼為0或255的情況，而IEEE754標(biāo)準(zhǔn)有特別的規(guī)定：階碼是1—254，如果E是0并且M是0，則這個數(shù)的真值為±0（正負(fù)號和數(shù)符位有關(guān)）如果E=255并且M是0，則這個數(shù)的真值為±∞（同樣和符號位有關(guān)）如果E=255并且M不是0，則這不是一個數(shù)（NaN）。短浮點(diǎn)數(shù)和長浮點(diǎn)數(shù)（不含臨時浮點(diǎn)數(shù)）的存儲在尾數(shù)中隱含存儲著一個1，因此在計(jì)算尾數(shù)的真值時比一般形式要多一個整數(shù)1。對于階碼E的存儲形式因?yàn)槭?27的偏移，所以在計(jì)算其移碼時與人們熟悉的128偏移不一樣，正數(shù)的值比用128偏移求得的少1，負(fù)數(shù)的值多1，為避免計(jì)算錯誤，方便理解，常將E當(dāng)成二進(jìn)制真值進(jìn)行存儲。例如：將數(shù)值-0.5按IEEE754單精度格式存儲，先將-0.5換成二進(jìn)制并寫成標(biāo)準(zhǔn)形式：-0.5（10進(jìn)制）=-0.1（2進(jìn)制）=-1.0×2-1（2進(jìn)制，-1是指數(shù)），這里s=1，M為全0，E-127=-1，E=126（10進(jìn)制）=01111110（2進(jìn)制），則存儲形式為：1

01111110000000000000000000000000Chapter3—ArithmeticforComputers—37Chapter3—ArithmeticforComputers—38雙精度浮點(diǎn)數(shù)的范圍階碼0000…00和1111…11特殊用途最小值階碼:

指數(shù)=1–1023=–1022尾數(shù):000…00有效位=1.0±1.0×2–1022≈±2.2×10–308最大值階碼:11111111110

指數(shù)=2046–1023=位數(shù):111…11有效位≈2.0±2.0×2≈±1.8×10+308Chapter3—ArithmeticforComputers—39浮點(diǎn)數(shù)精度相對精度（分辨率）尾數(shù)的每一部分都有意思單精度:大約2–23Equivalentto23×log102≈23×0.3≈7decimaldigitsofprecision雙精度:大約2–52Equivalentto52×log102≈52×0.3≈16decimaldigitsofprecisionChapter3—ArithmeticforComputers—40浮點(diǎn)數(shù)的示例如何表示–0.75–0.75=(–1)1×1.12×2–1S=1尾數(shù)=1000…002階碼=–1+偏移單精度:–1+127=126=011111102雙精度:–1+1023=1022=單精度:1011111101000…008位23位雙精度:11000…00Chapter3—ArithmeticforComputers—41浮點(diǎn)數(shù)的示例計(jì)算下列浮點(diǎn)數(shù)的真值

11000000101000…00S=1尾數(shù)=01000…002階碼=100000012=129x=(–1)1×(1+012)×2(129–127) =(–1)×1.25×22 =–5.0Chapter3—ArithmeticforComputers—42非規(guī)格化的浮點(diǎn)數(shù)階碼=000...0隱含位為0比規(guī)格化的數(shù)要小以較低的精度允許下溢尾數(shù)=000...00.0有兩種表示法!Chapter3—ArithmeticforComputers—43無窮和NaNs階碼=111...1,尾數(shù)=000...0±無窮可以參與計(jì)算階碼=111...1,尾數(shù)≠000...0Not-a-Number(NaN)表示非法或則未定義的結(jié)果e.g.,0.0/0.0可以參與計(jì)算，結(jié)果衡為NaNChapter3—ArithmeticforComputers—44浮點(diǎn)數(shù)加法以一個4位的十進(jìn)制數(shù)為例：9.999×101+1.610×10–11.對階把小階的值調(diào)整到和大階一致(-1調(diào)整到1)9.999×101+0.016×1012.尾數(shù)相加9.999×101+0.016×101=10.015×1013.結(jié)果規(guī)格化&檢查是否溢出1.0015×1024.進(jìn)行必要的舍入處理1.002×102Chapter3—ArithmeticforComputers—45浮點(diǎn)數(shù)加法現(xiàn)在計(jì)算一個4位的二進(jìn)制數(shù)1.0002×2–1+–1.1102×2–2(0.5+–0.4375)1.對接小階對大階1.0002×2–1+–0.1112×2–12.尾數(shù)相加1.0002×2–1+–0.1112×2–1=0.0012×2–13.規(guī)格化&檢查溢出1.0002×2–4,withnoover/underflow4.進(jìn)行必要的舍入1.0002×2–4(nochange)=0.0625Chapter3—ArithmeticforComputers—46浮點(diǎn)加法的硬件實(shí)現(xiàn)比整數(shù)復(fù)雜很多如果在一個時鐘周期內(nèi)完成，就會要求時鐘周期非常的長比整數(shù)運(yùn)算跟費(fèi)時較慢的時鐘會對所有的指令產(chǎn)生影響浮點(diǎn)加法器通常需要花費(fèi)幾個時鐘周期可以被流水化Chapter3—ArithmeticforComputers—47浮點(diǎn)加法Step1Step2Step3Step4Chapter3—ArithmeticforComputers—48浮點(diǎn)乘法以一個4位的十進(jìn)制乘法為例1.110×1010×9.200×10–51.指數(shù)相加如果指數(shù)有偏移，還需要減去多加的偏移值新指數(shù)=10+–5=52.有效位相乘1.110×9.200=10.21210.212×1053.規(guī)格化，同時檢查上溢和下溢1.0212×1064.舍入，可能還需要進(jìn)一步規(guī)格化1.021×1065.計(jì)算符號位+1.021×106Chapter3—ArithmeticforComputers—49浮點(diǎn)乘法下面是一個4位的二進(jìn)制數(shù)的例子1.0002×2–1×–1.1102×2–2(0.5×–0.4375)1.階碼相加無偏移:–1+–2=–3有偏移:(–1+127)+(–2+127)=–3+254–127=–3+1272.有效位相乘1.0002×1.1102=1.11021.1102×2–33.規(guī)格化，同時檢查上溢和下溢1.1102×2–3

無溢出，也不需規(guī)格化4.舍入，可能還需要進(jìn)一步規(guī)格化1.1102×2–3(nochange)5.計(jì)算符號位:+ve×–ve–ve–1.1102×2–3=–0.21875Chapter3—ArithmeticforComputers—50浮點(diǎn)運(yùn)算硬件浮點(diǎn)乘法和加法的硬件復(fù)雜度類似有效位上進(jìn)行乘法而不是加法浮點(diǎn)運(yùn)算通常需要的操作是加法,減法,乘法,除法,求倒數(shù),平方根浮點(diǎn)數(shù)和整數(shù)間的轉(zhuǎn)換通常需要多個時鐘周期很容易用流水實(shí)現(xiàn)流水方式

Chapter3—ArithmeticforComputers—52MIPS中的浮點(diǎn)指令浮點(diǎn)數(shù)使用協(xié)處理器通過ISA相連的附屬處理器獨(dú)立的浮點(diǎn)寄存器32個單精度:$f0,$f1,…$f31配對為雙精度:$f0/$f1,$f2/$f3,…Release2ofMIPsISAsupports32×64-bitFPreg’s浮點(diǎn)指令只操作浮點(diǎn)寄存器程序通常不會在浮點(diǎn)寄存器上進(jìn)行整數(shù)操作，或在整數(shù)寄存器上進(jìn)行浮點(diǎn)操作因此可以提供更多的寄存器，而不影響指令的長度浮點(diǎn)數(shù)讀取、存儲指令lwc1,ldc1,swc1,sdc1e.g.,ldc1$f8,32($sp)Chapter3—ArithmeticforComputers—53MIPS中的浮點(diǎn)指令單精度add.s,sub.s,mul.s,div.se.g.,add.s$f0,$f1,$f6雙精度add.d,sub.d,mul.d,div.de.g.,mul.d$f4,$f4,$f6比較c.xx.s,c.xx.d(xxiseq,lt,le,…)SetsorclearsFPcondition-codebite.g.c.lt.s$f3,$f4分支bc1t,bc1fe.g.,bc1tTargetLabelChapter3—ArithmeticforComputers—54示例:°Fto°CC語言: floatf2c(floatfahr){

return((5.0/9.0)*(fahr-32.0));

}Fahr變量存在$f12,$f0存結(jié)果,常量存在全局共享內(nèi)存編譯后的MIPS指令:

f2c:lwc1$f16,const5($gp)

lwc2$f18,const9($gp)

div.s$f16,$f16,$f18

lwc1$f18,const32($gp)

sub.s$f18,$f12,$f18

mul.s$f0,$f16,$f18

jr$raChapter3—ArithmeticforComputers—55示例:數(shù)組乘法X=X+Y×Z都是32×32矩陣,64-bit雙精度C語言:

voidmm(doublex[][],

doubley[][],doublez[][]){

inti,j,k;

for(i=0;i!=32;i=i+1)

for(j=0;j!=32;j=j+1)

for(k=0;k!=32;k=k+1)

x[i][j]=x[i][j]

+y[i][k]*z[k][j];

}x,y,z指針存儲在$a0,$a1,$a2,

i,j,k在$s0,$s1,$s2中Chapter3—ArithmeticforComputers—56示例:數(shù)組乘法MIPScode:

li$t1,32#$t1=32(rowsize/loopend)

li$s0,0#i=0;initialize1stforloop

L1:li$s1,0#j=0;restart2ndforloop

L2:li$s2,0#k=0;restart3rdforloop

sll$t2,$s0,5#$t2=i*32(sizeofrowofx)

addu$t2,$t2,$s1#$t2=i*size(row)+j

sll$t2,$t2,3#$t2=byteoffsetof[i][j]

addu$t2,$a0,$t2#$t2=byteaddressofx[i][j]

l.d$f4,0($t2)#$f4=8bytesofx[i][j]

L3:sll$t0,$s2,5#$t0=k*32(sizeofrowofz)

addu$t0,$t0,$s1#$t0=k*size(row)+j

sll$t0,$t0,3#$t0=byteoffsetof[k][j]

addu$t0,$a2,$t0#$t0=byteaddressofz[k][j]

l.d$f16,0($t0)#$f16=8bytesofz[k][j]

…Chapter3—ArithmeticforComputers—57示例:數(shù)組乘法…

sll$t0,$s0,5#$t0=i*32(sizeofrowofy)

addu$t0,$t0,$s2#$t0=i*size(row)+k

sll$t0,$t0,3#$t0=byteoffsetof[i][k]

addu$t0,$a1,$t0#$t0=byteaddressofy[i][k]

l.d$f18,0($t0)#$f18=8bytesofy[i][k]

mul.d$f16,$f18,$f16#$f16=y[i][k]*z[k][j]

add.d$f4,$f4,$f16#f4=x[i][j]+y[i][k]*z[k][j]

addiu$s2,$s2,1#$kk+1

bne$s2,$t1,L3#if(k!=32)gotoL3

s.d$f4,0($t2)#x[i][j]=$f4

addiu$s1,$s1,1#$j=j+1

bne$s1,$t1,L2#if(j!=32)gotoL2

addiu$s0,$s0,1#$i=i+1

bne$s0,$t1,L1#if(i!=32)gotoL1Chapter3—ArithmeticforComputers—58精度IEEE754定義了多種舍入控制策略多存儲幾個位(保護(hù),舍入,sticky)可以選擇不同的舍入模式允許程序員微調(diào)計(jì)算中的行為不是所有的硬件都實(shí)現(xiàn)了IEEE754的舍入策略大部分語言和類庫只是用缺省的策略是硬件復(fù)雜度、效率和市場需求的折衷Chapter3—ArithmeticforComputers—59內(nèi)在含義Bits沒有固有的含義由在上面操作的指令決定如何使用計(jì)算機(jī)中數(shù)的表示有限的