如何用乘法运算代替除法运算
Ofweek 2022-05-12

  与传统的4/8位单片机相比,ARM的性能和处理能力是遥遥领先的。但与之相应,ARM的系统设计复杂度和难度,较之传统的设计方法也大大提升了,同时也大大拓展了针对ARM芯片特性进行优化的空间,例如针对指令流水线的优化、针对寄存器分配进行的优化等。

  ARM在硬件上不支持除法指令,编译器是通过调用C库函数来实现除法运算的,有许多不同类型的除法程序来适应不同的除数和被除数。但直接利用C库函数中的标准整数除法程序,根据执行情况和输入操作数的范围,要花费20~100个周期,消耗较多的软件运行时间。在实时嵌入式应用中,对时间参数较为敏感,故可以考虑如何优化避免除法消耗过多的CPU运行时间。

  除法和模运算(/和%)执行起来比较慢,所以应尽量避免使用。但是,除数是常数的除法运算和用同一个除数的重复除法,执行效率会比较高。在ARM中,可以利用单条MUL指令实现乘法操作。本文将阐述如何用乘法运算代替除法运算,以及如何使除法的次数最少化。

 

  1 避免除法运算

 

  在非嵌入式领域,因为CPU运算速度快、存储器容量大,除法操作通常都是不加考虑直接使用的。但在嵌入式领域,首先需要考虑的是这些除法操作是否是必须的。以对环形缓冲区操作为例,经常要用到除法,其实完全可以避免这些除法运算。


 

  假定有一个buffer_size大小的环形缓冲区,如图1所示,offset指定目前所在的位置。通过increment字节来增加offset的值,一般是这样写的:

  0ffset=(Offset+increment)%buffer_size;

  效率更高的写法是:

  offset+=increment;

  if(offset>=buffer_size){

  offset-=buffer_size;

  }

  第一种写法要花费50个周期,而第二种因为没有除法运算,只须花费3个周期。这里假定increment

  如果不能避免除法运算,那么就应尽量使除数和被除数是无符号的整数。有符号的除法程序执行起来更加慢,因为它们先要取得除数和被除数的绝对值,再调用无符号除法运算,最后再确定结果的符号。

 

  2 充分利用商和余数

 

  许多C语言库中的除法函数返回商和余数。换句话说,每一个除法运算,余数是可以无偿得到的,反之亦然。例如,要在屏幕缓冲区找到偏移量为offset的屏幕位置(x,y),可以这样写:

  typeclef struct{

  int x;

  int y;

  }point;

  point getxy_v1(unsigned int offset,unsigned int bytes_per_line){

  point p;

  p.y=offset/lt)ytes_per_line;

  p.x=offset - p.y* bytes_per_line;

  return p;

  }

  这里,似乎对p.x使用减法和乘法,少了一次除法运算;但是,实际上使用模运算或者取余操作效率更高,对getxy_v1改进如下:

  point getxy_v2(unsigned int offset,unsigned int bytes_per_line){

  point P;

  P.x=offset%bytes_per_1ine;

  P.y=offset/bytes_per_line;

  return P;

  }

  从下面编译器的输出结果可以看到,只有一次除法调用。实际上,这个程序要比前面的getxy_vl少4条指令(注意,并不是对所有的编译器和C库都有这样的结果)。

  getxy_v2

  STMFD r13!,{r4,r14};保存r4,lr人堆栈

  MOV r4,r0 ;赋值后r4保存的为点P基址

  MOV r0,r2 ;r0=bytes_per_line

  BL rt_udiv ;调用无符号除法例程

  (r0.;r1)=(rl/r0,rl%r0)

  STR r0,[r4,#4] ;P.y=offset/bytes_per_line

  STR rl,[r4,#o] ;P.x=offset%bytes_per_line

  LDMFD r13!,(r4,pc);恢复上下文,返回

 

  3 把除法转换为乘法

 

  在程序中,同一个除数的除法经常会出现很多次。在前面的例子中,bytes_per_line的值在整个程序中都是固定不变的。又如3到2笛卡尔坐标变换,其中就使用了同一个除数两次:

  (x,Y,x)→(x/z,y/z)

  这种情况下,使用cache指令中的值1/z,并使用1/z的乘法来代替除法运算,效率会更高。另外,要尽可能使用int类型的运算,避免使用浮点运算。

  下面将更加偏重于从数学和理论的角度分析,把重复除法转换成乘法运算。

  下面来区分精确数学意义上的除法和整型除法运算:

  n/d,即整数n被分成整数d份,结果趋向于O(与C语言相同);

  n%d,即n被d除之后的余数,就是n--d(n/d);

  n/d=n·d-1,即真正数学意义上的n被d除。

  当使用整型除法时,最容易估算d-1值的方法是计算232/d。然后,就可以估算n/d为:

  (n(232/d))/232 (1)

  在执行n的乘法时,需要精确到64位。对于这种方法,会出现如下问题:

  为了计算232/d,由于一个unsigned int类型的数据放不下232,编译器要使用64位long long类型的数,而且必须指定除法为(1 ull<<32)/d。这种64位的除法比32位的除法执行起来要慢得多。

  如果d碰巧是1,那么232/d就不再适合于un—signed int数据类型。

  上面的做法似乎很好,而且解决了这两个问题。那么,再来看一下用(232一1)/d代替232/d。 令

  s=0xffffffff ul/d (2)

  

  以上n/d-2,q,n/d+1为整数值,所以可得q=n/d或q=(n/d)一1,即初步估计的结果q与正确值n/d有可能存在偏差1。可以发现,通过计算余数r=n—q·d(O≤r<2d)是比较容易的。下面的代码纠正了这个结果:

  r=n--q*d;/*初步估计结果余数r的范围为O≤r<2d*/

  if(r>=d){/*若需要校正*/

  r-=d;/*校正r,使O≤r

  n++;/*相应商加1进行校正*/

  } /*得正确结果q=n/d和r=n%d*/

  下面给出一个实例,用上面的算法完成了N个元素的数组被d除。首先,计算上面所说的s值,然后用乘以5来代替每个被d除的除法。64位的乘是很容易实现的,因为ARM中有一条指令UMULL,可以进行2个32位数相乘,给出一个64位的结果。

  void scale(

  unsigned int*dest; /*目的数据*/

  unsigned int*src; /*源数据*/

  unsignedInt d; /*分母d*/

  urlslglaedInt N;) /*数据长度*/

  {

  unsigned int s=0xFFFFFFFFu/d;

  do{

  unsigned int n,q,r;

  n=*(src++);

  q=(urtslgrted int)(((unsined tong long)n*s)>>32);

  r=n*d;

  if(r>=d){ /*若需要对商进行校正*/

  q++;

  }

  *(dest++)=q;

  }while(--N);

  }

  这里假定除数和被除数都是32位的无符号整数。当然,使用32位乘法进行16位的无符号数计算,或者使用1 28位乘法进行64位数计算,运算规则是一样的。可以为特定的数据选择最窄的运算宽度。如果数据是16位的,那么就设置s=(216一1)/d,然后用标准的整型乘法来求值q。

 

  4 结论

 

  在编程中,为了节省CPU运行时间,应尽可能避免使用除法。对环形缓冲区的处理可以不用除法。如果不能避免除法运算,那么应尽可能使用除法程序同时产生商n/d和余数n%d的好处。对于重复对一除数d的除法.预先计算好s=(2k一1)/d,用乘以s的2k位乘法来代替除以d的k位无符号整数除法,可大大减少由于直接使用除法操作引入的指令周期数。

声明: 本文转载自其它媒体或授权刊载,目的在于信息传递,并不代表本站赞同其观点和对其真实性负责,如有新闻稿件和图片作品的内容、版权以及其它问题的,请联系我们及时删除。(联系我们,邮箱:evan.li@aspencore.com )
0
评论
  • 【7.24 深圳】2025国际AI+IoT生态发展大会/2025全球 MCU及嵌入式技术论坛


  • 相关技术文库
  • 单片机
  • 嵌入式
  • MCU
  • STM
  • 基于C51单片机实现汽车座椅自动控制系统的软硬件设计

    引言 随着人们生活水平的提高,对汽车座椅的舒适性要求也越来越高,要求对汽车座椅地调节能够更加简单、方便、快捷。目前,汽车座椅位置的调节多采用基于手动调节方式的机械和电动控制两种方式。汽车座椅位置的调节...

    07-02
  • MCS51单片机程序设计时堆栈的计算方法解析

    用C语言进行MCS51系列单片机程序设计是单片机开发和应用的必然趋势。Keil公司的C51编译器支持经典8051和8051派生产品的版本,通称为Cx51。应该说,Cx51是C语言在MCS51单片机上的扩展,既有C语言的共性,又有它自己...

    07-02
  • 51单片机定时器工作原理及用法

    TMOD : 控制定时器的工作方式。8个bit,高四位 bit 控制 T1,、低四位 bit 控制 T0。因为定时器有4种工作方式;TMOD = 0x00(工作方式0),TMOD = 0x01(工作方式0),TMOD = 0x02(工作方式2),TMOD = 0x03(工作方式3)。...

    07-02
  • 51单片机学习单片机之路总结

    学习单片机有一学期了,现在也由51转到STM32了。一直想对51的学习做一个总结。也希望对别人有一些启发。也给后学者提供一些建议。当然本文是我对自己学习过程的总结,若有不对的地方,还请高手指出。 我想,再看本...

    07-02
  • hot51增强型单片机开发板原理图

    功能要求: 一):绿灯25s倒计时,绿灯过度红灯有5s黄灯时间,红灯25s后直接跳绿灯。 二):按键按下模拟闯红灯输入,产生5s蜂鸣器鸣叫。 开发环境: 软件:Keil uVision4 硬件:HOT51增强型单片机开发板 程序代码:...

    07-01
  • 51单片机的延时子程序

    延时程序在单片机编程中使用非常广泛,但一些读者在学习中不知道延时程序怎么编程,不知道机器周期和指令周期的区别,不知道延时程序指令的用法, ,本文就此问题从延时程序的基本概念、机器周期和指令周期的区别和联系...

    07-01
  • 什么是Flash盘?Flash盘的结构是什么样的?

    Flash是大家常使用的存储之一,对于Flash,大家或多或少有所了解。上篇文章中,小编对Flash闪存的类型有所介绍。为继续增进大家对Flash的认识,本文将对Flash盘、Flash盘结构以及Flash读写操作予以介绍。如果你对本...

    07-01
  • 深谈嵌入式系统,嵌入式系统是如何组成的?

    嵌入式系统在生活中有诸多应用,大家对于嵌入式系统或多或少有所耳闻。在前两篇文章中,小编对嵌入式系统进行过详细介绍。为继续增进大家对嵌入式系统的认识,本文将对嵌入式系统的组成加以说明。如果你对嵌入式系...

    06-27
  • 嵌入式系统秘籍共享,最全嵌入式系统解析

    嵌入式系统的应用十分广泛,因此越来越多的人学习嵌入式系统。由此,在学习嵌入式系统之前,我们应当对嵌入式系统具备一些认识。所以在本文余下部分,小编将对嵌入式系统进行全面解析。如果你对嵌入式系统具有兴趣...

    06-27
  • 51单片机超声波测距程序详解

    51单片机超声波测距程序详解 超声波四通道测距:超声波测距实现分为三大块: 其一是12864带字库的液晶驱动程序: 代码如下: /////////////////12864驱动程序/////////////////////////// //1写数据 void WriteDat...

    06-25
  • 51系列单片机的引脚图

    51系列单片机的引脚图 端子介绍 l P0.0~P0.7 P0口8位双向口线(在引脚的39~32号端子)。 l P1.0~P1.7 P1口8位双向口线(在引脚的1~8号端子)。 l P2.0~P2.7 P2口8位双向口线(在引脚的21~28号端子)。 l P3.0~P3.7 P2口8...

    06-25
  • 51单片机串口通信需要加超时中断吗?

    接收数据时,超过一定时间就算出错. 这个超时的时间是单片机自己算出的吗?超时的时间是由编程序的人定的,他定多长就多长从一段程序开始 实现电脑向 单片机发送一些数据,单片机返回Iget +数据 #include #define u...

    06-25
下载排行榜
更多
评测报告
更多
广告