如何在檢測兩個2的補碼整數時檢測溢出？

Question

我想乘兩個數字，並檢測是否有溢出。什麼是最簡單的方法來做到這一點？

Answer 1

檢查一個是否小於最大值除以另一個。 （所有值都被視爲絕對值）。

2的complementness幾乎沒有什麼關係了，因爲乘法溢出如果x *（2 ^Ñ - X）> 2 ^中號，其等於（X * 2 ^Ñ - X ）> 2 ^中號，或x <（X * 2 ^ñ - 2 ^中號），所以你必須四溢的數字反正比較（X 可能溢出，而結果可能不）。

Answer 2

替代帕維爾Shved的解決方案......

如果您選擇的語言是彙編程序，那麼你應該能夠檢查溢出標誌。如果沒有，你可以編寫一個自定義的彙編程序例程，如果溢出標誌被設置，它將設置一個變量。

如果這是不可接受的，您可以找到兩個值（絕對值）中最重要的設置位。如果總和超過整數（或無符號）中的位數，那麼如果它們相乘，則會發生溢出。

希望這會有所幫助。

Answer 3

如果你的號碼不是來自最大的積分數據類型，那麼你可能只是把它們放在一起，乘以並與數字原始類型的最大值進行比較。例如。在Java中，當將兩個int相乘時，可以將它們投射到long並將結果與​​Integer.MAX_VALUE或Integer.MIN_VALUE（取決於符號組合）進行比較，然後將結果降至int。

如果類型已經是最大的，那麼檢查一個是否小於最大值除以另一個。但不要拿絕對的價值！相反，您需要爲每個符號組合分別設置不同的比較邏輯。否則，pos可能會被歸約爲neg * neg。否則，pos可能會減少爲neg * neg。首先測試0個參數以允許安全分割。

對於實際的代碼，看到MathUtils類公地數學2，或commons-math 3ArithmeticUtils的Java源代碼。尋找public static long mulAndCheck(long a, long b)。爲正 a和b的情況下是

// check for positive overflow with positive a, positive b 
if (a <= Long.MAX_VALUE/b) { 
    ret = a * b; 
} else { 
    throw new ArithmeticException(msg); 
} 

Answer 4

乘以64位回答兩個32位數字的結果，2 787-8得到16等二進制乘法被簡單地轉移並加入。所以如果你說操作數A中設置了兩個32位操作數和位17，並且操作數b中設置了15或16以上的任何位，那麼你將溢出一個32位結果。位17左移16位33加到32。

所以問題的另一個問題是輸入的大小和結果的大小，如果結果是相同的大小，那麼你必須找到兩個操作數中最重要的一個，如果結果是比你的結果空間大，你會溢出。

EDIT

是乘以2個3位號將導致在任何一個5比特數或6比特數，如果有在添加了進位。同樣，2位和5位也可能導致6位或7位等等。如果這個問題出現問題的原因是爲了確定結果變量中是否有空格作爲答案，那麼這個解決方案將起作用，並且對於大多數大多數處理器的語言。在某些方面它可以明顯更快，而對其他方面則明顯更慢。它通常很快（取決於它當然如何實現）來查看操作數中的位數。如果您可以在您的語言或處理器內完成操作，則最大操作數的倍數是安全的。除了昂貴的代價（很慢）以外，大多數處理器在操作數大小任意加倍時都不會少得多。最快的當然是下降到彙編器做乘法並且看溢出位（或者比較一個結果寄存器爲零）。如果你的處理器無法在硬件中進行乘法運算，那麼無論你做什麼，它都會變得很慢。我猜測儘管速度最快，並且具有最準確的溢出狀態，但asm並不是這篇文章的正確答案。

二進制使得乘法小巫見大巫到小數，例如採用二進制數

 
0b100 * 
0b100 

就像在學校十進制數學，你（可以）開始與下操作的至少顯著位和乘以反對一切在上面的操作數中的位置，除了二進制外，只有兩個選擇，你乘以零，這意味着你不必添加到結果，或者你乘以一個，這意味着你只需移動和添加，不需要像你一樣的實際乘法有十進制。

 
    000 : 0 * 100 
000 : 0 * 100 
100 : 1 * 100 

添加了列，答案是0b10000

同十進制數學在數百列是指複製上面的數字並添加兩個零的1，它的工作原理同任何其他基地以及。因此，0b100次0b110是0b1000，第二列中的一個是如此複製並在第三列中添加一個零+ 0b10000，以便複製並添加兩個零= 0b11000。

這導致查看兩個數字中最重要的位。 0b1xx * 0b1xx保證將1xxxx添加到答案中，並且這是添加中的最大位位置，沒有其他最終添加的單個輸入會填充該列或填充更重要的列。從那裏你只需要更多的位，以防其他位被累加引起進位。

