- 文章
- 整數溢位
2012年6月9日（最後更新：2014年6月9日）
整數溢位
評分：3.8/5 (448 票)
溢位是一種現象，即對兩個數字的操作超過了資料型別可以擁有的最大值（或低於最小值）。通常認為整數型別非常大，人們沒有考慮到兩個數字的和可能大於該範圍。但在科學和數學計算中，這可能會發生。例如，發動機轉向軟體中未處理的算術溢位是阿麗亞娜 5 火箭首次飛行墜毀的主要原因。該軟體一直被認為是無錯誤的，因為它已在之前的多次飛行中使用過；但那些飛行使用的是較小的火箭，產生的加速度小於阿麗亞娜 5 火箭。本文將介紹如何解決這個問題。
在本文中，我們只處理整數型別（而不處理像 float 和 double 這樣的型別）
為了理解如何解決這個問題，我們將首先了解數字是如何儲存的。
如果資料型別的大小為 n 位元組，則它可以儲存 28n 個不同的值。這被稱為資料型別的範圍。
如果無符號資料型別的大小為 n 位元組，則範圍為 0 到 28n-1
如果帶符號資料型別的大小為 n 位元組，則範圍為 -28n-1 到 28n-1-1
因此，short（通常為 2 位元組）的範圍為 -32768 到 32767，而 unsigned short 的範圍為 0 到 65535
考慮一個值為 250 的 short 變數。
它在計算機中以如下方式儲存（以二進位制格式）
00000000 11111010
一個數的補碼是該數的位翻轉後的數。它用 ~ 表示
例如，~250 是 11111111 00000101
負數使用 2 的補碼系統儲存。根據該系統，-n=~n+1
-250 儲存為 11111111 00000110
http://stackoverflow.com/questions/1049722/what-is-2s-complement
10000000 00000000 (-32768) 沒有正數對應項。它的負數是它本身（嘗試 -n=~n+1）
如果資料型別是 unsigned，11100010 01110101 將被讀取為 57973，而如果資料型別是 signed，則將被讀取為 -7563。如果將 65536（範圍）新增到 -7563，您將得到 57973。
溢位
考慮一個數據型別 var_t，大小為 1 位元組（範圍為 256）
signed var_t a,b;
unsigned var_t c,d;
如果 c 為 200(11001000)，d 為 100(01100100)，則 c+d 為 300(00000001 00101100)，這大於最大值 255(11111111)。 00000001 00101100 大於一個位元組，因此高位位元組將被拒絕，c+d 將被讀取為 44。所以，200+100=44！這很荒謬！（注意 44=300-256）。這是一個無符號溢位的例子，其中該值無法儲存在可用的位元組數中。在這種溢位中，結果會模範圍（這裡是 256）。
如果 a 為 100(01100100)，b 為 50(00110010)，則 a+b 為 150(10010110)，這大於最大值 127。相反，a+b 將被讀取為 -106（注意 -106=150-256）。這是一個有符號溢位的例子，其中結果會模範圍（這裡是 256）。
除法和取模永遠不會產生溢位。
加法溢位
只有在被加的數字的符號相同時才會發生溢位（無符號數始終是這種情況）
可以透過檢視其符號與運算元的符號相反來輕鬆檢測有符號溢位。
讓我們分析一下無符號整數加法中的溢位。
考慮一個數據型別的兩個變數 a 和 b，大小為 n，範圍為 R。
設 + 是實際的數學加法，a$b 是計算機進行的加法。
如果 a+b<=R-1, a$b=a+b
由於 a 和 b 是無符號的，a$b 大於或等於 a 和 b。
如果 a+b>=R a$b=a+b-R
由於 R 大於 a 和 b，a-R 和 b-R 為負數
所以，a+b-R<a 和 a+b-R<b
因此，a$b 小於 a 和 b。
這種差異可用於檢測無符號加法溢位。 a-b 可以被視為 a+(-b)，因此可以以相同的方式處理減法。
乘法溢位：有兩種方法可以檢測溢位
1. 如果 a*b>max，則 a>max/b（如果 unsigned，max 為 R-1，如果 signed，max 為 R/2-1）。
2. 假設存在一個大小為 n 且範圍為 R 的資料型別，稱為 var_t，以及一個大小為 2n 的資料型別，稱為 var2_t。
假設有兩個 var_t 變數 a 和 b。 var2_t 的範圍將是 R*R，它總是大於 a 和 b 的乘積。因此，如果 var2_t(a)*var2_t(b)>R，則發生了溢位。
截斷：當從較長的變數分配給較短的變數時，會發生這種情況。例如，
如果將 int 替換為 unsigned short，也會顯示類似的行為。
型別轉換： 考慮
每當在相同型別的無符號變數和有符號變數之間執行操作時，運算元都會轉換為無符號型別。
每當在 long 型別和 short 型別之間執行操作時，運算元都會轉換為 long 型別。
上面的程式碼返回 1，因為 a 和 b 被轉換為 unsigned int，然後進行比較。
如果我們使用 __int64（一個 64 位型別）而不是 unsigned int，並使用 18446744073709551610 而不是 4294967290，結果將會相同。
型別提升： 每當對型別短於 int 的兩個變數執行操作時，這兩個變數的型別都會轉換為 int。 例如。
在本文中，我們只處理整數型別（而不處理像 float 和 double 這樣的型別）
為了理解如何解決這個問題，我們將首先了解數字是如何儲存的。
關於整數
如果資料型別的大小為 n 位元組，則它可以儲存 28n 個不同的值。這被稱為資料型別的範圍。
如果無符號資料型別的大小為 n 位元組，則範圍為 0 到 28n-1
如果帶符號資料型別的大小為 n 位元組，則範圍為 -28n-1 到 28n-1-1
因此，short（通常為 2 位元組）的範圍為 -32768 到 32767，而 unsigned short 的範圍為 0 到 65535
考慮一個值為 250 的 short 變數。
它在計算機中以如下方式儲存（以二進位制格式）
00000000 11111010
一個數的補碼是該數的位翻轉後的數。它用 ~ 表示
例如，~250 是 11111111 00000101
負數使用 2 的補碼系統儲存。根據該系統，-n=~n+1
-250 儲存為 11111111 00000110
http://stackoverflow.com/questions/1049722/what-is-2s-complement
10000000 00000000 (-32768) 沒有正數對應項。它的負數是它本身（嘗試 -n=~n+1）
如果資料型別是 unsigned，11100010 01110101 將被讀取為 57973，而如果資料型別是 signed，則將被讀取為 -7563。如果將 65536（範圍）新增到 -7563，您將得到 57973。
溢位
考慮一個數據型別 var_t，大小為 1 位元組（範圍為 256）
signed var_t a,b;
unsigned var_t c,d;
如果 c 為 200(11001000)，d 為 100(01100100)，則 c+d 為 300(00000001 00101100)，這大於最大值 255(11111111)。 00000001 00101100 大於一個位元組，因此高位位元組將被拒絕，c+d 將被讀取為 44。所以，200+100=44！這很荒謬！（注意 44=300-256）。這是一個無符號溢位的例子，其中該值無法儲存在可用的位元組數中。在這種溢位中，結果會模範圍（這裡是 256）。
如果 a 為 100(01100100)，b 為 50(00110010)，則 a+b 為 150(10010110)，這大於最大值 127。相反，a+b 將被讀取為 -106（注意 -106=150-256）。這是一個有符號溢位的例子，其中結果會模範圍（這裡是 256）。
檢測溢位
除法和取模永遠不會產生溢位。
加法溢位
只有在被加的數字的符號相同時才會發生溢位（無符號數始終是這種情況）
可以透過檢視其符號與運算元的符號相反來輕鬆檢測有符號溢位。
讓我們分析一下無符號整數加法中的溢位。
考慮一個數據型別的兩個變數 a 和 b，大小為 n，範圍為 R。
設 + 是實際的數學加法，a$b 是計算機進行的加法。
如果 a+b<=R-1, a$b=a+b
由於 a 和 b 是無符號的，a$b 大於或等於 a 和 b。
如果 a+b>=R a$b=a+b-R
由於 R 大於 a 和 b，a-R 和 b-R 為負數
所以，a+b-R<a 和 a+b-R<b
因此，a$b 小於 a 和 b。
這種差異可用於檢測無符號加法溢位。 a-b 可以被視為 a+(-b)，因此可以以相同的方式處理減法。
乘法溢位：有兩種方法可以檢測溢位
1. 如果 a*b>max，則 a>max/b（如果 unsigned，max 為 R-1，如果 signed，max 為 R/2-1）。
2. 假設存在一個大小為 n 且範圍為 R 的資料型別，稱為 var_t，以及一個大小為 2n 的資料型別，稱為 var2_t。
假設有兩個 var_t 變數 a 和 b。 var2_t 的範圍將是 R*R，它總是大於 a 和 b 的乘積。因此，如果 var2_t(a)*var2_t(b)>R，則發生了溢位。
截斷：當從較長的變數分配給較短的變數時，會發生這種情況。例如，
short a;long b=70000;a=b; 只複製低位，並且值的含義被轉換。short a;int b=57973;a=b; 也會顯示此行為，變為 -7563。如果將 int 替換為 unsigned short，也會顯示類似的行為。
型別轉換： 考慮
unsigned int a=4294967290;int b=-6; return (a==b); 這返回 1。每當在相同型別的無符號變數和有符號變數之間執行操作時，運算元都會轉換為無符號型別。
每當在 long 型別和 short 型別之間執行操作時，運算元都會轉換為 long 型別。
上面的程式碼返回 1，因為 a 和 b 被轉換為 unsigned int，然後進行比較。
如果我們使用 __int64（一個 64 位型別）而不是 unsigned int，並使用 18446744073709551610 而不是 4294967290，結果將會相同。
型別提升： 每當對型別短於 int 的兩個變數執行操作時，這兩個變數的型別都會轉換為 int。 例如。
short a=32000,b=32000;cout<<a+b<<endl; 將顯示 64000，這大於 short 的最大值。 原因是 a 和 b 被轉換為 int，a+b 將返回一個 int，它可以具有 64000 的值。