[c++] 如何檢測整數溢出?



Answers

我看到你正在使用無符號整數。 根據定義, 在C中 (不知道C ++),無符號算術不會溢出......所以,至少對於C來說,你的觀點是沒有意義的:)

使用帶符號整數,一旦發生溢出,就會發生未定義行為 ,並且您的程序可以執行任何操作(例如:渲染測試無結果)。

#include <limits.h>
int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* unreliable test */
  /* ... */
}

要創建一個合格的程序,您需要產生溢出之前測試溢出。 該方法也可以與無符號整數一起使用

// for addition
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */;
if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */;
// for subtraction
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x < 0) && (a > INT_MAX + x)) /* `a - x` would overflow */;
if ((x > 0) && (a < INT_MIN + x)) /* `a - x` would underflow */;
// for multiplication
#include <limits.h>
int a = <something>;
int x = <something>;
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;
// there may be need to check for -1 for two's complement machines
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */

除了INT_MIN-1特殊情況外,不可能超過INT_MININT_MAX

Question

我正在用C ++編寫一個程序來查找b = c的所有解,其中abc一起使用0-9的所有數字。 該程序循環遍歷ab的值,並且每次在abb上運行一個數字計數例程以檢查數字條件是否滿足。

但是,當b溢出整數限制時,可能會生成偽解。 我結束了檢查這個使用代碼,如:

unsigned long b, c, c_test;
...
c_test=c*b;         // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test;      // No overflow

有沒有更好的溢出測試方法? 我知道一些芯片有一個內部標誌,當溢出發生時被設置,但我從來沒有見過它通過C或C ++訪問。




It depends what you use it for. Performing unsigned long(DWORD) addition or Multiplication the best solution is to use ULARGE_INTEGER.

ULARGE_INTEGER is a structure of two DWORDs. The full value can be accessed as "QuadPart" while the hi DWORD is accessed as "HighPart" and the low DWORD is accessed as "LowPart"

例如:

