Comment détecter un débordement d'entier?

je vois que vous utilisez des entiers non signés. Par définition, en C (ne sait pas C++), l'arithmétique non signée ne déborde pas ... donc, au moins pour C, votre point est discutable :)

avec des entiers signés, une fois qu'il y a eu débordement, comportement non défini s'est produit et votre programme peut faire n'importe quoi (par exemple: rendre les tests non concluants). 

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

pour créer un programme conforme vous devez tester le débordement avant générant ledit débordement. La méthode peut aussi être utilisée avec des entiers non signés

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

pour la division (à l'exception du INT_MIN et du -1 cas spécial) il n'y a pas de possibilité de dépasser INT_MIN ou INT_MAX .

il est une façon de déterminer si une opération est susceptible de déborder, en utilisant les positions des bits les plus significatifs dans les opérandes et un peu de binaire-mathématiques de base connaissances.

pour addition, deux opérandes quelconques donneront (au plus) un peu plus que le plus grand un-bit de l'opérande. Par exemple:

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

pour la multiplication, deux opérandes quelconques donneront (au plus) la somme de la les bits de l'opérande. Par exemple:

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

de même, vous pouvez estimer la taille maximale du résultat de a à la puissance de b comme ceci:

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

(bien sûr, substituez le nombre de bits à votre entier cible.)

Je ne suis pas sûr du moyen le plus rapide pour déterminer la position du plus haut un-bit dans un nombre, voici une méthode de la force brute:

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

ce n'est pas parfait, mais ça vous donnera une bonne idée si deux nombres peuvent déborder avant de faire l'opération. Je ne sais pas si ce serait plus rapide que de simplement vérifier le résultat comme vous l'avez suggéré, à cause de la boucle dans la fonction highestOneBitPosition , mais cela pourrait (surtout si vous saviez combien de bits il y avait dans les opérandes avant).

Clang 3.4+ et GCC 5+ offre vérifié l'arithmétique des objets internes. Ils offrent une solution très rapide à ce problème, surtout par rapport aux contrôles de sécurité bit-testing.

pour l'exemple de la question de L'OP, ça marcherait comme ça:

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
}

la documentation de Clang ne spécifie pas si c_test contient le résultat de débordement en cas de débordement, mais le GCC la documentation dit que oui. Étant donné que ces deux-là aiment être __builtin - compatible, il est probablement sûr de supposer que C'est comment Clang fonctionne aussi.

il y a un __builtin pour chaque opération arithmétique qui peut déborder (addition, soustraction, multiplication), avec des variantes signées et non signées, pour des tailles int, des tailles longues, et de longues tailles. La syntaxe du nom est __builtin_[us](operation)(l?l?)_overflow :

• u pour non signée ou s pour signée ;
• est l'une des opérations add , sub ou mul ;
• non l suffixe signifie que les opérandes sont des int s; un l signifie long ; deux l s long long .

donc pour un ajout signé long entier vérifié, ce serait __builtin_saddl_overflow . La liste complète peut être trouvé sur la page Clang documentation .

GCC 5+ et Clang 3.8+ offrent en outre des constructions génériques qui fonctionnent sans spécifier le type des valeurs: __builtin_add_overflow , __builtin_sub_overflow et __builtin_mul_overflow . Ceux-ci travaillent également sur les types plus petits que int .

les bâtiments sont plus bas à ce qui est le mieux pour la plate-forme. Sur x86, ils vérifient les drapeaux carry, overflow et sign.

de Visual Studio cl.l'exe n'a pas d'équivalents directs. Pour les additions et soustractions non signées, y compris <intrin.h> vous permettra d'utiliser addcarry_uNN et subborrow_uNN (où NN est le nombre de bits, comme addcarry_u8 ou subborrow_u64 ). Leur signature est un peu obtus:

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 est le drapeau carry/borrow à l'entrée, la valeur de retour est le carry / borrow à la sortie. Il ne semble pas avoir d'équivalents pour les opérations signées ou multiplication.

sinon, Clang for Windows est maintenant prêt pour la production (assez bon pour le Chrome), ce qui pourrait être une option, aussi.

certains compilateurs fournissent l'accès à l'indicateur de débordement entier dans le CPU que vous pourriez alors tester, mais ce n'est pas standard.

vous pouvez également tester la possibilité de débordement avant d'effectuer la multiplication:

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

