【ARM汇编】如何用汇编求最大公约数?

发布时间:2023-09-23 08:30

在这里插入图片描述

CSDN话题挑战赛第1期
活动详情地址:话题PK赛
参赛话题:汇编知识分享
话题描述:我们的计算机知识就像一座金字塔,底层是数学,上面是数字电路,然后是汇编,再往上是操作系统、网络、数据库、高级编程语言、框架等等…我们不可能精通这个金子塔的每一层, 但是想走的更远就必须要了解这个金字塔的底层。因此,学习汇编并不是为了用汇编在应用层设计程序,而是为了深刻理解机器运行程序的机理。就像对于人来说不能没有常识一样,尽管常识不能直接挣钱吃饭,但它影响谈吐,影响你的判断力和决断力,决定着你接受新事物和新知识的程度。汇编就是计算机语言里面的常识和基础。

大家好,我是汤姆凯特。

【ARM汇编】如何用汇编求最大公约数?_第1张图片

文章目录

  • 如何用汇编求最大公约数?
  • C语言实现方法
      • 更相减损术
      • 图解
      • 举例
      • C语言代码部分
  • 汇编语言如何实现
    • 第一步
    • 第二步
        • 1.构造循环
        • 2.两数比较|作差
    • 第三步
    • 汇编源码
    • 运行调试
  • 总结

每篇前言

☀️作者简介:大家好我是汤姆凯特,大家可以叫我汤姆
个人主页:IM汤姆凯特的CSDN博客
系列专栏:【ARM嵌入式基础】
每日一句:

只有经过长时间完成其发展的艰苦工作,并长期埋头沉没于其中的任务,方可有所成就。——黑格尔


如何用汇编求最大公约数?

学习任何语言都逃不掉练习求解最大公因数的算法,C语言中我们有多种求解办法——穷举法——辗转相除法——更相减损术。在汇编中我们都可以实现,今天这篇文章给大家介绍用更相减损术求解最大公约数。

C语言实现方法

更相减损术

更相减损术是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。

​ 1.先判断两个数的大小,如果两数相等,则这个数本身就是就是它的最大公约数。
  2.如果不相等,则用大数减去小数,然后用这个较小数与它们相减的结果相比较,如果相等,则这个差就是它们的最大公约数,如果不相等,则继续执行2操作,直到两个数相等时为两个数的最大公约数。

图解

【ARM汇编】如何用汇编求最大公约数?_第2张图片

举例

例:用更相减损术求98与63的最大公约数。

解:由于63不是偶数,把98和63以大数减小数,并辗转相减:

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以,98和63的最大公约数等于7。

C语言代码部分

//更相减损术
int gcd(int a, int b)
{
	if (a == b)
	{
		return a;
	}
	else if (a > b)
	{
		return gcd(a - b, b);
	}
	else
	{
		return gcd(b - a, a);
	}
}

汇编语言如何实现

在汇编中实现这个算法首先要知道汇编中的减法指令——SUB。SUB的使用方法跟ADD类似并且也可以加判断后缀。

汇编语言实现整体分为三个步骤:1.读取两个数值。2.更相减损法运算。3.显示计算结果。

第一步

可以调用C的scanf函数,读取键盘上键入的数据。我们这里重点讲解sub指令,所以简化键入步骤,直接用两个寄存器存放两个待求数据。

mov r4,#98
mov r5,#63

第二步

通过C的代码我们也可以看出,整个算法包括——比较、相减、循环三个部分。

在写汇编时可以先从框架入手,首先把循环构造出来,然后在循环中比较,然后根据比较的不同结果相减。

1.构造循环

进入循环之后,只要不满足相等就继续循环。

gcd:
	...
	bne gcd

2.两数比较|作差

cmp本质是用前面数减后面数,下面sub减语言加了后缀,为比较的结果做出反应,gt表大于(即:当r4大于r5,用r4-r5结果存到r4),lt表小于(即:当r4小于r5,用r5-r4结果存到r5)。

    cmp r4,r5
    subgt r4,r5
    sublt r5,r4

第三步

当满足两数相等,循环相减完成,那么此时r4=r5的值且为两数的最大公因数,任意将r4或r5的值传给r1,调用printf输出即可。

调用printf,必须现在全局变量中定义输出的格式串。

.data
    fmt:.asciz "\n  gcd=%d\n"
 main:    
    ......
    ldr r0,=fmt
    mov r1,r4
    bl printf

汇编源码

//辗转相减法求最大公约数

//辗转相减法求最大公约数
.data
    fmt:.asciz "\n  gcd=%d\n"
.text
.globl main
main:
    push {lr}
    mov r4,#98
    mov r5,#63
gcd:
    cmp r4,r5
    subgt r4,r5
    sublt r5,r4
    bne gcd
    ldr r0,=fmt
    mov r1,r4
    bl printf
    mov r0,#0
    pop {lr}
    mov pc,lr
.end

运行调试

【ARM汇编】如何用汇编求最大公约数?_第3张图片


总结

  • SUB是不带借位的减法指令,功能是(OP1)←(OP1)-(OP2)。
  • 再写汇编程序时,可以先把整体框架写出,再把循环框架写出,然后再往框架中添加想要实现的功能
  • 在汇编中辗转相减使用循环、CMP、SUB指令即可完成算法功能。

本期内容就结束了,如果内容有误,麻烦大家评论区指出!
如有疑问可以在评论区留言!
下期预告: 【ARM汇编】分支结构

CSDN话题挑战赛第1期
活动详情地址:话题PK赛

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号