Como detectar estouro de multiplicação de números inteiros não assinados?

Eu estava escrevendo um programa em C ++ para encontrar todas as soluções de um ^b = c , onde a , b e c juntos usar todos os dígitos 0-9 exatamente uma vez. O programa em loop sobre os valores de um e b , e funcionou uma rotina dígitos de contagem de cada vez em um , b e um ^b para verificar se a condição dígitos estava satisfeito.

No entanto, soluções falsas podem ser geradas quando a ^b excede o limite inteiro. Acabei verificando 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 um estouro, mas nunca o vi acessado por C ou C ++.

Cuidado que o estouro assinado int é um comportamento indefinido em C e C ++ e, portanto, você deve detectá-lo sem realmente causar isso. Para estouro int assinado antes da adição, consulte Detectando estouro assinado em C / C ++ .

Vejo que você está usando números inteiros não assinados. Por definição, em C (não sei sobre C ++), a aritmética não assinada não transborda ... então, pelo menos para C, seu argumento é discutível :)

Com números inteiros assinados, após o estouro, ocorre um comportamento indefinido (UB) e seu programa pode fazer qualquer coisa (por exemplo: tornar os testes inconclusivos). 

#include <limits.h>

int a = <something>;
int x = <something>;
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 não assinados:

// 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>;
// There may be a need to check for -1 for two's complement machines.
// If one number is -1 and another is INT_MIN, multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */
// general case
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;

Para a divisão (exceto para o INT_MINe -1caso especial), não há qualquer possibilidade de ir mais INT_MINou INT_MAX.

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

Além disso, quaisquer dois operandos resultarão em (no máximo) um pouco mais que o bit mais alto do maior operando. 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 (no máximo) na soma 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 da apotência da bseguinte forma:

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 número inteiro de destino, é claro.)

Não tenho certeza da maneira mais rápida de determinar a posição do bit mais alto de 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 estourar antes de você fazer a operação. Não sei se seria mais rápido do que simplesmente verificar o resultado da maneira que você sugeriu, por causa do loop na highestOneBitPositionfunção, mas poderia ser (especialmente se você soubesse quantos bits havia nos operandos anteriormente).

O Clang 3.4+ e o GCC 5+ oferecem embutidos aritméticos verificados. Eles oferecem uma solução muito rápida para esse problema, especialmente quando comparados às verificações de segurança de teste de bits.

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_testcontém o resultado do estouro se ocorreu um estouro, mas a documentação do GCC diz que sim. Dado que esses dois gostam de ser __builtincompatíveis, provavelmente é seguro assumir que é assim que Clang também funciona.

Existe um __builtinpara cada operação aritmética que pode exceder (adição, subtração, multiplicação), com variantes assinadas e não assinadas, para tamanhos int, tamanhos longos e tamanhos longos. A sintaxe para o nome é __builtin_[us](operation)(l?l?)_overflow:

• upara sem sinal ou spara assinado ;
• operação é uma das add, subou mul;
• nenhum lsufixo significa que os operandos são ints; um lsignifica long; dois ls significa long long.

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

GCC 5+ e Clang 3.8+ além de oferecer builtins genéricos que funcionam sem especificar o tipo dos valores: __builtin_add_overflow, __builtin_sub_overflowe __builtin_mul_overflow. Eles também funcionam em tipos menores queint .

Os componentes internos são inferiores ao que é melhor para a plataforma. No x86, eles verificam os sinalizadores de transporte, transbordamento e sinalização.

O cl.exe do Visual Studio não possui equivalentes diretos. Para adições e subtrações não assinadas, inclusive <intrin.h>permitirá que você use addcarry_uNNe subborrow_uNN(onde NN é o número de bits, como addcarry_u8ou subborrow_u64). A assinatura deles é 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 carry / emprestado na entrada e o valor de retorno é o carry / emprestado na saída. Não parece ter equivalentes para operações ou multiplicações assinadas.

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

Alguns compiladores fornecem acesso ao sinalizador de estouro de número 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 -Wallemitirá 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 o estouro antes que ocorra, conforme descrito no documento CERT , e isso seria incrivelmente tedioso para ser usado sistematicamente.

Compilar com -fwrapvresolve 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 ocorrer. A situação atual permite que o compilador otimize uma verificação de estouro, o que é inaceitável na minha opinião.

O Clang agora suporta verificações dinâmicas de estouro para números inteiros assinados e não assinados. Veja a opção -fsanitize = integer . Por enquanto, é o único compilador C ++ com verificação de estouro dinâmico totalmente suportada para fins de depuração.