avertissement: GCC peut optimiser un contrôle de débordement lors de la compilation avec -O2 . L'option -Wall vous donnera un avertissement dans certains cas, comme

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

, mais pas dans cet exemple:

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

le seul moyen sûr est de vérifier le débordement avant qu'il ne se produise, comme décrit dans le papier CERT , et ce serait incroyablement fastidieux à utiliser systématiquement.

compilation avec -fwrapv résout le problème, mais désactive certaines optimisations.

Nous avons désespérément besoin d'une meilleure solution. Je pense que le compilateur devrait émettre un avertissement par défaut lors de la réalisation d'une optimisation qui repose sur le débordement ne se produit pas. La situation actuelle permet au compilateur d'optimiser un débordement de vérifier, ce qui est inacceptable à mon avis.

clang supporte maintenant les contrôles de débordement dynamique pour les entiers signés et non signés. Voir - fsanitize=entier switch. Pour l'instant, il ne s'agit que d'un seul compilateur C++ avec une vérification dynamique de débordement entièrement supportée à des fins de débogage.

Voici une solution" non portable " à la question. Les processeurs Intel x86 et x64 ont le soi-disant EFLAGS-register ( http://en.wikipedia.org/wiki/EFLAGS ), qui est remplie par le processeur après chaque opération arithmétique entière. Je vais sauter une description détaillée ici. Les drapeaux pertinents sont le drapeau " Overflow "(masque 0x800) et le drapeau" Carry " (masque 0x1). Pour les interpréter correctement, il faut considérer si les opérandes sont de type signé ou non signé.

voici un moyen pratique de vérifier les options de C/C++. Le code suivant fonctionnera sur Visual Studio 2005 ou une version plus récente (32 et 64 bits), ainsi que sur 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 );
}

si les opérandes étaient multipliées sans débordement, vous obtiendriez une valeur de retour de 0 de query_intel_eflags( 0x801 ), c'est-à-dire que ni les drapeaux carry ni overflow ne sont activés. Dans l'exemple de code de main () fourni, un débordement se produit et les deux options sont définies 1. Ce contrôle n'implique pas d'autres calculs, il devrait donc être assez rapide.

je vois que beaucoup de gens ont répondu à la question sur le débordement, mais je voulais aborder son problème original. Il a dit que le problème était de trouver un ^b =c tel que tous les chiffres sont utilisés sans répétition. Ok, ce n'est pas ce qu'il a demandé dans ce post, mais je pense toujours qu'il était nécessaire d'étudier la limite supérieure du problème et de conclure qu'il n'aurait jamais besoin de calculer ou de détecter un débordement (note: Je ne suis pas compétent en mathématiques donc j'ai fait cette étape par étape, mais le résultat final était si simple que cela peut avoir une formule simple).

le point principal est que la limite supérieure que le problème exige pour a, b ou c est 98.765.432. Quoi qu'il en soit, en commençant par séparer le problème dans les parties triviales et non triviales:

• x ⁰ == 1 (toutes les permutations de 9, 8, 7, 6, 5, 4, 3, 2 are solutions)
• x ¹ = = x (Pas de solution possible)
• 0 ^b = = 0 (pas de solution possible)
• 1 ^b == 1 (Pas de solution possible)
• a ^b , a > 1, b > 1 (non trivial)

maintenant nous avons juste besoin de montrer qu'aucune autre solution n'est possible et que seules les permutations sont valides (et alors le code pour les imprimer est trivial). Nous revenons à la limite supérieure. En fait la partie supérieure la limite est c ≤ 98.765.432. C'est la limite supérieure parce que c'est le plus grand nombre avec 8 chiffres (10 chiffres au total moins 1 pour chaque a et b). Cette limite supérieure n'est que pour c parce que les limites pour a et b doivent être beaucoup plus basses à cause de la croissance exponentielle, comme nous pouvons le calculer, variant b de 2 à la limite supérieure:

    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

avis, par exemple la dernière ligne: il dit que 1.97^27 ~98M. Donc, par exemple, 1^27 == 1 et 2^27 = = 134.217.728 et ce n'est pas une solution parce que il a 9 chiffres (2 > 1,97 donc il est en fait plus grand que ce qui devrait être testé). Comme on peut le voir, les combinaisons disponibles pour tester a et b sont vraiment petites. Pour b == 14, nous devons essayer 2 et 3. Pour b = = 3, on commence à 2 et on s'arrête à 462. Tous les résultats sont accordés pour être inférieur à ~98M.

maintenant, testez toutes les combinaisons ci-dessus et cherchez celles qui ne répètent aucun chiffre:

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

aucun d'entre eux ne correspond au problème (qui peut également être vu par l'absence de '0', '1', ..., "9").

