8086汇编】迭代-手把手教你实现递归求斐波那契数和无符号数字的输出
概述
本期的重点在于使用8086汇编语言
实现循环迭代
,无符号数字输出
,使用多位内存储存超长整型
,超长整型打印输出
程序框图
模块图
初始化准备
我们先把代码段
、数据段
和栈段
准备好相关的数据并完成相关的初始化
声明段
我们先声明三个段
1 | assume cs:codesg,ds:datasg,ss:stacksg |
装载数据
在数据段
我们准备填入如下数据
choose
字符串,用于输出提示信息result
字符串,用于输出提示信息enter
字符串,用于输出回车换行,即\n\r
pressQ
字符串,用于输出退出程序的提示信息wrongRange
字符串,用于输出范围错误的提示信息num1
12字节长整型,表示迭代中的Fib(n-2)
num2
12字节长整型,表示迭代中的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 |