匯編練習：不會溢出的除法

王爽老師的《匯編語言》在實驗10.2中提出了div指令可能出現(xiàn)的除法溢出的問題负蠕。例如對于16位除以8位的情形敬惦，考慮被除數(shù)是0x1234，除數(shù)是0x01儡首。根據(jù)div的約定蔬胯，商在AL中氛濒，余數(shù)在AH中迈勋。但是顯然計算結果的商是0x1234，8位的AL無法容納，因此會產(chǎn)生除法溢出馍惹。使用Bochs調(diào)試時，會在div之后出現(xiàn)iret窥突，即CPU產(chǎn)生了一個中斷返回指令努溃。
為了兼容32位對16位的除法硫嘶，設計一個雙字除法調(diào)用過程divdw：

輸入：
- 被除數(shù)：一個32位的整數(shù)阻问，高16位在DX中，低16位在AX中
- 除數(shù)：一個16位的整數(shù)沦疾，存儲在CX中
輸出：
- 商：32位的整數(shù)称近，高16位在DX中第队，低16位在AX中
- 余數(shù)：16位整數(shù)，儲存在CX中

因為商也是雙字長刨秆，因此divdw過程一定不會發(fā)生除法溢出凳谦。這是因為，考慮被除數(shù)最大是0xFFFFFFFF衡未，除數(shù)最小是0x0001尸执，則商最大為0xFFFFFFFF，不會超過雙字長缓醋。但是直接使用div指令是無法辦到的如失，所以我們下面需要設計divdw的過程。首先給出一個數(shù)論中關于帶余數(shù)除法的引理：

(帶余數(shù)除法)：設 $a,b$ 是兩個整數(shù)送粱， $b\neq0$ 褪贵，則存在唯一的整數(shù)對 $(p,r)$ ，使得 $a=pb+r\quad (0\leqslant r <|b|)$

我們接下來約定抗俄，符號 $\frac{a}{ b}$ 表示實數(shù)除法脆丁， $\mathrm{int}(\frac{a})$ 表示整數(shù)除法的商动雹，相當于上面的 $p$ 槽卫； $\mathrm{rem}(\frac{a})$ 表示整數(shù)除法的余數(shù)胰蝠，相當于上面的 $r$ 晒夹。例如，對于 $a=7,b=3$ 姊氓，我們有 $\frac{a}{ b}=2.333\dotsc,\mathrm{int}(\frac{a}丐怯)=2,\mathrm{rem}(\frac{a})=1$

現(xiàn)在來考慮雙字除法翔横。設被除數(shù)如下： $D=\mathrm{0x\ }\underbrace{a_{31}a_{30}\dotsc a_{16}}_{DX}\underbrace{a_{15}a_{14}\dotsc a_{0}}_{AX}$ 如同我們可以把10進制數(shù) $1234$ 寫成 $12\times100+34$ 读跷，16進制下的數(shù) $D$ 可以寫為 $\begin{split} D&=\mathrm{0x\ }\underbrace{a_{31}a_{30}\dotsc a_{16}}_{H}\times \mathrm{0x}\underbrace{100\dotsc0}_{16\;0's}+\mathrm{0x}\underbrace{a_{15}a_{14}\dotsc a_{0}}_{L}\\&=H\times65536+L\end{split}$ 顯然 $H$ 和 $L$ 分別是寄存器DX和AX中的值。
現(xiàn)在設除數(shù)是 $n$ 禾唁，從而 $\frac{D}{n}=\frac{H}{n}\times 65536+\frac{L}{n}$ 再次強調(diào)此時我們表示的是實數(shù)除法效览。根據(jù)整數(shù)帶余數(shù)除法引理，對于 $H,n$ 荡短，又存在唯一的如下表示 $H=\mathrm{int}(\frac{H}{n})\times n+\mathrm{rem}(\frac{H}{n})$ 其中 $0\leqslant \mathrm{rem}(\frac{H}{n}) <n$ 丐枉，從而 $\frac{H}{n}=\mathrm{int}(\frac{H}{n})+\frac{\mathrm{rem}(H/n)}{n}$ ，于是 $\begin{split} \frac{D}{n}&=\left(\mathrm{int}(\frac{H}{n})+\frac{\mathrm{rem}(H/n)}{n}\right)\times 65536+\frac{L}{n}\\ &=\mathrm{int}(\frac{H}{n})\times 65536+\frac{1}{n}\left(\mathrm{rem}(\frac{H}{n})\times65536+L \right)\end{split}$ 因為 $H$ 是16位的掘托，因此 $H$ 除以 $n$ 的整數(shù)部分 $\mathrm{int}(H/n)$ 必然也不超過16位瘦锹。
對于括號中的部分，討論其取值范圍（設 $n$ 是正整數(shù)） $\begin{split} 0\leqslant& \mathrm{rem}(\frac{H}{n})\leqslant n-1\\ 0\leqslant& \mathrm{rem}(\frac{H}{n})\times 65536 + L \leqslant 65536\times (n-1)+L \end{split}$ 因為 $L$ 是16位整數(shù)，故 $L<65536$ 弯院，于是 $\begin{split} 0\leqslant& \mathrm{rem}(\frac{H}{n})\times 65536 + L <65536\times n \\ 0\leqslant& \frac{1}{n}\left(\mathrm{rem}(\frac{H}{n})\times65536+L \right)< 65536 \end{split}$ 由此可知辱士，對其取整的結果： $\mathrm{int}\left[\frac{1}{n}\left(\mathrm{rem}(\frac{H}{n})\times65536+L \right)\right]$ 不超過16位。

現(xiàn)在听绳，令 $\begin{cases} P&=\mathrm{int}(H/n)\\ Q&=\mathrm{int}\left[\frac{1}{n}\left(\mathrm{rem}(\frac{H}{n})\times65536+L \right) \right]\\ r&=\frac{1}{n}\left(\mathrm{rem}(\frac{H}{n})\times65536+L \right) -Q \end{cases}$ 我們重新敘述結果：
$\frac{D}{ n}=P\times 65536 + (Q+r)\quad(P,Q\in\mathbb{N},r\in\mathbb{R})$ 換句話說
$D=(P\times65536+Q)\times n + r\times n$ 顯然 $n\times r$ 是整數(shù)颂碘，并且 $n\times r<r$ 。這是因為通過定義可知椅挣， $r$ 是實數(shù) $(\mathrm{rem}(H/n)\times65536+L)/n$ 減去它的整數(shù)部分（即 $Q$ ）头岔，因此結果就是該實數(shù)的小數(shù)部分，因此 $r\in[0,1)$ 鼠证，從而 $n\times r\in\{0,1,\dotsc,n-1\}$ 切油，根據(jù)帶余數(shù)除法引理，這個余數(shù) $n\times r$ 是唯一的名惩。

因此我們有
$\begin{cases} \mathrm{int}(\frac{D}{ n})&=P\times 65536 +Q \\ \mathrm{rem}(\frac{D}{ n})&=n\times r=D-(P\times65536+Q) \end{cases}$ 因為 $P,Q$ 均不超過16位澎胡，因此除法結果，商的高16位 $P$ 存儲在DX中娩鹉，低16位 $Q$ 存儲在AX中攻谁，余數(shù) $\mathrm{rem}(\frac{D}{n})$ 不能大于除數(shù) $n$ ，故而也可以安全存儲在CX中弯予。