l'exemple de code qui le résout suit. Notez aussi que c'est écrit en python, non pas parce qu'il nécessite des entiers de précision arbitraires (le code ne calcule rien de plus grand que 98 millions), mais parce que nous avons découvert que le nombre de tests est si petit que nous devrions utiliser un langage de haut niveau pour faire usage de ses conteneurs et bibliothèques intégrés (note également: le code a 28 lignes).

    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)

si vous avez un type de données qui est plus grand que celui que vous voulez tester (disons que vous faites un add 32 bits et que vous avez un type 64 bits). Ensuite, cela détectera si un débordement s'est produit. Mon exemple est un add 8-bit. Mais peut être mis à l'échelle.

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

il est basé sur les concepts expliqués sur cette page: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

pour un exemple de 32 bits, 0xff devient 0xffffffff et 0x80 devient 0x80000000 et finalement uint16_t devient un uint64_t .

NOTE : cela capte des dépassements d'additions/soustractions entières, et j'ai réalisé que votre question implique une multiplication. Dans ce cas, la division est probablement la meilleure approche. C'est généralement une façon que les implémentations calloc s'assurent que les params ne débordent pas car ils sont multipliés pour obtenir la taille finale.

la manière la plus simple est de convertir votre unsigned long s en unsigned long long s, faire votre multiplication, et comparer le résultat à 0x1000000ll.

vous trouverez probablement que c'est plus efficace que de faire la division comme vous l'avez fait dans votre exemple.

Oh, et il va travailler à la fois le C et le C++ (comme vous l'avez marqué la question avec les deux).

je viens de jeter un oeil au glibc manuel . Il y a une mention d'un piège de débordement entier ( FPE_INTOVF_TRAP ) dans le cadre de SIGFPE . Ce serait l'idéal, à part les mauvais passages du manuel:

FPE_INTOVF_TRAP Débordement d'entier (impossible dans un programme C sauf si vous activez le piégeage de débordement d'une manière spécifique au matériel).

Un peu de honte vraiment.

bien qu'il ait été deux ans, j'ai senti que je pourrais aussi bien ajouter mon penithworth pour un moyen vraiment rapide de détecter le débordement pour au moins additions, ce qui pourrait donner une avance pour la multiplication, la division et la puissance-de

l'idée est que exactement parce que le processeur va juste laisser la valeur de retour à zéro et que C / C++ est de faire abstraction de n'importe quel processeur spécifique, vous pouvez:

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

cela garantit à la fois que si un opérande est zéro et on ne l'est pas, alors le débordement ne sera pas faussement détecté, et est significativement plus rapide que beaucoup d'opérations non/XOR/et/test comme précédemment suggéré.

Modifier : Comme l'a souligné, cette approche, bien mieux que d'autres plus élaborées façons est encore optimisable. Voici une révision du code original contenant l'optimisation:

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

pour les entiers non signés, vérifiez que le résultat est plus petit qu'un des arguments:

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

Pour les entiers signés, vous pouvez vérifier les signes des arguments et du résultat. des entiers de différents signes ne peuvent pas déborder, et les entiers de même débordement de signe seulement est le résultat est de signe différent:

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

vous ne pouvez pas accéder au drapeau overflow depuis C/C++.