DWORD My Addition(DWORD Value_A,DWORD Value_B) { ULARGE_INTEGER a,b;

   b.LowPart = Value_A;  // a 32 bit value(up to 32 bit)
   b.HighPart = 0;
   a.LowPart = Value_B;  // a 32 bit value(up to 32 bit)
   a.HighPart = 0;

   a.QuadPart += b.QuadPart;

   // if  a.HighPart
   // Then a.HighPart contains the overflow(carry)

   return (a.LowPart + a.HighPart)

// any overflow is stored in a.HighPart(up to 32 bits)




Calculate the results with doubles. They have 15 significant digits. Your requirement has a hard upper bound on c of 10 8 — it can have at most 8 digits. Hence, the result will be precise if it's in range, and it will not overflow otherwise.




CERT has developed a new approach to detecting and reporting signed integer overflow, unsigned integer wrapping, and integer truncation using the "as-if" infinitely ranged (AIR) integer model. CERT has published a technical report describing the model and produced a working prototype based on GCC 4.4.0 and GCC 4.5.0.

The AIR integer model either produces a value equivalent to one that would have been obtained using infinitely ranged integers or results in a runtime constraint violation. Unlike previous integer models, AIR integers do not require precise traps, and consequently do not break or inhibit most existing optimizations.




Inline assembly lets you check the overflow bit directly. If you are going to be using C++, you really should learn assembly.




我看到很多人回答了溢出問題,但我想解決他最初的問題。 他說問題是要找到一個b = c,這樣所有數字都可以不用重複使用​​。 好的,這不是他在這篇文章中提出的問題,但我仍然認為有必要研究問題的上限並得出結論,他永遠不需要計算或檢測溢出(注意:我不熟練在數學中,所以我一步一步做了這個,但最終的結果非常簡單,以至於這可能有一個簡單的公式)。

要點是,問題對a,b或c所要求的上限是98.765.432。 無論如何,首先在瑣碎和不平凡的部分分解問題:

  • x 0 == 1(9,8,7,6,5,4,3,2的所有置換都是解)
  • x 1 == x(沒有可能的解決方案)
  • 0 b == 0(無法解決)
  • 1 b == 1(無法解決)
  • a b ,a> 1,b> 1(非平凡)

現在我們只需要證明沒有其他解決方案是可行的,只有排列是有效的(然後打印它們的代碼是微不足道的)。 我們回到上限。 其實上限是c≤98.765.432。 這是上限,因為它是8位數字的最大數字(總共10位數字,每個a和b減1)。 這個上限僅適用於c,因為a和b的界限必須低得多,因為我們可以計算出指數增長,從b變化到上界:

    9938.08^2 == 98765432
    462.241^3 == 98765432
    99.6899^4 == 98765432
    39.7119^5 == 98765432
    21.4998^6 == 98765432
    13.8703^7 == 98765432
    9.98448^8 == 98765432
    7.73196^9 == 98765432
    6.30174^10 == 98765432
    5.33068^11 == 98765432
    4.63679^12 == 98765432
    4.12069^13 == 98765432
    3.72429^14 == 98765432
    3.41172^15 == 98765432
    3.15982^16 == 98765432
    2.95305^17 == 98765432
    2.78064^18 == 98765432
    2.63493^19 == 98765432
    2.51033^20 == 98765432
    2.40268^21 == 98765432
    2.30883^22 == 98765432
    2.22634^23 == 98765432
    2.15332^24 == 98765432
    2.08826^25 == 98765432
    2.02995^26 == 98765432
    1.97741^27 == 98765432

注意,例如最後一行:它表示1.97 ^ 27〜98M。 因此,例如,1 ^ 27 == 1和2 ^ 27 == 134.217.728,這不是一個解決方案,因為它有9位數字(2> 1.97,所以它實際上比應該測試的大)。 可以看出,可用於測試a和b的組合非常小。 對於b == 14,我們需要嘗試2和3.對於b == 3,我們從2開始並在462結束。所有結果被授予小於〜98M。

現在只需測試以上所有組合,並查找不重複任何數字的組合:

    ['0', '2', '4', '5', '6', '7', '8'] 2^84 = 7056
    ['1', '2', '3', '4', '5', '8', '9'] 2^59 = 3481
    ['0', '1', '2', '3', '4', '5', '8', '9'] 2^59 = 3481 (+leading zero)
    ['1', '2', '3', '5', '8'] 3^8 = 512
    ['0', '1', '2', '3', '5', '8'] 3^8 = 512 (+leading zero)
    ['1', '2', '4', '6'] 2^4 = 16
    ['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
    ['1', '2', '4', '6'] 4^2 = 16
    ['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
    ['1', '2', '8', '9'] 2^9 = 81
    ['0', '1', '2', '8', '9'] 2^9 = 81 (+leading zero)
    ['1', '3', '4', '8'] 4^3 = 81
    ['0', '1', '3', '4', '8'] 4^3 = 81 (+leading zero)
    ['2', '3', '6', '7', '9'] 6^3 = 729
    ['0', '2', '3', '6', '7', '9'] 6^3 = 729 (+leading zero)
    ['2', '3', '8'] 3^2 = 8
    ['0', '2', '3', '8'] 3^2 = 8 (+leading zero)
    ['2', '3', '9'] 2^3 = 9
    ['0', '2', '3', '9'] 2^3 = 9 (+leading zero)
    ['2', '4', '6', '8'] 2^8 = 64
    ['0', '2', '4', '6', '8'] 2^8 = 64 (+leading zero)
    ['2', '4', '7', '9'] 2^7 = 49
    ['0', '2', '4', '7', '9'] 2^7 = 49 (+leading zero)

沒有一個符合問題(這也可以通過不存在'0','1',...,'9')來看到。

解決它的示例代碼如下。 還要注意這是用python編寫的,並不是因為它需要任意的精度整數(代碼不會計算任何大於9800萬的值),而是因為我們發現測試的數量太小,以至於我們應該使用高級語言利用其內置的容器和庫(注:代碼有28行)。

    import math

    m = 98765432
    l = []
    for i in xrange(2, 98765432):
        inv = 1.0/i
        r = m**inv
        if (r < 2.0): break
        top = int(math.floor(r))
        assert(top <= m)

        for j in xrange(2, top+1):
            s = str(i) + str(j) + str(j**i)
            l.append((sorted(s), i, j, j**i))
            assert(j**i <= m)

    l.sort()
    for s, i, j, ji in l:
        assert(ji <= m)
        ss = sorted(set(s))
        if s == ss:
            print '%s %d^%d = %d' % (s, i, j, ji)

        # Try with non significant zero somewhere
        s = ['0'] + s
        ss = sorted(set(s))
        if s == ss:
            print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)



儘管已經兩年了,但我覺得我不妨加入我的馬里諾斯來實現一種非常快速的方法來檢測溢出,至少可以增加,這可能會帶來乘法,除法和權力

這個想法正是因為處理器會讓值回到零,並且C / C ++將從任何特定的處理器中抽像出來,您可以:

uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);

這既保證瞭如果一個操作數是零而另一個不是,那麼溢出就不會被錯誤地檢測出來,並且比以前提到的大量NOT / XOR / AND /測試操作快得多。

編輯 :正如指出的,這種方法雖然比其他更精細的方法更好,但仍然是可以優化的。 以下是包含優化的原始代碼的修訂:

uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < x; // Alternatively "value < y" should also work



You can't access the overflow flag from C/C++.

I don't agree with this. You could write some inline asm and use a jo (jump overflow) instruction assuming you are on x86 to trap the overflow. Of course you code would no longer be portable to other architectures.

look at info as and info gcc .




我需要回答這個浮點數的相同問題,其中位掩碼和移位看起來並不樂觀。 我解決的方法適用於有符號和無符號,整數和浮點數。 即使沒有更大的數據類型以促進中間計算,它也可以工作。 它不是所有這些類型中最有效率的,但是因為它對所有這些類型都有效,所以值得使用。

簽名溢出測試,加法和減法:

  1. 獲取表示類型MAXVALUE和MINVALUE的最大和最小可能值的常量。

  2. 計算和比較操作數的符號。

    一個。 如果任一值為零,則加法和減法都不會溢出。 跳過剩餘的測試。

    灣 如果符號相反,則添加不能溢出。 跳過剩餘的測試。

    C。 如果符號相同,則減法不能溢出。 跳過剩餘的測試。

  3. 測試MAXVALUE的正溢出。

    一個。 如果兩個符號均為正數,且MAXVALUE - A <B,則加法將溢出。

    灣 如果B的符號是負數且MAXVALUE - A <-B,則減法將溢出。

  4. 測試MINVALUE的負溢出。

    一個。 如果兩個符號均為負值且MINVALUE - A> B,則加法將溢出。

    灣 如果A的符號是負數並且MINVALUE - A> B,則減法將溢出。

  5. 否則,不會溢出。

簽名溢出測試,乘法和除法:

  1. 獲取表示類型MAXVALUE和MINVALUE的最大和最小可能值的常量。

  2. 計算並比較操作數的大小(絕對值)。 (下面,假設A和B是這些大小,而不是簽名的原稿。)

    一個。 如果任一值為零,則乘法不能溢出,並且除法將產生零或無窮大。

    灣 如果任一值為1,則乘法和除法不能溢出。

    C。 如果一個操作數的大小低於1,另一個大於1,則乘法不能溢出。

    d。 如果幅度都小於1,則劃分不能溢出。

  3. 測試MAXVALUE的正溢出。

    一個。 如果兩個操作數都大於1且MAXVALUE / A <B,則乘法將溢出。

    灣 如果B小於1並且MAXVALUE * B <A,那麼除法將溢出。

  4. 否則,不會溢出。

注意:MINVALUE的最小溢出由3處理,因為我們取絕對值。 但是,如果ABS(MINVALUE)> MAXVALUE,那麼我們會有一些罕見的誤報。

下溢測試類似,但涉及EPSILON(最大正數大於零)。




一些編譯器提供了訪問CPU中的整數溢出標誌,然後可以測試,但這不是標準的。

在執行乘法之前,您還可以測試溢出的可能性:

if ( b > ULONG_MAX / a ) // a * b would overflow



clang現在支持對有符號和無符號整數進行動態溢出檢查。 請參閱-fsanitize=integer切換。 目前,只有一個C ++編譯器支持完全支持動態溢出檢查以進行調試。




mozilla::CheckedInt<T> provides overflow-checked integer math for integer type T (using compiler intrinsics on clang and gcc as available). The code is under MPL 2.0 and depends on three ( IntegerTypeTraits.h , Attributes.h and Compiler.h ) other header-only non-standard library headers plus Mozilla-specific assertion machinery . You probably want to replace the assertion machinery if you import the code.




#include <stdio.h>
#include <stdlib.h>

#define MAX 100 

int mltovf(int a, int b)
{
    if (a && b) return abs(a) > MAX/abs(b);
    else return 0;
}

main()
{
    int a, b;

    for (a = 0; a <= MAX; a++)
        for (b = 0; b < MAX; b++) {

        if (mltovf(a, b) != (a*b > MAX)) 
            printf("Bad calculation: a: %d b: %d\n", a, b);

    }
}



最簡單的方法是將unsigned long s轉換為unsigned long long s,進行乘法運算並將結果與0x100000000LL進行比較。

您可能會發現,這比您在示例中完成的部門更高效。

噢,它可以在C和C ++中工作(正如你用這兩個標記問題一樣)。

剛剛看了一下glibc手冊 。 作為SIGFPE一部分,提到了一個整數溢出陷阱( FPE_INTOVF_TRAP )。 除了手冊中令人討厭的部分之外,這將是理想的:

FPE_INTOVF_TRAP整數溢出(除非您以硬件特定的方式啟用溢出陷阱,否則在C程序中不可能)。

有點恥辱真的。




To expand on Head Geek's answer, there is a faster way to do the addition_is_safe ;

bool addition_is_safe(unsigned int a, unsigned int b)
{
    unsigned int L_Mask = std::numeric_limits<unsigned int>::max();
    L_Mask >>= 1;
    L_Mask = ~L_Mask;

    a &= L_Mask;
    b &= L_Mask;

    return ( a == 0 || b == 0 );
}

This uses machine-architecture safe, in that 64-bit and 32-bit unsigned integers will still work fine. Basically, I create a mask that will mask out all but the most significant bit. Then, I mask both integers, and if either of them do not have that bit set, then addition is safe.

This would be even faster if you pre-initialize the mask in some constructor, since it never changes.






Related