Vejo que muitas pessoas responderam à pergunta sobre estouro, mas eu queria resolver o problema original. Ele disse que o problema era encontrar um ^b = c de modo que todos os dígitos sejam usados ​​sem repetição. Ok, não foi isso que ele pediu neste post, mas ainda acho que era necessário estudar o limite superior do problema e concluir que ele nunca precisaria calcular ou detectar um estouro (nota: não sou proficiente em matemática, 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 exigido pelo problema para a, b ou c é 98.765.432. De qualquer forma, começando dividindo o problema nas partes trivial e não trivial:

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

Agora, apenas precisamos mostrar que nenhuma outra solução é possível e apenas as permutações são válidas (e o código para imprimi-las é trivial). 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 (total de 10 dígitos menos 1 para cada aeb). Esse limite superior é apenas para c porque os limites de aeb devem ser muito mais baixos devido ao crescimento exponencial, como podemos calcular, variando de b de 2 ao 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. Assim, por exemplo, 1 ^ 27 == 1 e 2 ^ 27 == 134.217.728 e essa não é uma solução, pois possui 9 dígitos (2> 1,97; portanto, é realmente maior do que deveria 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 como inferiores a ~ 98M.

Agora basta testar todas as combinações acima e procurar as que não repetem nenhum dígito:

    ['0', '2', '4', '5', '6', '7', '8'] 84^2 = 7056
    ['1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481
    ['0', '1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481 (+leading zero)
    ['1', '2', '3', '5', '8'] 8^3 = 512
    ['0', '1', '2', '3', '5', '8'] 8^3 = 512 (+leading zero)
    ['1', '2', '4', '6'] 4^2 = 16
    ['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
    ['1', '2', '4', '6'] 2^4 = 16
    ['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
    ['1', '2', '8', '9'] 9^2 = 81
    ['0', '1', '2', '8', '9'] 9^2 = 81 (+leading zero)
    ['1', '3', '4', '8'] 3^4 = 81
    ['0', '1', '3', '4', '8'] 3^4 = 81 (+leading zero)
    ['2', '3', '6', '7', '9'] 3^6 = 729
    ['0', '2', '3', '6', '7', '9'] 3^6 = 729 (+leading zero)
    ['2', '3', '8'] 2^3 = 8
    ['0', '2', '3', '8'] 2^3 = 8 (+leading zero)
    ['2', '3', '9'] 3^2 = 9
    ['0', '2', '3', '9'] 3^2 = 9 (+leading zero)
    ['2', '4', '6', '8'] 8^2 = 64
    ['0', '2', '4', '6', '8'] 8^2 = 64 (+leading zero)
    ['2', '4', '7', '9'] 7^2 = 49
    ['0', '2', '4', '7', '9'] 7^2 = 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 ele segue. Observe também que está escrito em Python, não porque ele precisa de números inteiros de precisão arbitrários (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 contêineres e bibliotecas integrados (observe também: o código possui 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)

Aqui está uma solução "não portátil" para a pergunta. As CPUs Intel x86 e x64 possuem o chamado registro 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 "Transporte" (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 (32 e 64 bits), bem como no GNU C / C ++ 64 bits.

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

Se os operandos fossem multiplicados sem transbordamento, você obteria um valor de retorno 0 de query_intel_eflags(0x801), ou seja, nem os sinalizadores de transporte nem de transbordamento sã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 cálculos adicionais; portanto, deve ser bastante rápido.

Se você tiver um tipo de dados maior que o que você deseja testar (digamos que você adicione um de 32 bits e um de 64 bits), isso detectará se ocorreu um estouro. Meu exemplo é para uma adição 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, 0xFFtorna 0xFFFFFFFF- 0x80se 0x80000000e torna - se e, finalmente, uint16_ttorna-se um uint64_t.

NOTA : isso captura estouros de adição / subtração de números inteiros e percebi que sua pergunta envolve multiplicação. Nesse caso, a divisão é provavelmente a melhor abordagem. Geralmente, é uma maneira de as callocimplementações garantirem que os parâmetros não excedam à medida que são multiplicados para obter o tamanho final.

A maneira mais simples é converter seus unsigned longs em unsigned long longs, 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 pergunta com ambos).

Acabei de dar uma olhada no manual da glibc . Há uma menção de uma interceptação de excesso de número inteiro ( FPE_INTOVF_TRAP) como parte de SIGFPE. Isso seria ideal, além dos bits desagradáveis ​​no manual:

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

Um pouco de pena mesmo.

Aqui está uma maneira muito rápida de detectar o estouro de pelo menos adições, o que pode dar uma vantagem para multiplicação, divisão e potência.

A idéia é que, exatamente porque o processador deixará o valor voltar a zero e que o C / C ++ seja 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 é zero e outro 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.

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

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

Uma maneira mais eficiente e barata de detectar o estouro de multiplicação é:

uint32_t x, y;
const bool overflow = (x >> 16U) * (y >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;

Isso resulta em UINT32_MAX no estouro ou no resultado da multiplicação. É um comportamento estritamente indefinido para permitir que a multiplicação prossiga para números inteiros assinados nesse caso.

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

Alguns compiladores permitem inserir instruções de interceptação no código. Em GCC a opção é -ftrapv.

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

No entanto, -ftrapvparece não fazer nada no x86 usando o GCC mais recente. Eu acho que é uma sobra de uma versão antiga ou específica para alguma outra arquitetura. Eu esperava que o compilador inserisse um código de operação INTO após cada adição. Infelizmente não faz isso.

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

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

Para números inteiros assinados, você pode verificar os sinais dos argumentos e do resultado.

Os números inteiros de sinais diferentes não podem transbordar e os números inteiros do mesmo sinal transbordam apenas se o resultado for de um sinal diferente:

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

Eu precisava responder a mesma pergunta para números de ponto flutuante, onde mascaramento e mudança de bits não parecem promissores. A abordagem que decidi trabalhar para números assinados e não assinados, números inteiros e de ponto flutuante. Funciona mesmo se não houver um tipo de dados maior a ser promovido para cálculos intermediários. Não é o mais eficiente para todos esses tipos, mas como funciona para todos eles, vale a pena usá-lo.

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

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 qualquer valor for zero, nem a adição nem a subtração podem exceder. Pule os testes restantes.

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

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

3. Teste para estouro positivo de MAXVALUE.

   uma. Se ambos os sinais forem positivos e MAXVALUE - A <B, a adição transbordará.

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

4. Teste para estouro negativo de MINVALUE.

   uma. Se ambos os sinais são negativos e MINVALUE - A> B, a adição transbordará.

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

5. Caso contrário, não haverá transbordamento.

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

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 com um. (Abaixo, suponha que A e B sejam essas magnitudes, não os originais assinados.)

   uma. Se qualquer valor for zero, a multiplicação não poderá exceder e a divisão produzirá zero ou um infinito.

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

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

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

3. Teste para estouro positivo de MAXVALUE.

   uma. Se os dois operandos forem maiores que um e MAXVALUE / A <B, a multiplicação será excedida.

   b. Se B for menor que um e MAXVALUE * B <A, a divisão transbordará.

4. Caso contrário, não haverá transbordamento.

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

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

A CERT desenvolveu uma nova abordagem para detectar e relatar estouro de número inteiro assinado, agrupamento de número inteiro não assinado e truncamento de número inteiro usando o modelo de número inteiro "como se" infinitamente variado (AIR). O CERT publicou um relatório técnico descrevendo o modelo e produziu um protótipo funcional com base no GCC 4.4.0 e GCC 4.5.0.

O modelo inteiro do AIR produz um valor equivalente a um que seria obtido usando números inteiros infinitamente variados ou resulta em uma violação de restrição de tempo de execução. Diferentemente dos modelos inteiros anteriores, os inteiros do AIR não exigem traps precisos e, consequentemente, não interrompem ou inibem a maioria das otimizações existentes.

Outra ferramenta interessante é o IOC: um verificador de estouro inteiro para C / C ++ .

Este é um Clang remendado compilador , que adiciona verificações ao código no momento da compilação.

Você obtém saída assim:

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

Outra variante de uma solução, usando linguagem assembly, é um procedimento externo. Este exemplo para multiplicação de números inteiros não assinados usando g ++ e fasm no Linux x64.

Este procedimento multiplica dois argumentos inteiros não assinados (32 bits) (de acordo com a especificação para amd64 (seção 3.2.3 Passagem de parâmetro ).

Se a classe for INTEGER, o próximo registro disponível da sequência% rdi,% rsi,% rdx,% rcx,% r8 e% r9 será usado

(edi e esi registra no meu código)) e retorna o resultado ou 0 se um estouro ocorreu.

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

Teste:

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

Vincule o programa ao arquivo de objeto asm. No meu caso, no Qt Creator , adicione-o LIBSem um arquivo .pro.

Calcule os resultados com dobras. Eles têm 15 dígitos significativos. Sua exigência tem um limite superior rígido em c de 10 ⁸  - ele pode ter no máximo 8 dígitos. Portanto, o resultado será preciso se estiver dentro do alcance e, caso contrário, não excederá o limite.

Experimente esta macro para testar o bit de estouro de máquinas de 32 bits (adaptou a solução de Angel Sinigersky)

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

Eu o defini como uma macro porque, caso contrário, o bit de estouro seria substituído.

A seguir é uma pequena aplicação com o segmento de código acima:

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

A captura de estouro de número inteiro em C indica uma solução mais geral do que a discutida pelo CERT (é mais geral em termos de tipos manipulados), mesmo que exija algumas extensões do GCC (não sei o quão amplamente elas são suportadas).

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

Eu não concordo com isso. Você pode escrever alguma linguagem assembly embutida e usar umjo instrução (jump overflow) assumindo que você esteja no x86 para interceptar o estouro. Obviamente, seu código não seria mais portátil para outras arquiteturas.

Olhe para info ase info gcc.

Para expandir a resposta do Head Geek, existe uma maneira mais rápida de fazer o 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 );
}

Isso usa arquitetura segura da máquina, pois números inteiros não assinados de 64 e 32 bits ainda funcionarão bem. Basicamente, eu crio uma máscara que mascarará tudo, exceto o bit mais significativo. Então, mascarei os dois números inteiros e, se um deles não tiver esse bit definido, a adição será segura.

Isso seria ainda mais rápido se você pré-inicializar a máscara em algum construtor, pois ela nunca muda.

mozilla::CheckedInt<T>fornece matemática de número inteiro verificado pelo estouro para o tipo inteiro T(usando intrínsecas do compilador no clang e no gcc, conforme disponível). O código está no MPL 2.0 e depende de três ( IntegerTypeTraits.h, Attributes.he Compiler.h) outros cabeçalhos de biblioteca não padrão apenas de cabeçalho, além de mecanismos de asserção específicos para Mozilla . Você provavelmente deseja substituir o mecanismo de asserção se importar o código.

A resposta do MSalter é uma boa ideia.

Se o cálculo inteiro for necessário (para precisão), mas o ponto flutuante estiver disponível, você poderá fazer algo como:

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

O conjunto de instruções x86 inclui uma instrução de multiplicação não assinada que armazena o resultado em dois registros. Para usar essa instrução de C, pode-se escrever o seguinte código em um programa de 64 bits (GCC):

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

Para um programa de 32 bits, é necessário tornar o resultado em 64 bits e os parâmetros em 32 bits.

Uma alternativa é usar o intrínseco dependente do compilador para verificar o registro do sinalizador. A documentação do GCC para transbordamento intrínseco pode ser encontrada em 6.56 Funções internas para executar aritmética com verificação de estouro .

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

    }
}

Uma maneira limpa de fazer isso seria substituir todos os operadores (+ e * em particular) e verificar se há um estouro antes de executar as operações.

Depende do que você usa. Realizando adição ou multiplicação longa não assinada (DWORD), a melhor solução é usar ULARGE_INTEGER.

ULARGE_INTEGER é uma estrutura de dois DWORDs. O valor total pode ser acessado como "QuadPart", enquanto o DWORD alto é acessado como "HighPart" e o DWORD baixo é acessado como "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)

Para executar uma multiplicação sem sinal sem transbordar de maneira portátil, o seguinte pode ser usado:

... /* 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;
}

A maneira simples de testar o estouro é fazer a validação, verificando se o valor atual é menor que o valor anterior. Por exemplo, suponha que você tenha um loop para imprimir os poderes de 2:

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

A adição de verificação de estouro da maneira que descrevi resulta em:

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

Ele funciona para valores não assinados, bem como valores assinados positivos e negativos.

Obviamente, se você quisesse fazer algo semelhante para diminuir valores em vez de aumentar valores, você iria virar o <=sinal para fazê-lo >=, assumindo que o comportamento do underflow é o mesmo que o comportamento do overflow. Com toda a honestidade, isso é tão portátil quanto você obtém sem acesso ao sinalizador de estouro de uma CPU (e isso exigiria código de montagem em linha, tornando seu código não portátil em implementações de qualquer maneira).