C语言除法算法和取模运算的实现(多种算法,多种思路)

  • 内容
  • 评论
  • 相关

对计算机来说,除法与求模是整数算术运算中最复杂的运算。相对其他运算(如加法与减法)来说,这两种算法的执行速度非常慢。例如,ARM 硬件上不支持除法指令,编译器调用 C 库函数来实现除法运算。直接利用 C 库函数中的标准整数除法程序要花费 20~100 个周期,消耗较多资源。

在非嵌入式领域,因为 CPU 运算速度快、存储器容量大,所以执行除法运算和求模运算消耗的这些资源对计算机来说不算什么。但是在嵌入式领域,消耗大量资源带来的影响不言而喻。因此,从理论上讲,我们应该在程序表达式中尽量减少对除法运算与求模运算的使用,尽量使用其他方法来代替除法与求模运算。例如,对于下面的示例代码:

if (x/y>z)
{
    // ...
}

我们可以将其修改成如下形式:

if (((y>0)&&(x>y*z))||((y<0)&&(x<y*z)))
{
    // ...
}

这样就简单地避免了一些除法运算。同时,也可以在表达式中通过合并除法的方式来减少除法运算,下面通过示例来讲解。对于如下代码:

double x=a/b/c;
double y=a/b+c/b;

根据数学结合原则,上面的代码可以通过合并的方式减少代码中的除法运算,修改后的代码如下:

double x=a/(b*c);
double y=(a+c)/b;

同样,对于求模运算,也可以采用相应的方法来代替,如下面的示例代码:

a=a%8;

可以修改为:

a=a&7;

对于下面的表达式:

x=(x+y)%z;

可以通过如下方式来避免使用模操作符:

x+=y;
while(x>=z)
{
    x-=z;
}

通过上面的阐述,相信大家对如何减少使用除法与模运算有了初步了解。下面将详细讨论如何优化除法运算与求模运算。

用倒数相乘来实现除法运算

何为倒数相乘?其实很简单,它的核心思想就是利用乘法来代替实现除法运算。例如,在 IA-32 处理器中,乘法指令的运算速度比除法指令要快 4~6 倍。因此,在某些情况下尽量使用乘法指令来代替除法指令。

那么,我们该如何利用乘法来代替实现除法运算呢?原理就是被除数乘以除数的倒数,用公式表现为:

x/y=x*(1/y)

例如,计算 10/5,可以根据公式 x/y=x*(1/y) 这样来计算:

10/5=10*(1/5)=10*0.2=2

在实际应用中,一些编译器也正是基于这个原理才得以将除法运算转换为乘法运算的。现在我们来看一个除法运算示例:

#include <stdio.h>
int main(void)
{
    int x = 3/2;
    float y = 3.0/2.0;
    printf("3/2 = %d\r\n3.0/2.0 = %1.1f\n",x,y);
    return 0;
}

运算结果为:
3/2 = 1
3.0/2.0 = 1.5

通过该除法运算示例可以看出,很明显没能充分考虑到浮点类型。另外,在 C 语言中,一般情况下 1 除以任何数其结果皆为 0。那么怎样才能解决这个问题呢?编译器采用了一种称为“定点运算”(fixed-point arithmetic)的方法。

那么何为定点运算,定点运算有什么特点呢?

前面已经阐述过,由于计算机表示实数时为了在固定位数内能表示尽量精确的实数值,分配给表示小数部分的位数并不是固定的,也就是说“小数点是浮动的”,因此计算机表示的实数数据类型也称为浮点数。

相对于“小数点是浮动的”来讲,定点运算根据字面意思来理解就是“小数点是固定的”。有了定点运算,表示小数时不再用阶码(exponent component,即小数点在浮点数据类型中的位置),而是要保持小数点的位置固定不变。这和硬件浮点数机制截然不同,硬件浮点数机制是由硬件负责向整数部分和小数部分分配可用的位数。有了这种机制,浮点数就可以表示很大范围的数——从极小的数(在 0~1 的实数)到极大的数(在小数点前有数十个 0)。这种小数的定点表示法有很多优点,尤其能极大地提高效率。当然,作为代价,同样也必须承受随之而来的精度上的损失。

对于定点数表示法(fixed-point),相信大家并不陌生。所谓定点格式,即约定机器中所有数据的小数点位置是固定不变的。在计算机中通常采用两种简单的约定:将小数点的位置固定在数据的最高位之前(即定点小数),或者固定在最低位之后(即定点整数)。

其中,定点小数是纯小数,约定的小数点位置在符号位之后、有效数值部分的最高位之前。若数据 x 的形式为 x=x0x1x2…xn(其中 x0 为符号位,x1,…,xn 是数值的有效部分,也称为尾数,x1 为最高有效位),则在计算机中的表示形式为:


本文标题:C语言除法算法和取模运算的实现(多种算法,多种思路)

本文地址:https://www.hosteonscn.com/2772.html

评论

0条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注