與最壞的情況下發生的所有那些時間所有的人，0b111 * 0b111

 
0b00111 + 
0b01110 + 
0b11100 

這導致進位，導致0b110001除。 6位。 3位操作數乘以3位操作數3 + 3 = 6位最壞情況。

因此，使用最高有效位（而不是保存值的寄存器的大小）的操作數大小決定了最差情況下的存儲要求。

那麼，假設積極的操作數是真的。如果你認爲這些數字有些是負面的，它會改變事情，但不會太多。

減4次5，0b1111 ... 111100 * 0b0000 .... 000101 = -20或0b1111..11101100

它需要4個位來表示負4個4位來表示一個正5 （不要忘記你的標誌位）。如果您剝離了所有符號位，我們的結果需要6位。

讓我們看看4位極端案例

 
-8 * 7 = -56 
0b1000 * 0b0111 = 0b1001000 
-1 * 7 = -7 = 0b1001 
-8 * -8 = 64 = 0b01000000 
-1 * -1 = 2 = 0b010 
-1 * -8 = 8 = 0b01000 
7 * 7 = 49 = 0b0110001 

比方說，我們算的正數爲最顯著1加一，負最顯著0加1。

 
-8 * 7 is 4+4=8 bits actual 7 
-1 * 7 is 1+4=5 bits, actual 4 bits 
-8 * -8 is 4+4=8 bits, actual 8 bits 
-1 * -1 is 1+1=2 bits, actual 3 bits 
-1 * -8 is 1+4=5 bits, actual 5 bits 
7 * 7 is 4+4=8 bits, actual 7 bits. 

所以這條規則的作品，爲-1 * -1，你可以看到，我叫了減一個一位，爲加一件事找到零加上一個例外。無論如何，我認爲如果這是一個4位* 4位機器，至少應該有4位結果，而我將這個問題解釋爲我需要超過4位來安全存儲答案。所以這個規則可以解決這個問題的2s補數學問題。

如果您的問題是要準確地確定溢出，然後速度是次要的，那麼，對於某些系統來說，對於每次乘法，它都會非常慢。如果這是你所問的問題，爲了獲得一些速度，你需要對語言和/或處理器稍微調整一點。如果可以，加大最大操作數，並檢查結果大小以上的非零位，或使用除法和比較。如果無法將操作數大小加倍，請進行除法和比較。在分割之前檢查零。

其實你的問題並沒有說明你正在談論什麼大小的溢出。良好的舊8086 16位16位給出了一個32位結果（硬件），它永遠不會溢出。那麼32位32位，32位乘法的32位乘法器容易溢出的問題呢？這個問題的操作數的大小是多少，它們是相同的大小還是它們的輸入大小的兩倍？你是否願意執行硬件無法做到的乘法（沒有溢出）？你是否正在編寫一個編譯器庫，並試圖確定是否可以將操作數提供給硬件以提高速度，或者如果必須在沒有硬件繁瑣的情況下執行數學運算。如果你建立了操作數，那麼你會得到哪種類型的東西，編譯器庫會嘗試在執行乘法操作之前將操作數退回，這取決於編譯器和它的庫。並且它會使用計數比特技巧來決定使用硬件乘法還是軟件。

我的目標是顯示二進制乘法是如何以可消化的形式工作的，所以您可以通過查找每個操作數中單個位的位置來查看需要多少最大存儲量。現在，您可以在每個操作數中找到那個位的速度有多快。如果您正在尋找不是最大值的最小存儲需求，那是不同的故事，因爲涉及兩個操作數中的每個重要位而不是每個操作數一個位，所以必須進行乘法運算以確定最小存儲。如果您不關心最大或最小存儲量，則只需執行乘法操作，並在您定義的溢出限制之上尋找非零值，或者如果您有時間或硬件則使用除法值。

你的標籤暗示你對浮點不感興趣，浮點是一個完全不同的野獸，你不能將任何這些固定點規則應用於浮點，他們不工作。

Answer 5

在C，這裏的一些成熟優化的代碼來處理全方位的角落情況：

int 
would_mul_exceed_int(int a, int b) { 
    int product_bits; 

    if (a == 0 || b == 0 || a == 1 || b == 1) return (0); /* always okay */ 
    if (a == INT_MIN || b == INT_MIN) return (1); /* always underflow */ 

    a = ABS(a); 
    b = ABS(b); 

    product_bits = significant_bits_uint((unsigned)a); 
    product_bits += significant_bits_uint((unsigned)b); 

    if (product_bits == BITS(int)) { /* cases where the more expensive test is required */ 
    return (a > INT_MAX/b); /* remember that IDIV and similar are very slow (dozens - hundreds of cycles) compared to bit shifts, adds */ 
    } 
    return (product_bits > BITS(int)); 
} 

Full example with test cases here

上述方法的好處是它不需要鑄造到更大類型，所以該方法可以在較大的整數類型上工作。