如何用汇编语言编写一个求最大公约数（GCD）的过程——辗转相除法
发布时间：2023-03-23 12:00
选题：《汇编语言 基于X86处理器》【Kip Irvine著】—— Chapter7 编程练习第6题
两个数的最大公约数（GCD）是指能整除这两个数的最大整数。下述伪代码描述的是循环整数除法的GCD算法：
int GCD(int x,int y)
{
x = abs(x)
y = abs(y)
do{
int n = x % y
x = y
y = n
}while(y>0)
return x
}用汇编语言实现该程序，并编写测试程序，通过向该函数传递不同的数值对其进行多次调用。
---------------------------------------------------------------------------------------------------------------------------
我们可以从题目得到两个很重要的信息：
一、最大公约数的概念：能整除这两个数的最大整数。
二、算法思想：
1、两个数假定x，y；
2、两者相除取余；
3、若，余数不为0，则将除数作为下一次的被除数，商作为下一次的除数；
4、直到找到余数为零时的商，返回此时商的值。
而我们将上述的算法思想取了一个好听的名字叫做“辗转相除法”，此外，大家可以自行验证一下该方法是否能准确的求出两个数值的最大公约数。
接下来我们就来讲讲，如何使用汇编语言来编写这样的一个算法：
1、首先我们建立asm项目，配置好汇编环境与外部库路径；然后我们初始化DWORD类型的A，B两个数，另外准备一个变量result用于储存最后找到的最大公约数；此外，另编写三句提示语便于清晰的显示：
Include Irvine32.inc
.data
prompt1 BYTE '第一个数字是：',0
prompt2 BYTE '第二个数字是：',0
prompt3 BYTE '两个数字的最大公约数是：',0
A DWORD 14750
B DWORD 37550
result DWORD ?
2、然后由于我们想多次输出过程，所以我们继续编写一个辅助显示的——Display函数；
;---------------------------
Display PROC
;用于被调用，显示结果
;---------------------------
call WriteInt ;调用writeInt,输出数字
call crlf
ret
Display ENDP
3、接着开始构思程序主体，思路大概是：先输出第一个数字，再输出第二个数字，然后调用算法求出结果，最后输出结果；
.code
main PROC
;显示第一个数字：
mov EDX,OFFSET prompt1 ;用offset获取显示语的偏移地址，并存入EDX中
call WriteString ;调用WriteString,将显示语以字符串形式显示出来
mov EAX,A
call Display ;调用Display函数
;显示第二个数字：
mov EDX,OFFSET prompt2
call WriteString
mov EBX,B
call Display
;调用算法：
mov EDX,OFFSET prompt3
call WriteString
call ZhanzhuanMethod ;调用辗转相除函数，求两个数字的最大公约数
;显示结果：
mov EAX, result ;将结果result存放入EAX中
call Display ;再次调用Display函数，输出结果
4、然后就是最关键的GCD算法实现了，在这里我们对先梳理一下算法思路：
- 将A、B的值分别送入寄存器EAX与EBX中；
- 为了保证被除数大于除数，故使用cmp指令比较A、B大小；
- 被除数大于除数，即使用无符号数跳转指令JNB（leftOp>=rightOp），其结果为否，则交换；结果为真，则跳转到L1；
- 编写L1自身循环用于找到余数为0时的商，其中若找到余数为0的商则跳，将结果放入result并ret。
;---------------------------
ZhanzhuanMethod PROC ;辗转相除函数
;用于求最大公约数的方法
;---------------------------
mov EAX, A
mov EBX, B
cmp EAX, EBX ;比较EAX与EBX
JNB L1 ;EAX大于或等于EBX，则跳转到L_1
mov B, EAX ;若上一步为否，则：交换位置，避免除数大于被除数
mov A, EBX
L1:
mov EAX, A ;已交换/默认不变（满足条件时），保证了A > B
mov EBX, B
mov EDX, 0 ;初始化EDX为0
div EBX ;A%B，两个数字相除，余数自动存入EDX中
cmp EDX, 0 ;比较EDX与0
JE L_End ;JE指令为等于跳转。若余数为0，则找到了最终的最大公约数，跳转到L_End
mov EAX, B ;若上一步余数不为0，则将 除数B 放入 EAX 中
mov A, EAX ;再把原除数B，通过EAX传递给A，作为用作下一次操作的 被除数
mov B, EDX ;再把EDX内的余数，赋给B，作为下一次操作的 除数 （从而再次保证了A > B）
jmp L1
L_End:
mov result,EBX
ret
ZhanzhuanMethod ENDP
main ENDP
END main那么到这里，本题就算是成功的解决了，经过最终的调试，我们可以看到调试结果如下：
在环境搭建与链接库路径导入无误的情况下，程序到底能不能run呢？感兴趣的小伙伴们赶快试一下吧！
----------------------------------------------------------------------------------------------------------------------------
附：（完整代码）
Include Irvine32.inc
.data
prompt1 BYTE '第一个数字是：',0
prompt2 BYTE '第二个数字是：',0
prompt3 BYTE '两个数字的最大公约数是：',0
A DWORD 14750
B DWORD 37550
result DWORD ?
.code
main PROC
;显示第一个数字：
mov EDX,OFFSET prompt1 ;用offset获取显示语的偏移地址，并存入EDX中
call WriteString ;调用WriteString,将显示语以字符串形式显示出来
mov EAX,A
call Display ;调用Display函数
;显示第二个数字：
mov EDX,OFFSET prompt2
call WriteString
mov EBX,B
call Display
;调用算法：
mov EDX,OFFSET prompt3
call WriteString
call ZhanzhuanMethod ;调用辗转相除函数，求两个数字的最大公约数
;显示结果：
mov EAX, result ;将结果result存放入EAX中
call Display ;再次调用Display函数，输出结果
;---------------------------
ZhanzhuanMethod PROC ;辗转相除函数
;用于求最大公约数的方法
;---------------------------
mov EAX, A
mov EBX, B
cmp EAX, EBX ;比较EAX与EBX
JNB L1 ;EAX大于或等于EBX，则跳转到L_1
mov B, EAX ;若上一步为否，则：交换位置，避免除数大于被除数
mov A, EBX
L1:
mov EAX, A ;已交换/默认不变（满足条件时），保证了A > B
mov EBX, B
mov EDX, 0 ;初始化EDX为0
div EBX ;A%B，两个数字相除，余数自动存入EDX中
cmp EDX, 0 ;比较EDX与0
JE L_End ;JE指令为等于跳转。若余数为0，则找到了最终的最大公约数，跳转到L_End
mov EAX, B ;若上一步余数不为0，则将 除数B 放入 EAX 中
mov A, EAX ;再把原除数B，通过EAX传递给A，作为用作下一次操作的 被除数
mov B, EDX ;再把EDX内的余数，赋给B，作为下一次操作的 除数 （从而再次保证了A > B）
jmp L1
L_End:
mov result,EBX
ret
ZhanzhuanMethod ENDP
;---------------------------
Display PROC
;用于被调用，显示结果
;---------------------------
call WriteInt ;调用writeInt,输出数字
call crlf
ret
Display ENDP
main ENDP
END main