汇编练习：不会溢出的除法

作者: Azur_wxj | 来源:发表于2020-03-01 11:32 被阅读0次

汇编练习：不会溢出的除法
8086汇编(30)解决除法溢出的问题
我竟在arm汇编除法算法里找到了leetcode某道题的解法
14.1.4(2)整式的除法
汇编学习笔记（完结篇）
一些汇编题目分析
汇编学习12 内中断
两个整数相除
栈溢出练习
汇编进位与溢出标志位

王爽老师的《汇编语言》在实验10.2中提出了div指令可能出现的除法溢出的问题。例如对于16位除以8位的情形，考虑被除数是0x1234，除数是0x01。根据div的约定，商在AL中，余数在AH中。但是显然计算结果的商是0x1234，8位的AL无法容纳，因此会产生除法溢出。使用Bochs调试时，会在div之后出现iret，即CPU产生了一个中断返回指令。
为了兼容32位对16位的除法，设计一个双字除法调用过程divdw：

输入：
- 被除数：一个32位的整数，高16位在DX中，低16位在AX中
- 除数：一个16位的整数，存储在CX中
输出：
- 商：32位的整数，高16位在DX中，低16位在AX中
- 余数：16位整数，储存在CX中

因为商也是双字长，因此divdw过程一定不会发生除法溢出。这是因为，考虑被除数最大是0xFFFFFFFF，除数最小是0x0001，则商最大为0xFFFFFFFF，不会超过双字长。但是直接使用div指令是无法办到的，所以我们下面需要设计divdw的过程。首先给出一个数论中关于带余数除法的引理：

(带余数除法)：设 $a,b$ 是两个整数， $b\neq0$ ，则存在唯一的整数对 $(p,r)$ ，使得 $a=pb+r\quad (0\leqslant r <|b|)$

我们接下来约定，符号 $\frac{a}{ b}$ 表示实数除法， $\mathrm{int}(\frac{a}{b})$ 表示整数除法的商，相当于上面的 $p$ ； $\mathrm{rem}(\frac{a}{b})$ 表示整数除法的余数，相当于上面的 $r$ 。例如，对于 $a=7,b=3$ ，我们有 $\frac{a}{ b}=2.333\dotsc,\mathrm{int}(\frac{a}{b})=2,\mathrm{rem}(\frac{a}{b})=1$

现在来考虑双字除法。设被除数如下： $D=\mathrm{0x\ }\underbrace{a_{31}a_{30}\dotsc a_{16}}_{DX}\underbrace{a_{15}a_{14}\dotsc a_{0}}_{AX}$ 如同我们可以把10进制数 $1234$ 写成 $12\times100+34$ ，16进制下的数 $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中的值。
现在设除数是 $n$ ，从而 $\frac{D}{n}=\frac{H}{n}\times 65536+\frac{L}{n}$ 再次强调此时我们表示的是实数除法。根据整数带余数除法引理，对于 $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$ 的整数部分 $\mathrm{int}(H/n)$ 必然也不超过16位。
对于括号中的部分，讨论其取值范围（设 $n$ 是正整数） $\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位整数，故 $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位。

现在，令 $\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$ 是整数，并且 $n\times r<r$ 。这是因为通过定义可知， $r$ 是实数 $(\mathrm{rem}(H/n)\times65536+L)/n$ 减去它的整数部分（即 $Q$ ），因此结果就是该实数的小数部分，因此 $r\in[0,1)$ ，从而 $n\times r\in\{0,1,\dotsc,n-1\}$ ，根据带余数除法引理，这个余数 $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中，余数 $\mathrm{rem}(\frac{D}{n})$ 不能大于除数 $n$ ，故而也可以安全存储在CX中。

汇编练习：不会溢出的除法
王爽老师的《汇编语言》在实验10.2中提出了div指令可能出现的除法溢出的问题。例如对于16位除以8位的情形，考虑...
8086汇编(30)解决除法溢出的问题
解决除法溢出的问题名称:divdw 功能:进行不会产生溢出的除法运算，被除数为dword型，除数为word型，结...
我竟在arm汇编除法算法里找到了leetcode某道题的解法
今天讲讲arm汇编中除法的底层实现。汇编代码本身比较长了，如需参考请直接拉到文末。下面我直接把arm的除法算法的...
14.1.4(2)整式的除法
以下是整式除法预习练习以下是整式除法复习练习
汇编学习笔记（完结篇）
内中断对于8086，当cpu内部有下面的情况发生时，将产生相应的中断：除法错误，如执行div时产生的除法溢出 ...
一些汇编题目分析
最近在学习汇编做MOOC和练习题的时候碰到了几道比较难的题，觉得可以总结一下。栈溢出和大小端有如下的C代码以及...
汇编学习12 内中断
1.内中断产生 CPU产生内中断的原因：（1）除法发生溢出（2）单步执行指令（3）执行into指令（？）（4）执行...
两个整数相除
描述将两个整数相除，要求不使用乘法、除法和 mod 运算符。如果溢出，返回 2147483647 。样例给定...
栈溢出练习
一，工具安装二，程序源码文件名为:StackOF.c 可以看到，其是将main函数里的buffer作为msg传...
汇编进位与溢出标志位
以例题开始说明：写出如下程序段执行后进位标志位与溢出标志位的变化标志寄存器保存的是当前指令执行后的运算状态CF只...