# 如何检测整数溢出？

``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` `

` `bool addition_is_safe(uint32_t a, uint32_t b) { size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b); return (a_bits<32 && b_bits<32); }` `

` `bool multiplication_is_safe(uint32_t a, uint32_t b) { size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b); return (a_bits+b_bits<=32); }` `

` `bool exponentiation_is_safe(uint32_t a, uint32_t b) { size_t a_bits=highestOneBitPosition(a); return (a_bits*b<=32); }` `

（当然，用目标整数代替位数。）

` `size_t highestOneBitPosition(uint32_t a) { size_t bits=0; while (a!=0) { ++bits; a>>=1; }; return bits; }` `

` `#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 */` `

` `unsigned long b, c, c_test; if (__builtin_umull_overflow(b, c, &c_test)) { // returned non-zero: there has been an overflow } else { // return zero: there hasn't been an overflow }` `

Clang文档没有指定如果发生溢出， `c_test`是否包含溢出的结果，但GCC文档说明了这一点。 鉴于这两个人喜欢与`__builtin`兼容，那么可以肯定的是，这也是Clang的工作原理。

• `u`表示无符号`s`表示签名 ;
• 操作是`add``sub``mul` ;
• 没有后缀表示操作数是`int` ; 一个意味着`long` ; 两个意思`long long`

GCC 5+和Clang 3.8+还提供通用的内build函数，不需要指定值的types：__builtin_add_overflow，__builtin_sub_overflow和`__builtin_mul_overflow` 。 这些也适用于小于`int`types。

Visual Studio的cl.exe没有直接的等价物。 对于无符号的加法和减法，包括`<intrin.h>`将允许使用`addcarry_uNN``addcarry_uNN` （其中NN是位数，如`addcarry_u8``addcarry_u8` ）。 他们的签名有些迟钝：

` `unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum); unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);` `

`c_in` / `b_in`是input的进位/借位标志，返回值是进位/借位输出。 它似乎没有签名操作或乘法的等价物。

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

` `if (a + b < a) { /* deal with overflow */ }` `

` `b = abs(a); if (b < 0) { /* deal with overflow */ }` `

`-fwrapv`编译解决了这个问题，但是禁用了一些优化。

` `#include <cstddef> #if defined( _MSC_VER ) #include <intrin.h> #endif inline size_t query_intel_x86_eflags( const size_t query_bit_mask ) { #if defined( _MSC_VER ) return __readeflags() & query_bit_mask; #elif defined( __GNUC__ ) // this code will work only on 64-bit GNU-C machines; // Tested and does NOT work with Intel C++ 10.1! size_t eflags; __asm__ __volatile__( "pushfq \n\t" "pop %%rax\n\t" "movq %%rax, %0\n\t" :"=r"(eflags) : :"%rax" ); return eflags & query_bit_mask; #else #pragma message("No inline assembly will work with this compiler!") return 0; #endif } int main(int argc, char **argv) { int x = 1000000000; int y = 20000; int z = x * y; int f = query_intel_x86_eflags( 0x801 ); printf( "%X\n", f ); }` `

• x 0 == 1（9，8，7，6，5，4，3，2的所有置换都是解）
• x 1 == x（没有可能的解决scheme）
• 0 b == 0（没有解决scheme）
• 1 b == 1（没有解决scheme）
• a b ，a> 1，b> 1（非平凡）

` ` 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` `

` ` ['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)` `

` ` 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)` `

` `uint8_t x, y; /* give these values */ const uint16_t data16 = x + y; const bool carry = (data16 > 0xff); const bool overflow = ((~(x ^ y)) & (x ^ data16) & 0x80);` `

`FPE_INTOVF_TRAP`整数溢出（在C程序中是不可能的，除非您以硬件特定的方式启用溢出陷阱）。

