有一個芯片能做8位除以4位的計算(無符號)。請利用上8位除以4位
這個結果(商和餘數)完成16位除以8位的計算(無符號)。寫出算法即可。

假設有乘法器。

解：

設被除數是B3*2^12 + B2*2^8 + B1*2^4 + B0
設除數是A1*2^4 + A0
Ai,Bi 都是4位2進制數。A1,A0都不是零。所有的數都用符號量值表示。

(1)討論 A1*2^4 + A0 除 B3*2^12 + B2*2^8
為了用8位除以4位結果
先討論 A1*2^4 除 B3*2^12 + B2*2^8 = A1 除 ( B3*2^4 + B2 )2^4

根據假定，A1 除 ( B3*2^4 + B2 )，商為Q2，餘數為R2。
從而，

( B3*2^4 + B2 )2^8 = (A1*2^4)*Q2*2^4 + R2*2^8
也就是說，當前的商是 Q2*2^4，把它放到累加累減商寄存器中。

考慮到除數的另一部分 A0，總餘數為
-A0*Q2*2^4 + R2*2^8 + B1*2^4 + B0
無論正負，總餘數的絕對值比被除數小。

(2)討論 A1*2^4 + A0 除 (1)的總餘數。
應用類似的過程，得到商Q1 和 更小的總餘數。
把商Q1 累加累減到商寄存器中。

......

(N)當總餘數的絕對值是8位數的時候，假定是C1*2^4 + C0 且符號為正
討論 A1*2^4 + A0 除 C1*2^4 + C0
用 A1*2^4 除 C1*2^4 = A1 除 C1。這是8位除以4位的特殊形式。

根據假定，A1 除 C1，商為Q0，餘數為R0。
這樣，
C1*2^4 = (A1*2^4)*Q0 + R0*2^4
也就是說，當前的商是 Q0，把它放到累加累減商寄存器中。
考慮到除數的另一部分 A0，總餘數為
-A0*Q0 + R0*2^4 + C0

當總餘數的絕對值小於A1*2^4 + A0的時候，如果總餘數大於等於零，這個
總餘數就是結果餘數，商寄存器中的數就是商。如果總餘數小於零，商寄
存器減1，結果餘數 = 總餘數 + A1*2^4 + A0，商寄存器中的數就是商。