8086汇编】迭代-手把手教你实现递归求斐波那契数和无符号数字的输出
概述
本期的重点在于使用8086汇编语言实现循环迭代,无符号数字输出,使用多位内存储存超长整型,超长整型打印输出
程序框图

模块图

初始化准备
我们先把代码段、数据段和栈段准备好相关的数据并完成相关的初始化
声明段
我们先声明三个段
| 1 | assume cs:codesg,ds:datasg,ss:stacksg | 
装载数据
在数据段我们准备填入如下数据
- choose字符串,用于输出提示信息
- result字符串,用于输出提示信息
- enter字符串,用于输出回车换行,即- \n\r
- pressQ字符串,用于输出退出程序的提示信息
- wrongRange字符串,用于输出范围错误的提示信息
- num112字节长整型,表示迭代中的- Fib(n-2)
- num212字节长整型,表示迭代中的- Fib(n-1),同时最终答案也存在- num2中
- numlen单字(2字节)变量,储存输出数字串的长度/栈的深度
- tmpcx1单字变量,辅助暂存- cx的值,避免使用栈,防止栈的管理混乱
这里写入num我们使用dw指令写入一个字长(2字节)
而写入字符串必须一个字节一个字节写入,所以使用db指令
特别的,在8086中,$用于表示一段字符串的结尾
| 1 | ;初始化数据段,并填入数字 | 
而对于栈段,其实并不需要做什么特别的初始化,当然我们可以给它额外做个置零
这里对连续内存置零我们使用了dup指令配合db进行重复写入
| 1 | ;初始化栈段,置空 | 
主逻辑框架
最后我们再在代码段把整个程序的主逻辑框架,这里我们会调用一些自定义的模块,但这里只是保留它们的名字和逻辑功能,具体实现交给文章的后半部分
| 1 | codesg segment | 
无符号数字输入模块
柿子拣软的捏,所以我们先来实现最简单的输入模块
这个模块的功能需求有
- 支持输入十进制数字串,并存储到ax输出
- 支持判断是否输入Q,输入时跳转到退出程序
- 可在输入非法字符(包括回车)时,停止输入,跳转到输出返回
初始化&现状保存
如同C语言函数的传值传参一样,我们也模拟函数的行为做传值传参。为此我们就要做现状保存。
现状保存的具体做法就是按一定顺序把需要保存的寄存器数据存入堆栈,函数返回前我们再逆序取出来。
至于如何传出获取到的数字,我们这里约定使用ax作为输出型参数输出寄存器
| 1 | ;================数字键入模块============ | 
非法输入处理和数字存入
我们采用死循环的方式逐个字符即时读取,
为了防止Q被解析成非法字符,所以我们先判断输入是否为Q,若是,我们就跳转到程序退出。但是因为这里的代码长度问题,使用je可能会越界,所以我们使用了二级跳跃:je 配合 jmp far ptr使用
然后再判断到非法字符(非0~9数字字符)时模块跳出循环到模块结束部分InputNumEnd。
这里的判断非法字符我们要配合之前用过的cmp,这里用到的标志位是CF进位标志位和ZF零标志位,要用到的跳转函数是ja和jb
- ja: Jump if Above,当- op1 > op2时跳转
- jb: Jump if Below,当- op1 < op2时跳转
这样我们就能只取'0'和'9'中间的字符了,
至于数字存入,我们则是把暂存的结果(这里是bx)乘以10再加上ax里的尾数的数值
而如何实现x10操作呢?我们采用移位操作/乘以2的n次方 配合加法,即把bx*=10拆成bx = bx*2^3 + bx + bx
| 1 | FarProcExit: | 
模块的完整代码
| 1 | ;================数字键入模块============ | 
斐波那契数输出模块/超长整型输出模块
使用万进制的内存存储
大于双字(无法加载到内存器中)的二进制数转十进制太麻烦太难了,所以我们退而求其次,将其变成万进制转十进制,这样的转换就简单多了。因此我们对内存的分块的视图如下:

显然我们引入了一个前提:一个字内的值不会超过9999,这一前提的实现我们交给迭代求值模块来实现
万进制的好处
使用万进制存储的最大的好处就是映射关系简单,我们可以简单地按字处理数字字符的转换,因为它的映射关系就是按字分块的

代码实现
基于万进制存储的思想,我们借助栈来产生数字字符串
当然,我们还有前导零的删除和中间0的输出要处理
删除前导零
思路上很简单,我们在产生数字字符时,适时地判断整个连续内存是否为0,若为0,显然此时产生的是前导零,我们可以直接跳转到输出子模块,这样就可以方便地删除前导零了。不过显然整个连续内存的判0较为复杂,所以我们还要封装一个判0模块来使用,同时也能防止一个模块内代码量过大
| 1 | ;========判空模块========== | 
输出中间0
当高位内存不为0时,我们要保证输出够中间0,所以我们使用四次循环打印配合cmp分流的方式,保证每一段内存,在高位不为0时,输出足够的中间0
输出一般数字字符
这里我们依然采用除以10求余法来获取每一位数字,然后加上'0'来转换为数字字符
至于顺序问题,我们会先求出来最低位的数字字符,但是我们要最后打印最低位数字字符,所以我们使用栈来暂存数字字符,最后出栈时就能很好地逆序输出。显然对同一个字内的值是这样,对于字与字之间,我们要先求低位字的数字字符再求高位的,这样能达到整体数字的顺序一致性
完整代码
| 1 | ;========Fib数字输出模块===== | 
斐波那契数列迭代模块
对于这一模块,我们采用ax输入参数,num2长内存输出结果。
以及我们要使用多位字节来储存大数字来应对溢出的风险。
迭代法求斐波那契数列
首先我们学习一下如何用最少的变量来迭代求斐波那契数列
- ax存储- Fib(n-2)
- bx存储- Fib(n-1),显然初始化时,- bx是- ax的后一位
- add ax,bx求得- Fib(n) = Fib(n-1) + Fib(n-2),此时- ax是- bx的后一位
- 交换ax和bx的值,此时bx重新成为ax的后一位,并且ax和bx都在斐波那契数列中向后走了一位
- 回到第一步继续循环迭代
超长整数迭代斐波那契数列
这里我们使用了多字的num1和num2分别存储Fib(n-2)和Fib(n-1),所以我们要实现多字整型的加法。这里我们使用循环来从低位往高位相加,当然,我们顺便也可以在加完后就交换低位的内存。
但是在加的时候,我们同时要考虑进位,,因为相加结果存在了ax,所以要及时判断ax的值是否超过了9999,若是,则减去10000,同时让高位+1。那么怎么加呢?我们可以用别的寄存器来临时存储,但其实我们可以直接加到内存中,在接下来的更高地址的字的运算里用到。那么问题来了,num1和num2加给谁呢?考虑到,num2表示Fib(n-1),在本次运算后要交换给num1,其正确性不能被低位的进位破坏,而num1原本的值本来就会在运算后被覆盖,所以把进位加给num1的就非常合适
代码实现
具体输出时还要考虑最基本的情况:Fib(1) = Fib(2) = 1,所以我们在输入时再加一个判断,单独输出这俩结果
| 1 | ;===========斐波那契数列迭代模块========规定用num2输出 | 
整个项目的代码
在完成了数个模块后,我们终于可以把它们都拼接在一块了。
| 1 | assume cs:codesg,ds:datasg,ss:stacksg | 