certains compilateurs vous permettent d'insérer des instructions trap dans le code. Sur GCC L'option est-ftrapv (mais je dois admettre que je ne l'ai jamais utilisé. Vérifier après la publication).

la seule chose portable et compilateur indépendant que vous pouvez faire est de vérifier les débordements sur votre propre. Comme vous l'avez fait dans votre exemple.

Edit:

vient de vérifier: - ftrapv semble ne rien faire sur x86 en utilisant le dernier GCC. Suppose que c'est un reliquat d'une ancienne version ou spécifiques à certains autres de l'architecture. Je m'attendais à ce que le compilateur insère un dans opcode après chaque ajout. Malheureusement, il ne le fait pas.

j'avais besoin de répondre à cette même question pour les nombres à virgule flottante, où le masquage de bits et le déplacement ne semblent pas prometteurs. L'approche sur laquelle j'ai opté fonctionne pour les nombres signés et non signés, les nombres entiers et les nombres à virgule flottante. Il fonctionne même s'il n'y a pas de plus grand type de données à promouvoir pour les calculs intermédiaires. Il n'est pas le plus efficace pour tous ces types, mais parce qu'il n'travail pour tous, il vaut la peine de l'utiliser.

Signé Dépassement de test, l'Addition et la Soustraction:

1. obtenir les constantes qui représentent les valeurs les plus grandes et les plus petites possibles pour le type, MAXVALUE et MINVALUE.

2. calculer et comparer les signes des opérandes.

   A. Si l'une ou l'autre valeur est zéro, alors ni l'addition ni la soustraction ne peuvent déborder. Sautez les tests restants.

   B. Si les signes sont opposés, l'ajout ne peut pas déborder. Sautez les tests restants.

   C. Si les signes sont les mêmes, alors la soustraction ne peut pas déborder. Sautez les tests restants.

3. Test de débordement positif de MAXVALUE.

   A. Si les deux signes sont positifs et MAXVALUE-A < B, alors l'ajout débordera.

   B. Si le signe de B est négatif et MAXVALUE - A < -B, alors la soustraction débordera.

4. Test de débordement négatif de MINVALUE.

   A. Si les deux signes sont négatifs et de MINVALUE-A > B, alors l'ajout débordera.

   B. Si le signe de A est négatif et MINVALUE-A > B, alors la soustraction débordera.

5. sinon, pas de débordement.

Signé Dépassement de test, de Multiplication et de Division:

1. obtenir les constantes qui représentent les valeurs les plus grandes et les plus petites possibles pour le type, MAXVALUE et MINVALUE.

2. calculer et comparer les grandeurs (valeurs absolues) des opérandes à un. (Ci-dessous, supposons que A et b sont ces valeurs, et non les originaux signés.)

   A. Si l'une ou l'autre valeur est zéro, la multiplication ne peut pas déborder, et la division donnera zéro ou un infini.

   B. Si, selon le cas: la valeur est un, la multiplication et la division ne peuvent pas déborder.

   C. Si la grandeur d'un opérande est inférieure à l'un et de l'autre est supérieure à un, la multiplication ne peut pas déborder.

   D. Si les deux grandeurs sont inférieures à un, la division ne peut pas déborder.

3. Test de débordement positif de MAXVALUE.

   A. Si les deux opérandes sont supérieures à un et MAXVALUE / A < B, alors la multiplication va déborder.

   B. Si B est inférieur à un et MAXVALUE * B < a, alors la division débordera.

4. sinon, pas de débordement.

Note: le débordement Minimum de MINVALUE est traité par 3, parce que nous avons pris des valeurs absolues. Toutefois, si ABS ( MINVALUE) > MAXVALUE, puis nous aurons quelques rares faux positifs.

les essais pour le débit inférieur sont similaires, mais impliquez EPSILON (le plus petit nombre positif supérieur à zéro).

un autre outil intéressant: http://embed.cs.utah.edu/ioc /

il s'agit d'un compilateur clang patché, qui ajoute des vérifications au code au moment de la compilation. Donc vous obtenez une sortie ressemblant à ceci:

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

CERT a développé une nouvelle approche pour détecter et rapporter le débordement d'entier signé, l'enrubannage d'entier non signé et la troncation d'entier en utilisant le modèle "as-if" infinitely ranged (AIR) entier. CERT a publié un rapport technique décrivant le modèle et a produit un prototype de travail basé sur GCC 4.4.0 et GCC 4.5.0.

le modèle AIR entier produit soit une valeur équivalente à celle qui aurait été obtenue en utilisant des entiers à portée infinie ou entraîne une violation de la contrainte d'exécution. Contrairement aux modèles précédents d'entiers, les entiers D'AIR ne nécessitent pas de pièges précis, et par conséquent ne cassent pas ou n'inhibent pas la plupart des optimisations existantes.

une autre variante de la solution en utilisant assembleur est un procédé externe. Cet exemple pour la multiplication entière non signée en utilisant g++ et fasm sous linux x64.

cette procédure multiplie deux arguments entiers non signés (32 bits) (selon spécification pour amd64 (section 3.2.3 passage du paramètre)

si la classe est entière, le prochain registre disponible de la séquence %rdi,%rsi,%rdx,%rcx,%r8 et le %r9 est utilisé

(EDI et esi enregistre dans mon code)) et renvoie le résultat ou 0 si un débordement a eu lieu.

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

essai:

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

programme de lien avec le fichier d'objet asm. Dans mon cas, dans Qt Creator, ajoutez-le à LIBS dans A. pro file

calculer les résultats avec doubles. Ils ont 15 chiffres significatifs. Votre exigence a une limite supérieure dure sur c de 10 ⁸ - il peut avoir au plus 8 chiffres. Donc, le résultat sera précis s'il est à portée, et il ne débordera pas autrement.

essayez cette macro pour tester le bit de débordement des machines 32 bits (adapté de la solution D'Angel Sinigersky)

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

Je l'ai défini comme une macro parce que sinon le bit de débordement aurait été écrasé.

est une petite application avec le code segment ci-dessus:

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

vous ne pouvez pas accéder au drapeau overflow depuis C/C++.

Je ne suis pas d'accord. Vous pouvez écrire un certain ASM en ligne et utiliser une instruction jo (saut de débordement) en supposant que vous êtes sur x86 pour piéger le débordement. Bien sûr, vous code plus portable vers d'autres architectures.

regardez info as et info gcc .

attraper les dépassements D'entiers dans C indique une solution plus générale que celle discutée par le CERT (elle est plus générale en termes de types manipulés), même si elle nécessite certaines extensions GCC (Je ne sais pas combien ils sont largement supportés).

une façon propre de le faire serait d'outrepasser tous les opérateurs (+ et * en particulier) et de vérifier s'il y a un débordement avant de perormer les opérations.

pour développer la réponse du Geek, il y a un moyen plus rapide de faire le 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 );
}

