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 = %drn3.0/2.0 = %1.1fn",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=x₀x₁x₂…x_n（其中 x₀ 為符號位，x₁，…，x_n 是數值的有效部分，也稱為尾數，x₁ 為最高有效位），則在計算機中的表示形式為：

---