Como detectar estouro de inteiro?

Eu estava escrevendo um programa em C ++ para encontrar todas as soluções de um b = c , onde a , b e c juntos usam todos os dígitos 0-9 exatamente uma vez. O programa passava pelos valores de aeb , e executava uma rotina de contagem de dígitos a cada vez em a , b e a b para verificar se a condição de dígitos era satisfeita.

No entanto, soluções espúrias podem ser geradas quando um b ultrapassa o limite inteiro. Acabei de verificar isso usando código como:

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 

Existe uma maneira melhor de testar o estouro? Eu sei que alguns chips têm um sinalizador interno que é definido quando ocorre estouro, mas nunca o vi acessado através de C ou C ++.

    Existe uma maneira de determinar se uma operação é susceptível de transbordar, usando as posições dos one-bits mais significativos nos operandos e um pouco de conhecimento básico de matemática binária.

    Para além disso, quaisquer dois operandos resultarão em (no máximo) um bit a mais que o maior bit de um operando maior. Por exemplo:

     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); } 

    Para multiplicação, quaisquer dois operandos resultarão em (no máximo) a sum dos bits dos operandos. Por exemplo:

     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); } 

    Da mesma forma, você pode estimar o tamanho máximo do resultado de a para o poder de b assim:

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

    (Substitua o número de bits pelo seu inteiro alvo, é claro).

    Eu não tenho certeza do caminho mais rápido para determinar a posição do maior bit em um número, aqui está um método de força bruta:

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

    Não é perfeito, mas isso lhe dará uma boa idéia se dois números podem transbordar antes de você fazer a operação. Eu não sei se seria mais rápido do que simplesmente verificar o resultado da maneira que você sugeriu, por causa do loop na function highestOneBitPosition , mas poderia (especialmente se você soubesse quantos bits estavam nos operandos de antemão).

    Eu vejo que você está usando números inteiros sem sinal. Por definição, em C (não sei sobre C ++), aritmética não assinada não estourar … então, pelo menos para C, seu ponto é discutível 🙂

    Com números inteiros assinados, uma vez que haja estouro, Ocorreu um comportamento indefinido e seu programa pode fazer qualquer coisa (por exemplo: renderizar testes inconclusivos).

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

    Para criar um programa em conformidade, você precisa testar o estouro antes de gerar o referido estouro. O método também pode ser usado com números inteiros sem sinal

     // for addition #include  int a = ; int x = ; 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  int a = ; int x = ; 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  int a = ; int x = ; 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 */ 

    para divisão (exceto para o caso especial INT_MIN e -1 ) não há possibilidade de ultrapassar INT_MIN ou INT_MAX .

    Clang 3.4+ e GCC 5+ oferecem checkins aritméticos controlados. Eles oferecem uma solução muito rápida para esse problema, especialmente quando comparados a verificações de segurança de testes de bit.

    Para o exemplo da pergunta do OP, funcionaria assim:

     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 } 

    A documentação do Clang não especifica se c_test contém o resultado transbordado se um estouro ocorreu, mas a documentação do GCC diz que sim. Dado que estes dois gostam de ser compatíveis, provavelmente é seguro assumir que é assim que o Clang funciona também.

    Há uma __builtin para cada operação aritmética que pode estourar (adição, subtração, multiplicação), com variantes assinadas e não assinadas, para tamanhos int, tamanhos longos e tamanhos longos longos. A syntax para o nome é __builtin_[us](operation)(l?l?)_overflow :

    • u por unsigned ou s por assinado ;
    • operação é um dos add , sub ou mul ;
    • nenhum sufixo l significa que os operandos são int s; um l significa long ; dois l significam long long .

    Então, para uma adição inteira longa assinada, seria __builtin_saddl_overflow . A lista completa pode ser encontrada na página de documentação do Clang .

    O GCC 5+ e o Clang 3.8+ também oferecem resources genéricos que funcionam sem especificar o tipo dos valores: __builtin_add_overflow , __builtin_sub_overflow e __builtin_mul_overflow . Estes também funcionam em tipos menores que int .

    O builtins menor para o que é melhor para a plataforma. No x86, eles verificam as bandeiras carry, overflow e sign.

    O cl.exe do Visual Studio não tem equivalentes diretos. Para adições e subtrações não assinadas, incluindo , você poderá usar addcarry_uNN e subborrow_uNN (onde NN é o número de bits, como addcarry_u8 ou subborrow_u64 ). Sua assinatura é um pouco obtusa:

     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 é o sinalizador de transporte / empréstimo na input, o valor de retorno é o transporte / empréstimo na saída. Não parece ter equivalentes para operações ou multiplicações assinadas.

    Caso contrário, o Clang for Windows está agora pronto para produção (bom o suficiente para o Chrome), de modo que poderia ser uma opção também.

    Alguns compiladores fornecem access ao sinalizador de estouro de inteiro na CPU, que você pode testar, mas isso não é padrão.

    Você também pode testar a possibilidade de estouro antes de executar a multiplicação:

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

    Aviso: o GCC pode otimizar uma verificação de estouro ao compilar com -O2 . A opção -Wall lhe dará um aviso em alguns casos como

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

    mas não neste exemplo:

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

    A única maneira segura é verificar se há estouro antes que ocorra, conforme descrito no documento CERT , e isso seria extremamente tedioso para usar sistematicamente.

    Compilar com -fwrapv resolve o problema, mas desativa algumas otimizações.

    Precisamos desesperadamente de uma solução melhor. Eu acho que o compilador deve emitir um aviso por padrão ao fazer uma otimização que depende do estouro não ocorrendo. A situação atual permite ao compilador otimizar uma verificação de estouro, o que é inaceitável na minha opinião.

    O clang agora suporta verificações de estouro dynamic para números inteiros assinados e não assinados. Veja -fsanitize = switch inteiro . Por enquanto, é apenas um compilador C ++ com verificação de estouro dynamic totalmente suportada para fins de debugging.

    Aqui está uma solução “não portátil” para a questão. Os processadores Intel x86 e x64 possuem o chamado registro EFLAGS ( http://en.wikipedia.org/wiki/EFLAGS ), que é preenchido pelo processador após cada operação aritmética inteira. Vou pular uma descrição detalhada aqui. Os sinalizadores relevantes são o sinalizador “Estouro” (máscara 0x800) e o sinalizador “Carregar” (máscara 0x1). Para interpretá-los corretamente, deve-se considerar se os operandos são do tipo assinado ou não assinado.

    Aqui está uma maneira prática de verificar os sinalizadores do C / C ++. O código a seguir funcionará no Visual Studio 2005 ou mais recente (ambos de 32 e 64 bits), bem como no GNU C / C ++ de 64 bits.

     #include  #if defined( _MSC_VER ) #include  #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 ); } 

    Se os operandos fossem multiplicados sem estouro, você obteria um valor de retorno de 0 a partir de query_intel_eflags (0x801), ou seja, nem os flags carry nem o estouro estão definidos. No código de exemplo fornecido de main (), ocorre um estouro e os dois sinalizadores são definidos como 1. Essa verificação não implica nenhum outro cálculo, portanto, deve ser bastante rápido.

    Vejo que muitas pessoas responderam à pergunta sobre estouro, mas queria abordar seu problema original. Ele disse que o problema era encontrar um b = c tal que todos os dígitos fossem usados ​​sem repetir. Ok, não é o que ele pediu neste post, mas eu ainda acho que era necessário estudar o limite superior do problema e concluir que ele nunca precisaria calcular ou detectar um estouro (note: eu não sou proficiente em matemática, então eu fiz isso passo a passo, mas o resultado final foi tão simples que isso pode ter uma fórmula simples).

    O ponto principal é que o limite superior que o problema requer para a, b ou c é 98.765.432. De qualquer forma, começando por dividir o problema nas partes triviais e não triviais:

    • x 0 == 1 (todas as permutações de 9, 8, 7, 6, 5, 4, 3, 2 são soluções)
    • x 1 == x (nenhuma solução é possível)
    • 0 b == 0 (nenhuma solução é possível)
    • 1 b == 1 (sem solução possível)
    • a b , a> 1, b> 1 (não trivial)

    Agora só precisamos mostrar que nenhuma outra solução é possível e apenas as permutações são válidas (e então o código para imprimi-las é trivial). Nós voltamos ao limite superior. Na verdade, o limite superior é c ≤ 98.765.432. É o limite superior porque é o maior número com 8 dígitos (10 dígitos no total menos 1 para cada aeb). Este limite superior é somente para c porque os limites para a e b devem ser muito menores devido ao crescimento exponencial, como podemos calcular, variando b de 2 para o limite superior:

      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 

    Observe, por exemplo, a última linha: diz que 1.97 ^ 27 ~ 98M. Então, por exemplo, 1 ^ 27 == 1 e 2 ^ 27 == 134.217.728 e isso não é uma solução porque tem 9 dígitos (2> 1,97 então é realmente maior do que o que deve ser testado). Como pode ser visto, as combinações disponíveis para testar aeb são realmente pequenas. Para b == 14, precisamos tentar 2 e 3. Para b == 3, começamos em 2 e paramos em 462. Todos os resultados são concedidos para serem menores que ~ 98M.

    Agora apenas teste todas as combinações acima e procure aquelas que não repetem nenhum dígito:

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

    Nenhum deles corresponde ao problema (que também pode ser visto pela ausência de ‘0’, ‘1’, …, ‘9’).

    O código de exemplo que resolve segue. Note também que é escrito em python, não porque precisa de inteiros de precisão arbitrária (o código não calcula nada maior que 98 milhões), mas porque descobrimos que a quantidade de testes é tão pequena que devemos usar uma linguagem de alto nível para faça uso de seus containers e bibliotecas embutidos (note também: o código tem 28 linhas).

      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) 

    Se você tiver um tipo de dados que é maior do que o que você deseja testar (digamos que você faça um acréscimo de 32 bits e tenha um tipo de 64 bits). Então, isso detectará se um estouro ocorreu. Meu exemplo é para um suplemento de 8 bits. Mas pode ser ampliado.

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

    É baseado nos conceitos explicados nesta página: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

    Para um exemplo de 32 bits, 0xff torna-se 0xffffffff e 0x80 torna-se 0x80000000 e, finalmente, uint16_t torna-se um uint64_t .

    NOTA : isso captura overtrows de adição / subtração de inteiros, e percebi que sua pergunta envolve multiplicação. Nesse caso, a divisão é provavelmente a melhor abordagem. Isso é comumente uma maneira de as implementações de calloc se certificarem de que os parâmetros não excedem quando são multiplicados para obter o tamanho final.

    A maneira mais simples é converter o seu unsigned long s em unsigned long long s, fazer sua multiplicação e comparar o resultado com 0x100000000LL.

    Você provavelmente descobrirá que isso é mais eficiente do que fazer a divisão como você fez no seu exemplo.

    Ah, e funcionará em C e C ++ (como você marcou a questão com ambos).


    Apenas dei uma olhada no manual da glibc . Há uma menção a uma armadilha de estouro de inteiro ( FPE_INTOVF_TRAP ) como parte do SIGFPE . Isso seria ideal, além dos bits desagradáveis ​​do manual:

    FPE_INTOVF_TRAP Estouro de inteiro (impossível em um programa C, a menos que você ative o trapping de estouro de uma maneira específica do hardware).

    Um pouco de vergonha realmente.

    Para inteiros não assinados, apenas verifique se o resultado é menor que um dos argumentos:

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

    Para inteiros assinados, você pode verificar os sinais dos argumentos e do resultado. inteiros de sinais diferentes não podem estourar, e inteiros de mesmo estouro de sinal só é o resultado é de sinal diferente:

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

    Embora já se passaram dois anos, senti que poderia acrescentar meu penithworth a uma maneira realmente rápida de detectar estouro de pelo menos acréscimos, o que poderia dar uma vantagem para multiplicação, divisão e potência.

    A idéia é que, exatamente porque o processador apenas deixa o valor voltar a zero e que o C / C ++ é abstraído de qualquer processador específico, você pode:

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

    Isso garante que, se um operando for zero e um não, o estouro não será falsamente detectado e será significativamente mais rápido do que muitas operações de teste NOT / XOR / AND /, conforme sugerido anteriormente.

    Edit : Como apontado, esta abordagem, embora melhor do que outras formas mais elaboradas, ainda é otimizável. A seguir, uma revisão do código original que contém a otimização:

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

    Você não pode acessar o sinalizador de estouro de C / C ++.

    Alguns compiladores permitem inserir instruções de trap no código. No GCC, a opção é -ftrapv (mas tenho que admitir que nunca usei. Vou verificar depois de postar).

    A única coisa independente e portátil do compilador que você pode fazer é verificar se há transbordamentos por conta própria. Assim como você fez no seu exemplo.

    Editar:

    Apenas verificado: -ftrapv parece não fazer nada no x86 usando o último GCC. Acho que é uma sobra de uma versão antiga ou específica para alguma outra arquitetura. Eu esperava que o compilador para inserir um código de operação INTO após cada adição. Infelizmente isso não acontece.

    Eu precisava responder essa mesma pergunta para números de ponto flutuante, nos quais o mascaramento de bit e o deslocamento não parecem promissores. A abordagem que estabeleci funciona para números inteiros e de ponto flutuante assinados e não assinados. Ele funciona mesmo se não houver nenhum tipo de dados maior para promover para cálculos intermediários. Não é o mais eficiente para todos esses tipos, mas porque funciona para todos eles, vale a pena usar.

    Teste de estouro assinado, adição e subtração:

    1. Obtenha as constantes que representam os maiores e menores valores possíveis para o tipo, MAXVALUE e MINVALUE.

    2. Calcule e compare os sinais dos operandos.

      uma. Se o valor for zero, nem a adição nem a subtração poderão ser excedidas. Pule os testes restantes.

      b. Se os sinais forem opostos, a adição não pode estourar. Pule os testes restantes.

      c. Se os sinais forem os mesmos, a subtração não pode transbordar. Pule os testes restantes.

    3. Teste para excesso positivo de MAXVALUE.

      uma. Se ambos os sinais forem positivos e MAXVALUE – A

      b. Se o sinal de B for negativo e MAXVALUE – A <-B, a subtração irá transbordar.

    4. Teste para estouro negativo de MINVALUE.

      uma. Se ambos os sinais forem negativos e MINVALUE – A> B, o acréscimo será excedido.

      b. Se o sinal de A for negativo e MINVALUE – A> B, a subtração irá transbordar.

    5. Caso contrário, nenhum estouro.

    Teste de estouro, multiplicação e divisão assinados:

    1. Obtenha as constantes que representam os maiores e menores valores possíveis para o tipo, MAXVALUE e MINVALUE.

    2. Calcule e compare as magnitudes (valores absolutos) dos operandos para um. (Abaixo, assuma que A e B são essas magnitudes, não os originais assinados.)

      uma. Se o valor for zero, a multiplicação não pode estourar e a divisão renderá zero ou um infinito.

      b. Se um dos valores for um, a multiplicação e a divisão não podem estourar.

      c. Se a magnitude de um operando estiver abaixo de um e do outro for maior que um, a multiplicação não pode estourar.

      d. Se as magnitudes forem menores que uma, a divisão não pode transbordar.

    3. Teste para excesso positivo de MAXVALUE.

      uma. Se os dois operandos forem maiores que um e MAXVALUE / A

      b. Se B for menor que um e MAXVALUE * B

    4. Caso contrário, nenhum estouro.

    Nota: O estouro mínimo de MINVALUE é tratado por 3, porque tomamos valores absolutos. No entanto, se ABS (MINVALUE)> MAXVALUE, teremos alguns falsos positivos raros.

    Os testes para underflow são semelhantes, mas envolvem EPSILON (o menor número positivo maior que zero).

    Another interesting tool: http://embed.cs.utah.edu/ioc/

    This is a patched clang compiler, which adds checks to the code at compile time. So you get output looking like this:

     CLANG ARITHMETIC UNDEFINED at  : Op: +, Reason : Signed Addition Overflow, BINARY OPERATION: left (int32): 2147483647 right (int32): 1 

    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.

    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 

    test:

     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

    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.

    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  #include  #include  #include  #if defined( _MSC_VER ) #include  #include  #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++.

    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 .

    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.

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

    mozilla::CheckedInt 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.

    @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 } } 
     #include  #include  #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); } } 

    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”

    Por exemplo:

    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)

    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; }