C++ - 整數運算之溢位偵測

整數運算中，最容易產生溢位問題的估計是階層運算。設計一個factorial遞回函式來運算階層，輸入是一個整數N，輸出則為N!的結果，輸入和輸出的整數資料型態一致，假設使用unsigned int作為整數資料型態，該factorial函式表示如下：

unsigned int factorial(unsigned int N)
{
    return (N == 0 || N == 1) ? 1 : N * factorial(N - 1);
}

這是很簡單的一個寫法，用unsigned int是因為階層的定義要求為正整數或0。這個寫法並沒考量到溢位問題，當輸入的N為13時，就會產生溢位問題。

如果是兩個整數相加，溢位會多增加一個位元，可以檢查兩個整數相加是否會有進位現象，進位後會不會超出資料型態的位元數，來判斷相加會不會產生溢位。

可是階層運算是乘法運算，無法用相加的溢位判斷方式，而要用其他的方式判斷。

方式一：溢位旗標的判斷。因為暫存器的關係，僅適用於int、unsigned int等32位元的整數資料型態，若用於其他位元數的整數資料型態會判斷錯誤。

unsigned int factorial(unsigned int N)
{
    unsigned int product = 0;
    product = (N == 0 || N == 1) ? 1 : N * factorial(N - 1);
    __asm jo overflowed;
    if (0)
    {
overflowed:
        throw(std::out_of_range("Overflowed"));
    }
    return product;
}

方法二：除法運算檢查。適用各種整數資料型態。

int factorial(int N)
{
    int product = 0;
    if (N < 0) // 限定N為正整數或0
    {
        throw(std::out_of_range("Negative integer"));
    }
    if (N == 0 || N == 1)
    {
        product = 1;
    }
    else
    {
        int multiplicand = factorial(N - 1);
        product = N * multiplicand;
        if (product / N != multiplicand) throw(std::out_of_range("Overflowed"));
    }
    return product;
}

方法三：自訂BigInteger的資料型態。 BigInteger的數字是使用字元陣列來表示，運算採取字元陣列的方式做運算，加減乘除也需要自訂，因為是用字元陣列來表示一個數字，所以該數字理論上可以無限大（實際上會受限字元陣列所能表示的最大長度）。

方法二就已經足夠使用，方法三就留給以後需要的時候再來實作。