【程式筆記】避免整數運算數值溢出(Overflow)的技巧

在進行整數加減的時候,直覺上會直接將兩個數值加起來。而在電腦的世界中,這麼做很容易會發生數值溢出(Overflow)的問題。

數值溢出(Overflow)

在電腦科學的領域中,每個數值都會被分配一組記憶體,當數值超出記憶體所能容納的空間時,我們會稱這種狀況叫做Overflow。
Overflow會對軟體產生不好的影響,輕微的像是軟體運作崩潰,嚴重的則有可能造成資料損壞。
駭客也會經常利用Overflow的原理去攻擊伺服器竊取資料。
因此,在寫程式的時候做好Overflow的防範是很重要的。

整數運算

整數的長度

整數的運算是最容易見到數值溢出發生的地方。直覺上,我們都會直接將兩的數值加起來,這在現實中是沒有問題的,然而在電腦的世界中,多數語言的整數的長度只有4個Byte(32bit),可以涵蓋的整數範圍為[0 ~ 4294967295](0 ~ 2^32-1),或[−2147483648 ~ 2147483647](2^16 ~ 2^16-1)。也因此,只要在計算的時候超過範圍,就會產生溢出。

常見的錯誤運算方式

  • a+b:相加是最頻繁發生溢出的運算方式,不論是老手或新手都很容易出現失誤,尤其是在進行大數值運算的時候,因為就算知道記下了溢出的範圍,也很難掌握住每個有可能產生溢出的Case。
  • a-b:相減可以看成反過來的相加,也很容易發生相減超過範圍的情況。
  • a*b:相乘也是容易製造溢出的原因之一。

解決方法

  • 宣告長整數(Long Int):
    長整數可以讓32bit的範圍擴增至64bit,涵蓋的範圍更廣,可以避免掉一般整數的計算溢出,但是仍然會有計算超過範圍的可能。
int a;      // 32-bit
long int a; // 64-bit
  • 換位表達運算式:
    利用不同的運算表達,限制計算的範圍,讓計算不會超過整數。在二分搜尋演算法(Binary search algorithm)中,中位數的計算是由低位數位置加上高位數位置除以二來獲得,運算式(LowIndex + HighIndex )/ 2,當兩個位置相加就有發生相加溢出的可能性,但如果我們利用換位表達,中位數的結果可以表示成LowIndex +(HighIndex – LowIndex)/ 2,這樣就能夠避免掉相加溢出的情形,也可以獲得相同的結果,可以參考這篇文章
int getMiddleValue(int a, int b){
        return (a+b)/2;
}

int getSafeMiddleValue(int a, int b){
        return a+(b-a)/2;
}

getMiddleValue(INT_MAX/2,INT_MAX/2+INT_MAX/4); // 數值溢出(Overflow)
getSafeMiddleValue(INT_MAX/2,INT_MAX/2+INT_MAX/4); // 正確顯示

JavaScript的Integer

JavaScript與多數語言的變數型別分類不一樣,只有一種數字型別(Number)涵蓋了所有數值的表示方式,Number型別是雙精度64位元浮點數,沒有單一表示整數的型別,在做整數運算的時候,則需要更注意數值是不是正確的表示。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。

回到頂端