` `unsigned int r, a, b; r = a+b; if (r < a) { // overflow }` `

` `signed int r, a, b, s; r = a+b; s = a>=0; if (s == (b>=0) && s != (r>=0)) { // overflow }` `

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

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

1. 获取表示typesMAXVALUE和MINVALUE的最大和最小可能值的常量。

2. 计算和比较操作数的符号。

一个。 如果任一值为零，则加法和减法都不能溢出。 跳过剩余的testing。

湾 如果符号相反，则加法不能溢出。 跳过剩余的testing。

C。 如果符号相同，则减法不能溢出。 跳过剩余的testing。

3. testingMAXVALUE的正溢出。

一个。 如果两个符号均为正数，且MAXVALUE – A <B，则加法将溢出。

湾 如果B的符号是负的，MAXVALUE – A <-B，则减法将溢出。

4. testingMINVALUE的负溢出。

一个。 如果两个符号均为负值，且MINVALUE – A> B，则加法将溢出。

湾 如果A的符号是负数，MINVALUE – A> B，则减法将溢出。

5. 否则，不会溢出。

1. 获取表示typesMAXVALUE和MINVALUE的最大和最小可能值的常量。

2. 计算并比较操作数的大小（绝对值）。 （下面，假设A和B是这些大小，而不是签名的原件。）

一个。 如果任一值为零，则乘法不能溢出，并且除法将产生零或无穷大。

湾 如果任一值为1，则乘法和除法不能溢出。

C。 如果一个操作数的大小小于1，另一个大于1，则乘法不能溢出。

d。 如果幅度都小于1，则划分不能溢出。

3. testingMAXVALUE的正溢出。

一个。 如果两个操作数都大于1且MAXVALUE / A <B，则乘法将溢出。

湾 如果B小于1且MAXVALUE * B <A，则分频将溢出。

4. 否则，不会溢出。

` `CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> : Op: +, Reason : Signed Addition Overflow, BINARY OPERATION: left (int32): 2147483647 right (int32): 1` `

CERT开发了一种使用“as-if”无限范围（AIR）整数模型检测和报告带符号整数溢出，无符号整数回绕和整数截断的新方法。 CERT发布了一个描述该模型的技术报告 ，并基于GCC 4.4.0和GCC 4.5.0生成了一个工作原型。

AIR整数模型要么产生一个相当于使用无限范围整数获得的值，要么导致运行时间约束冲突。 Unlike previous integer models, AIR integers do not require precise traps, and consequently do not break or inhibit most existing optimizations.

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.

Another variant of solution using assembler is an external procedure. This example for unsigned integer multiplication using g++ and fasm under linux x64.

This procedure multiplies two unsigned integer arguments (32 bits) (according to specification for amd64 (section 3.2.3 Parameter Passing)

If the class is INTEGER, the next available register of the sequence %rdi,%rsi,%rdx,%rcx,%r8 and %r9 is used

(edi and esi registers in my code)) and returns the result or 0 if an overflow has occured.

` `format ELF64 section '.text' executable public u_mul u_mul: MOV eax, edi mul esi jnc u_mul_ret xor eax, eax u_mul_ret: ret` `

testing：

` `extern "C" unsigned int u_mul(const unsigned int a, const unsigned int b); int main() { printf("%u\n", u_mul(4000000000,2));//0 printf("%u\n", u_mul(UINT_MAX/2,2));//ok return 0; }` `

link program with asm object file. In my case in Qt Creator add it to LIBS in a .pro file

Try this macro to test the overflow bit of 32-bit machines (adapted the solution of Angel Sinigersky)

` `#define overflowflag(isOverflow){ \ size_t eflags; \ asm ("pushfl ;" \ "pop %%eax" \ : "=a" (eflags)); \ isOverflow = (eflags >> 11) & 1;}` `

I defined it as a macro because otherwise the overflow bit would have been overwritten.

Subsequent is a little application with the code segement above:

` `#include <cstddef> #include <stdio.h> #include <iostream> #include <conio.h> #if defined( _MSC_VER ) #include <intrin.h> #include <oskit/x86> #endif using namespace std; #define detectOverflow(isOverflow){ \ size_t eflags; \ asm ("pushfl ;" \ "pop %%eax" \ : "=a" (eflags)); \ isOverflow = (eflags >> 11) & 1;} int main(int argc, char **argv) { bool endTest = false; bool isOverflow; do { cout << "Enter two intergers" << endl; int x = 0; int y = 0; cin.clear(); cin >> x >> y; int z = x * y; detectOverflow(isOverflow) printf("\nThe result is: %d", z); if (!isOverflow) { std::cout << ": no overflow occured\n" << std::endl; } else { std::cout << ": overflow occured\n" << std::endl; } z = x * x * y; detectOverflow(isOverflow) printf("\nThe result is: %d", z); if (!isOverflow) { std::cout << ": no overflow ocurred\n" << std::endl; } else { std::cout << ": overflow occured\n" << std::endl; } cout << "Do you want to stop? (Enter \"y\" or \"Y)" << endl; char c = 0; do { c = getchar(); } while ((c == '\n') && (c != EOF)); if (c == 'y' || c == 'Y') { endTest = true; } do { c = getchar(); } while ((c != '\n') && (c != EOF)); } while (!endTest); }` `

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

look at `info as` and `info gcc` .

Catching Integer Overflows in C points out a solution more general than the one discussed by CERT (it is more general in term of handled types), even if it requires some GCC extensions (I don't know how widely supported they are).

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

A clean way to do it would be to override all operators (+ and * in particular) and check for an overflow before perorming the operations.

@MSalters: Good idea.

If the integer calculation is required (for precision), but floating point is available, you could do something like:

` `uint64_t foo( uint64_t a, uint64_t b ) { double dc; dc = pow( a, b ); if ( dc < UINT_MAX ) { return ( powu64( a, b ) ); } else { // overflow } }` `

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.

x86 instruction set includes unsigned multiply instruction that stores the result to two registers. To use that instruction from C one can write following code in 64bit program (gcc):

` `unsigned long checked_imul(unsigned long a, unsigned long b) { __int128 res = (__int128)a * (__int128)b; if ((unsigned long)(res >> 64)) printf("overflow in integer multiply"); return (unsigned long)res; }` `

For 32bit program one needs to make result 64 bit and parameters 32bit.

Alternative is to use compiler depend instincts to check the flag register. GCC documentation for overflow instincts can be found from https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

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)

The simple way to test for overflow is to do validation by checking whether the current value is less than the previous value. For example, suppose you had a loop to print the powers of 2:

` `long lng; int n; for (n = 0; n < 34; ++n) { lng = pow (2, n); printf ("%li\n", lng); }` `

Adding overflow checking the way that I described results in this:

` `long signed lng, lng_prev = 0; int n; for (n = 0; n < 34; ++n) { lng = pow (2, n); if (lng <= lng_prev) { printf ("Overflow: %i\n", n); /* Do whatever you do in the event of overflow. */ } printf ("%li\n", lng); lng_prev = lng; }` `

It works for unsigned values as well as both positive and negative signed values.

Of course, if you wanted to do something similar for decreasing values instead of increasing values, you would flip the `<=` sign to make it `>=` , assuming the behaviour of underflow is the same as the behaviour of overflow. In all honesty, that's about as portable as you'll get without access to a CPU's overflow flag (and that would require inline assembly code, making your code non-portable across implementations anyway).

To perform an unsigned multiplication without overflowing in a portable way the following can be used:

` `... /* begin multiplication */ unsigned multiplicand, multiplier, product, productHalf; int zeroesMultiplicand, zeroesMultiplier; zeroesMultiplicand = number_of_leading_zeroes( multiplicand ); zeroesMultiplier = number_of_leading_zeroes( multiplier ); if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow; productHalf = multiplicand * ( c >> 1 ); if( (int)productHalf < 0 ) goto overflow; product = productHalf * 2; if( multiplier & 1 ){ product += multiplicand; if( product < multiplicand ) goto overflow; } ..../* continue code here where "product" is the correct product */ .... overflow: /* put overflow handling code here */ int number_of_leading_zeroes( unsigned value ){ int ctZeroes; if( value == 0 ) return 32; ctZeroes = 1; if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; } if( ( value >> 24 ) == 0 ){ ctZeroes += 8; value = value << 8; } if( ( value >> 28 ) == 0 ){ ctZeroes += 4; value = value << 4; } if( ( value >> 30 ) == 0 ){ ctZeroes += 2; value = value << 2; } ctZeroes -= x >> 31; return ctZeroes; }` `
` `#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: %db: %d\n", a, b); } }` `