cela utilise la machine-architecture sûre, dans ce 64-bit et 32-bit entiers non signés fonctionneront encore très bien. En gros, je crée un masque qui masquera tout sauf le plus significatif. Ensuite, je masque deux entiers, et si l'une d'entre elles n'ont que peu le jeu, puis plus sécuritaire.

ce serait encore plus rapide si vous pré-initialisez le masque dans certains constructeur, car il ne change jamais.

jeu d'instructions x86 comprend non signé multiplier instruction qui stocke le résultat de deux registres. Pour utiliser cette instruction de C on peut écrire le code suivant dans le programme 64bit (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;
}

pour le programme 32bit on doit faire le résultat 64 bits et les paramètres 32bit.

Alternative est d'utiliser des instincts de dépendance de compilateur pour vérifier le registre de drapeau. La documentation de GCC pour les instincts de débordement peut être trouvée à partir de https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

mozilla::CheckedInt<T> fournit des mathématiques entières vérifiées par débordement pour le type entier T (en utilisant le compilateur intrinsics sur clang et gcc comme disponibles). Le code est sous MPL 2.0 et dépend de trois ( IntegerTypeTraits.h , Attributes.h et Compiler.h ) autres en-têtes de bibliothèque non standard uniquement, plus Mozilla-specific assertion machinery . Vous voulez sans doute remplacez la machine d'assertion si vous importez le code.

@MSalters: bonne idée.

si le calcul de l'entier est requis (pour la précision), mais que la virgule flottante est disponible, vous pouvez faire quelque chose comme:

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

l'assemblage en ligne vous permet de vérifier le bit de débordement directement. Si vous allez utiliser C++, vous devriez vraiment apprendre à assembler.

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

    }
}

cela dépend pour quoi vous l'utilisez. Effectuer une addition ou une Multiplication longue(DWORD) non signée la meilleure solution est D'utiliser ULARGE_INTEGER.

ULARGE_INTEGER est une structure de deux DWORDs. La totalité de la valeur peut être consulté en tant que "QuadPart" pendant que le haut DWORD est accédé comme "HighPart" et le DWORD bas est accédé comme "LowPart "

par exemple:

DWORD Mon 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)

/ / tout débordement est stocké dans A. HighPart (up to 32 bits)

pour effectuer une multiplication non signée sans débordement d'une manière portable, on peut utiliser ce qui suit:

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