Meilleur moyen de détecter un dépassement d'entier dans C/C++

Question

J'ai écrit un programme en C++ pour trouver toutes les solutions d' un^b = c, où a, b et c ensemble utiliser tous les chiffres de 0 à 9 exactement une fois. Le programme en boucle sur les valeurs de a et b, et a couru un chiffre de comptage de routine à chaque fois sur a, b et un^b pour vérifier si les chiffres condition était remplie.

Cependant, à de fausses solutions peuvent être générés lorsqu' un^b débordements de l'entier de la limite. J'ai fini par vérifier cela à l'aide d'un code comme:

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

Est-il un meilleur moyen de test pour dépassement de capacité? Je sais que certaines puces ont un indicateur interne qui est défini lors du dépassement de capacité se produit, mais je n'ai jamais vu, il est accessible par le biais de C ou de C++.

Answer 1

Je vois que vous êtes en utilisant des entiers non signés. Par définition, en C (je ne connais pas le C++), non signé de l'arithmétique 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, un Comportement indéterminé a eu lieu et que votre programme peut faire quoi que ce soit (par exemple: rendu des 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 avez besoin de tester pour le débordement avant de générer dit débordement. La méthode peut être utilisée avec des entiers non signés trop

#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 */;
/* ... same thing for subtraction, multiplication, and division */

Answer 2

Départ avec Clang 3.4, il y a maintenant (non portable, mais peut-être gcc va faire la même chose finalement) vérifié l'arithmétique des objets internes. Pour l'exemple de l'OP de la question, il serait comme ça:

unsigned long b, c, c_test;
if (__builtin_umull_overflow(b, c, &c_test))
{
    // there has been an overflow
}
else
{
    // there hasn't been an overflow
}

La documentation ne précise pas si c_test contient la débordé résultat si un dépassement est produite. Je suppose que le résultat n'est pas défini (bien que probablement à la débordé le résultat).

Les objets internes inférieur à ce qui est le mieux pour la plate-forme, de sorte que sur la plupart des plates-formes, ce serait juste vérifier l'indicateur de débordement.

Il y a un __builtin pour chaque opération arithmétique qui peuvent déborder (addition, soustraction, multiplication), avec signés et non signés, les variantes, et de taille normale et longues tailles. La syntaxe pour le nom est __builtin_[us](operation)(ll?)_overflow, donc pour un activée signé long entier long outre, il serait __builtin_saddll_overflow. Ils retourner une valeur non nulle si le résultat a débordé. La liste complète est lié sur la page.

Answer 3

Il est un moyen pour déterminer si une opération est susceptible de déborder, en utilisant les positions de la plus-importante-bits des opérandes et un peu de base binaire-la connaissance des mathématiques.

De plus, toutes les deux opérandes en résultera (au plus) un peu plus que la plus grande opérande le plus élevé un peu. 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, les deux opérandes en résultera (au plus) à la somme des 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 de la suite de l' a de la puissance de l' b comme ceci:

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

(À remplacer par le nombre de bits de votre cible en entier, bien sûr.)

Je ne suis pas sûr de la façon la plus rapide pour déterminer la position de la plus haute d'un bit dans un certain nombre, ici, est une force brute de la méthode:

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

Il n'est pas parfait, mais cela vous donnera une bonne idée si deux nombres peut déborder avant de faire l'opération. Je ne sais pas si il serait plus rapide que de simplement en vérifiant le résultat de la façon dont vous l'avez suggéré, à cause de la boucle dans l' highestOneBitPosition de la fonction, mais il peut (surtout si vous saviez combien de bits étaient les opérandes à l'avance).

Answer 4

Certains compilateurs fournir l'accès à l'entier indicateur de débordement dans la CPU, qui vous pu tester, mais ce n'est pas la norme.

Vous pouvez également tester la possibilité de dépassement de capacité avant d'effectuer la multiplication:

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

Answer 5

Avertissement: GCC peut optimiser un débordement de vérifier 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 */ }

La seule façon est de vérifier pour le débordement avant qu'il se produit, comme décrit dans le CERT papier, 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 doit émettre un avertissement par défaut, lors de la prise d'optimisation qui repose sur le dépassement ne se produisent pas. La situation actuelle permet au compilateur d'optimiser un débordement de vérifier, ce qui est inacceptable à mon avis.