DJ10第3章-算術(shù)邏輯運算基礎(chǔ).ppt

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