《DJ10第3章-算術(shù)邏輯運(yùn)算基礎(chǔ).ppt》由會員分享，可在線閱讀，更多相關(guān)《DJ10第3章-算術(shù)邏輯運(yùn)算基礎(chǔ).ppt（30頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

3 3 3定點(diǎn)乘法運(yùn)算 2 補(bǔ)碼一位乘法 1 算法分析X補(bǔ) X0 X1X2 Xn Y為正 Y補(bǔ) 0 Y1Y2 Yn XY 補(bǔ) X補(bǔ) 0 Y1Y2 Yn Y為負(fù) Y補(bǔ) 1 Y1Y2 Yn XY 補(bǔ) X補(bǔ) 0 Y1Y2 Yn X 補(bǔ) 證明 2 對于定點(diǎn)小數(shù) Y 補(bǔ) 2 Y 1 Y1Y2 Yn 則Y Y 補(bǔ) 2 1 0 Y1Y2 Yn 2 0 Y1Y2 Yn 1 所以 X Y X 0 Y1Y2 Yn 1 X 0 Y1Y2 Yn X 則 X Y 補(bǔ) X 0 Y1Y2 Yn X 補(bǔ) X 0 Y1Y2 Yn 補(bǔ) X 補(bǔ) X 補(bǔ) 0 Y1Y2 Yn 補(bǔ) X 補(bǔ) 因?yàn)?0 Y1Y2 Yn 0 所以 X Y 補(bǔ) X 補(bǔ) 0 Y1Y2 Yn X 補(bǔ) 將 和 結(jié)合起來 有如下的 式 Y符號任意 XY 補(bǔ) X補(bǔ) 0 Y1Y2 Yn X 補(bǔ)Y0 符號位 展開為部分積的累加和形式 X補(bǔ) 0 Y1Y2 Yn X補(bǔ)Y0 X補(bǔ) Y0 2 1Y1 2 2Y2 2 nYn X補(bǔ) Y1 Y0 2 1 Y2 Y1 2 2 Y3 Y2 2 n 0 Yn XY 補(bǔ) X補(bǔ) 0 Y1Y2 Yn X 補(bǔ)Y0 X補(bǔ) Y0 Y1 2 1Y1 2 1Y2 2 2Y2 2 n 1 Yn 2 nYn 0 XY 補(bǔ) X補(bǔ) Y1 Y0 2 1 Y2 Y1 2 2 Y3 Y2 2 n Yn 1 Yn 在機(jī)器實(shí)現(xiàn)中可在末位Yn之后再增設(shè)一個附加位Yn 1 其初始值為0 對乘數(shù)Y的值并無影響 若定義 A0 補(bǔ)為初始部分積 A1 補(bǔ) An 補(bǔ)依次為各步求得的累加和并且右移后的部分積 則可將上式改寫為如下遞推形式 它更接近于乘法的分步運(yùn)算形式 A0 補(bǔ) 0 A1 補(bǔ) 2 1 A0 補(bǔ) Yn 1 Yn X 補(bǔ) A2 補(bǔ) 2 1 A1 補(bǔ) Yn Yn 1 X 補(bǔ) An 補(bǔ) 2 1 An 1 補(bǔ) Y2 Y1 X 補(bǔ) XY 補(bǔ) An 補(bǔ) Y1 Y0 X 補(bǔ)上式表明補(bǔ)碼一位乘的基本操作 被乘數(shù)X補(bǔ)乘以對應(yīng)的相鄰兩位乘數(shù)之差值 再與原部分積累加 然后右移一位 形成該步的部分積累加和 比較法 用乘數(shù)的相鄰兩位比較 低位減高位 的結(jié)果決定部分積 當(dāng)Yi 1 Yi 1 X補(bǔ)當(dāng)Yi 1 Yi 1 X補(bǔ)當(dāng)Yi 1 Yi 0 0 2 比較法算法 3 運(yùn)算實(shí)例X 0 1101 Y 0 1011 求 XY 補(bǔ) 初值 A 00 0000 B X補(bǔ) 11 0011 B X 補(bǔ) 00 1101 C Y補(bǔ) 1 0101 步數(shù)條件操作ACCnCn 1 00 0000 1 10 B 00 1101 00 1101 00 0110 11 0101 2 01 B 11 0011 11 1001 11 1100 111 010 3 10 B 00 1101 00 1001 00 0100 1111 01 4 01 B 11 0011 CnCn 1 1 01010 XY 補(bǔ) 0 10001111 不再移位 4 運(yùn)算規(guī)則 A B取雙符號位 符號參加運(yùn)算 C取單符號位 符號參加移位 以決定最后是否修正 C末位設(shè)置附加位Cn 1 初值為0 CnCn 1組成判斷位 決定運(yùn)算操作 作n步循環(huán) 若需作第n 1步 則不移位 僅修正 因?yàn)樗惴?XY 補(bǔ) X補(bǔ) Y1 Y0 2 1 Y2 Y1 An 補(bǔ) Y1 Y0 X 補(bǔ) 即 第n 1次是 Y1與Y0 的比較 該項(xiàng)沒有權(quán)值 不需要移位 當(dāng)Y1 Y0時 無需與X補(bǔ)相乘 因此 在第n步完成后 如果Y1 Y0 不需要作第n 1步 當(dāng)Y1 Y0 作 B或 B 即修正 但不移位 即有 1 0 B修正0 1 B修正0 0 不修正1 1 不修正 乘法運(yùn)算學(xué)習(xí)思路 三個步驟 1 從運(yùn)算的定義和性質(zhì)推導(dǎo)出由計(jì)算機(jī)實(shí)現(xiàn)的算法 2 由實(shí)例演示和驗(yàn)證該算法 3 歸納總結(jié)計(jì)算機(jī)實(shí)現(xiàn)該算法的規(guī)則 3 3 4定點(diǎn)除法運(yùn)算 除法的步驟 余數(shù)與除數(shù)加減 移位 例 0 10110 0 11111 0 10110 1101 0 11111 0 11111 0 0 11111 10101 0 11111 1011 0 0 1 0 1 1 0 0 00000 商 0 10110余數(shù) 0 10110 2 5 實(shí)現(xiàn)除法的關(guān)鍵 比較余數(shù) 除數(shù)絕對值大小 決定如何上商 可以推演出以下三種可由機(jī)器實(shí)現(xiàn)方法 比較法比較余數(shù)與除數(shù)的大小 夠減則做減法 并商1 不夠減則不做減法 并商0 不恢復(fù)余數(shù)法先做減法再判斷 不夠減時 通過下一步的加除數(shù)來恢復(fù)余數(shù) 恢復(fù)余數(shù)法先做減法再判斷是否夠減 夠減商1 不夠減商0 并加除數(shù)以恢復(fù)做減法前的余數(shù) 相當(dāng)與取消這一步的減法操作 1 原碼恢復(fù)余數(shù)法 2 余數(shù) 除數(shù) 為正 夠減 商1為負(fù) 不夠減 商0 恢復(fù)原余數(shù) 2 實(shí)例 假設(shè)X Y且 X Y X 0 10110 Y 0 11111 求X Y 給出商Q和余數(shù)R 設(shè)置A 被除數(shù) 余數(shù) B 除數(shù) C 商 初值 A X 00 10110 B Y 00 11111 C Q 0 00000 B 11 00001 比較兩數(shù)大小可用減法試探 1 算法 新余數(shù) 步數(shù)條件操作AC 00 101100 00000 1 0 B 01 01100 11 00001 00 01101 0 00001 2 1 B 00 11010 11 00001 11 11011 0 00010 3 恢復(fù)余數(shù) B 00 11111 00 11010 Cn SA Q1 Q2 r0 2r0 r1 2r1 r2 r2 設(shè)置A 被除數(shù) 余數(shù) B 除數(shù) C 商 步數(shù)條件操作AC 00 10101 5 0 B 01 01010 11 00001 00 01011 0 01011 6 1 B 00 10110 11 00001 11 10111 0 10110 7 恢復(fù)余數(shù) B 00 11111 00 10110 Cn Q4 Q5 Q3 r3 2r3 r4 2r4 r5 r5 01 10100 4 0 B 11 00001 2r2 0 00101 Q 0 10110 R 0 10110 2 5 3 說明 A B雙符號位 對X Y絕對值 X 小于 Y 運(yùn)算結(jié)束后 余數(shù)乘以2 n 與被除數(shù)同號 X Q Y R 2 原碼不恢復(fù)余數(shù)法 加減交替法 1 算法分析 設(shè)Y表示除數(shù) r表示余數(shù) 第i步將余數(shù)左移一位后減除數(shù) 2ri 1 Y 則其上商與下一步操作可能出現(xiàn)兩種情況 夠減 余數(shù)ri 2ri 1 Y 0 商1 Qi 1 下一步作ri 1 2ri Y 2ri Y 即 ri 1 2ri Y 但是 ri 1 2ri Y 2 ri Y Y 不夠減 ri 2ri 1 Y 0 商0 Qi 0 如果恢復(fù)余數(shù) 則ri ri Y 2ri 1 下一步做ri 1 2ri Y 所以 2ri Y與2ri Y等效 ri 1 2 算法 ri為正 則Qi為1 第i 1步作2ri Y ri為負(fù) 則Qi為0 第i 1步作2ri Y 3 實(shí)例 X 0 10110 Y 0 11111 求X Y 給出商Q和余數(shù)R 初值 A X 00 10110 B Y 00 11111 C Q 0 00000 B 補(bǔ) 11 00001 由此可得 ri 1 2ri 1 2Qi Y 步數(shù)條件操作AC 00 101100 00000 1 為正 B 01 01100 11 00001 00 01101 0 00001 2 為負(fù) B 00 11010 11 00001 11 11011 0 00010 3 B 00 11111 11 10110 0 00101 為正 00 10101 Cn Q1 Q2 Q3 r0 2r0 r1 2r1 r2 2r2 r3 4 為正 B 01 01010 11 00001 00 01011 0 01011 Q4 2r3 r4 步數(shù)條件操作AC 00 010110 01011 6 為負(fù) 恢復(fù)余數(shù) B 00 11111 00 10110 Q 0 10110 Cn Q4 r4 5 為正 B 00 10110 11 00001 11 10111 0 10110 Q5 2r4 r5 r5 R 0 10110 2 5 4 4 運(yùn)算規(guī)則 A B取雙符號位 X Y取絕對值運(yùn)算 且 X Y 根據(jù)余數(shù)的正負(fù)決定商值及下一步操作 求n位商 作n步操作 若第n步余數(shù)為負(fù) 則第n 1步恢復(fù)余數(shù) 以保證r 0 不移位 3 補(bǔ)碼不恢復(fù)余數(shù)法 加減交替法 如何上商 如何確定商符 1 判斷是否夠減 X Y 同號相除 夠減 不夠減 夠減 不夠減 夠減 r與X Y同號 不夠減 r與X Y異號 如何判斷是否夠減 r與Y同號 r與Y異號 異號相除 夠減 r與X同號 與Y異號 不夠減 r與X異號 與Y同號 判斷規(guī)則 同號 作X補(bǔ) Y補(bǔ) 夠減 r補(bǔ)與Y補(bǔ)同號 不夠減 r補(bǔ)與Y補(bǔ)異號 異號 作X補(bǔ) Y補(bǔ) 夠減 r補(bǔ)與Y補(bǔ)異號 不夠減 r補(bǔ)與Y補(bǔ)同號 2 求商值 上商規(guī)則 余數(shù)與除數(shù)同號商1 異號商0 余數(shù)的符號 除數(shù)的符號 因?yàn)樯虨樨?fù) 而負(fù)數(shù)的補(bǔ)碼與真值相反 除末位以外 3 算法 ri 1 補(bǔ) 2ri補(bǔ) 1 2Qi補(bǔ) Y補(bǔ) ri補(bǔ)與Y補(bǔ)同號 則Qi補(bǔ)為1 第i 1步作2ri補(bǔ) Y補(bǔ) ri補(bǔ)與Y補(bǔ)異號 則Qi補(bǔ)為0 第i 1步作2ri補(bǔ) Y補(bǔ) 4 求商符 令X補(bǔ) r0補(bǔ) r0補(bǔ)與Y補(bǔ) 同號 Q0補(bǔ) 1異號 Q0補(bǔ) 0 與實(shí)際商符相反 商符 便于與上商規(guī)則統(tǒng)一 除法完成后進(jìn)行修正 5 商的校正 商 余數(shù) 真商 假商 1 000 01 Q0 Q1Q2 Qn 1 求n 1位商 假商 2 n 第n位商 末位商 恒置1 1 商符變反 n位 余數(shù)求至rn 6 實(shí)例 X 0 10110 Y 0 11111 求X Y 給出商Q和余數(shù)R 初值 A X補(bǔ) 00 10110B Y補(bǔ) 11 00001 B 00 11111C Q補(bǔ) 0 00000 步數(shù)條件操作AC 00 101100 0000 1 異號 B 01 01100 11 00001 00 01101 0 0000 Cn 1 r Y Q1 r0 2r0 r1 求商符 Q0 異號 余數(shù)與除數(shù)同號商1 異號商0 2 同號 B 00 11010 11 00001 11 11011 0 0001 Q2 2r1 r2 步數(shù)條件操作AC Cn 1 5 B 11 00001 00 10110 11 10111 3 異號 B 11 10110 00 11111 00 10101 0 0010 4 異號 B 01 01010 11 00001 00 01011 0 0100 2r2 r3 2r3 r4 2r4 r5 Q4 Q3 假商 0 0100 真商 0 0100 1 00001 1 01001 補(bǔ)碼 Q 0 10111R 0 01001 2 5 真值 余數(shù) 11 10111 補(bǔ)碼 7 運(yùn)算規(guī)則 A B取雙符號位 符號參加運(yùn)算 X Y 根據(jù)余數(shù)與除數(shù)的符號決定商值及下一步操作 求n 1位商 作n步操作 求出rn 對商校正 商符變反 第n位商恒置1