Comment Java gère-t-il les débordements et débordements d'entiers et comment le vérifieriez-vous?

Comment Java gère-t-il les débordements et débordements d'entiers?

À partir de là, comment vérifieriez-vous / testeriez-vous que cela se produit?

S'il déborde, il revient à la valeur minimale et continue à partir de là. S'il déborde, il revient à la valeur maximale et continue à partir de là.

Vous pouvez vérifier cela au préalable comme suit:

public static boolean willAdditionOverflow(int left, int right) {
    if (right < 0 && right != Integer.MIN_VALUE) {
        return willSubtractionOverflow(left, -right);
    } else {
        return (~(left ^ right) & (left ^ (left + right))) < 0;
    }
}

public static boolean willSubtractionOverflow(int left, int right) {
    if (right < 0) {
        return willAdditionOverflow(left, -right);
    } else {
        return ((left ^ right) & (left ^ (left - right))) < 0;
    }
}

(vous pouvez remplacer intpar longpour effectuer les mêmes vérifications long)

Si vous pensez que cela peut se produire plus que souvent, envisagez d'utiliser un type de données ou un objet qui peut stocker des valeurs plus importantes, par exemple longou peut-être java.math.BigInteger. Le dernier ne déborde pas, pratiquement, la mémoire JVM disponible est la limite.

Si vous êtes déjà sur Java8, vous pouvez utiliser les nouvelles méthodes Math#addExact()et Math#subtractExact()qui déclencheront un ArithmeticExceptiondébordement.

public static boolean willAdditionOverflow(int left, int right) {
    try {
        Math.addExact(left, right);
        return false;
    } catch (ArithmeticException e) {
        return true;
    }
}

public static boolean willSubtractionOverflow(int left, int right) {
    try {
        Math.subtractExact(left, right);
        return false;
    } catch (ArithmeticException e) {
        return true;
    }
}

Le code source peut être trouvé ici et ici respectivement.

Bien sûr, vous pouvez également les utiliser immédiatement au lieu de les masquer dans une booleanméthode utilitaire.

Eh bien, en ce qui concerne les types entiers primitifs, Java ne gère pas du tout les débordements / débordements (pour flottant et double, le comportement est différent, il s'écoulera à +/- infini tout comme les mandats IEEE-754).

Lorsque vous ajoutez deux int, vous n'obtiendrez aucune indication lorsqu'un débordement se produit. Une méthode simple pour vérifier le débordement consiste à utiliser le type plus grand suivant pour réellement effectuer l'opération et vérifier si le résultat est toujours dans la plage du type source:

public int addWithOverflowCheck(int a, int b) {
    // the cast of a is required, to make the + work with long precision,
    // if we just added (a + b) the addition would use int precision and
    // the result would be cast to long afterwards!
    long result = ((long) a) + b;
    if (result > Integer.MAX_VALUE) {
         throw new RuntimeException("Overflow occured");
    } else if (result < Integer.MIN_VALUE) {
         throw new RuntimeException("Underflow occured");
    }
    // at this point we can safely cast back to int, we checked before
    // that the value will be withing int's limits
    return (int) result;
}

Ce que vous feriez à la place des clauses throw dépend des exigences de vos applications (throw, flush to min / max ou tout simplement enregistrer quoi que ce soit). Si vous voulez détecter un débordement sur de longues opérations, vous n'avez pas de chance avec les primitives, utilisez plutôt BigInteger.

Edit (2014-05-21): Étant donné que cette question semble être évoquée assez fréquemment et que j'ai dû résoudre le même problème moi-même, il est assez facile d'évaluer la condition de débordement par la même méthode qu'un processeur calculerait son indicateur V.

C'est fondamentalement une expression booléenne qui implique le signe des deux opérandes ainsi que le résultat:

/**
 * Add two int's with overflow detection (r = s + d)
 */
public static int add(final int s, final int d) throws ArithmeticException {
    int r = s + d;
    if (((s & d & ~r) | (~s & ~d & r)) < 0)
        throw new ArithmeticException("int overflow add(" + s + ", " + d + ")");    
    return r;
}

En java, il est plus simple d'appliquer l'expression (dans le if) aux 32 bits entiers et de vérifier le résultat en utilisant <0 (cela testera efficacement le bit de signe). Le principe fonctionne exactement de la même manière pour tous les types primitifs entiers , en changeant toutes les déclarations de la méthode ci-dessus en long, cela fonctionne longtemps.

Pour les types plus petits, en raison de la conversion implicite en int (voir le JLS pour les opérations au niveau du bit pour plus de détails), au lieu de vérifier <0, la vérification doit masquer explicitement le bit de signe (0x8000 pour les opérandes courts, 0x80 pour les opérandes d'octets, ajuster les conversions et déclaration des paramètres):

/**
 * Subtract two short's with overflow detection (r = d - s)
 */
public static short sub(final short d, final short s) throws ArithmeticException {
    int r = d - s;
    if ((((~s & d & ~r) | (s & ~d & r)) & 0x8000) != 0)
        throw new ArithmeticException("short overflow sub(" + s + ", " + d + ")");
    return (short) r;
}

(Notez que l'exemple ci-dessus utilise l'expression besoin de soustraire la détection de débordement)

Alors, comment / pourquoi ces expressions booléennes fonctionnent-elles? Tout d'abord, une réflexion logique révèle qu'un débordement ne peut se produire que si les signes des deux arguments sont les mêmes. Parce que, si un argument est négatif et un positif, le résultat (de l'addition) doit être plus proche de zéro, ou dans le cas extrême un argument est nul, le même que l'autre argument. Comme les arguments ne peuvent pas créer par eux-mêmes une condition de débordement, leur somme ne peut pas non plus créer de débordement.

Que se passe-t-il donc si les deux arguments ont le même signe? Jetons un coup d'œil au cas où les deux sont positifs: l'ajout de deux arguments qui créent une somme supérieure aux types MAX_VALUE, produira toujours une valeur négative, donc un débordement se produit si arg1 + arg2> MAX_VALUE. Maintenant, la valeur maximale qui pourrait en résulter serait MAX_VALUE + MAX_VALUE (le cas extrême, les deux arguments sont MAX_VALUE). Pour un octet (exemple) qui signifierait 127 + 127 = 254. En regardant les représentations binaires de toutes les valeurs qui peuvent résulter de l'ajout de deux valeurs positives, on constate que celles qui débordent (128 à 254) ont toutes le bit 7 défini, tandis que tout ce qui ne déborde pas (0 à 127) a le bit 7 (le plus haut, signe) effacé. C'est exactement ce que la première partie (à droite) de l'expression vérifie:

if (((s & d & ~r) | (~s & ~d & r)) < 0)

(~ s & ~ d & r) devient vrai, seulement si deux opérandes (s, d) sont positifs et que le résultat (r) est négatif (l'expression fonctionne sur les 32 bits, mais le seul bit qui nous intéresse est le bit (signe) le plus haut, qui est vérifié par le <0).

Maintenant, si les deux arguments sont négatifs, leur somme ne peut jamais être plus proche de zéro que n'importe lequel des arguments, la somme doit être plus proche de moins l'infini. La valeur la plus extrême que nous pouvons produire est MIN_VALUE + MIN_VALUE, qui (là encore pour l'exemple d'octet) montre que pour toute valeur dans la plage (-1 à -128), le bit de signe est défini, tandis que toute valeur de débordement possible (-129 à -256 ) a le bit de signe effacé. Ainsi, le signe du résultat révèle à nouveau la condition de débordement. C'est ce que la moitié gauche (s & d & ~ r) vérifie pour le cas où les deux arguments (s, d) sont négatifs et un résultat positif. La logique est largement équivalente au cas positif; tous les modèles de bits qui peuvent résulter de l'ajout de deux valeurs négatives verront le bit de signe effacé si et seulement si un dépassement de capacité s'est produit.

Par défaut, les mathématiques int et long de Java s'enroulent silencieusement en cas de débordement et de sous-dépassement. (Les opérations entières sur d'autres types d'entiers sont effectuées en promouvant d'abord les opérandes en entier ou long, selon JLS 4.2.2 .)

A partir de Java 8, java.lang.Mathfournit addExact, subtractExact, multiplyExact, incrementExact, decrementExactet negateExactméthodes statiques pour les deux int et arguments longs qui effectuent l'opération nommée, jetant ArithmeticException en cas de débordement. (Il n'y a pas de méthode divideExact - vous devrez vérifier le cas particulier ( MIN_VALUE / -1) vous-même.)

À partir de Java 8, java.lang.Math propose également toIntExactde convertir un long en entier, en lançant ArithmeticException si la valeur du long ne tient pas dans un entier. Cela peut être utile, par exemple, pour calculer la somme des entiers en utilisant des mathématiques longues non contrôlées, puis en utilisant toIntExactpour effectuer un transtypage en int à la fin (mais attention à ne pas laisser votre somme déborder).

Si vous utilisez toujours une ancienne version de Java, Google Guava fournit des méthodes statiques IntMath et LongMath pour l'addition, la soustraction, la multiplication et l'exponentiation vérifiées (en cas de débordement). Ces classes fournissent également des méthodes pour calculer les factorielles et les coefficients binomiaux qui renvoient MAX_VALUEen cas de débordement (ce qui est moins pratique à vérifier). Classes utilitaires primitives de goyave, SignedBytes, UnsignedBytes, Shortset Ints, fournissent des checkedCastméthodes pour réduire les types plus grands (lancer IllegalArgumentException sur sous / débordement, non ArithmeticException), ainsi que des saturatingCastméthodes qui renvoient MIN_VALUEou MAX_VALUEen cas de débordement.

Java ne fait rien avec le débordement d'entier pour les types primitifs int ou long et ignore le débordement avec des entiers positifs et négatifs.

Cette réponse décrit d'abord le débordement d'entier, donne un exemple de la façon dont cela peut se produire, même avec des valeurs intermédiaires dans l'évaluation d'expression, puis donne des liens vers des ressources qui donnent des techniques détaillées pour prévenir et détecter le débordement d'entier.

L'arithmétique et les expressions entières entraînant un débordement inattendu ou non détecté sont une erreur de programmation courante. Le débordement d'entier inattendu ou non détecté est également un problème de sécurité exploitable bien connu, en particulier car il affecte les objets de tableau, de pile et de liste.

Un débordement peut se produire dans une direction positive ou négative où la valeur positive ou négative serait au-delà des valeurs maximale ou minimale pour le type primitif en question. Un débordement peut se produire dans une valeur intermédiaire lors de l'évaluation d'une expression ou d'une opération et affecter le résultat d'une expression ou d'une opération où la valeur finale devrait se situer dans la plage.

Parfois, un débordement négatif est appelé par erreur un débordement. Le sous-dépassement est ce qui se produit lorsqu'une valeur est plus proche de zéro que ne le permet la représentation. Le sous-dépassement se produit en arithmétique entière et est attendu. Le sous-dépassement d'entier se produit lorsqu'une évaluation d'entier serait comprise entre -1 et 0 ou 0 et 1. Ce qui serait un résultat fractionnaire tronqué à 0. Ceci est normal et attendu avec l'arithmétique d'entier et non considéré comme une erreur. Cependant, cela peut conduire au code de lever une exception. Un exemple est une exception «ArithmeticException: / by zero» si le résultat d'un dépassement de capacité d'entier est utilisé comme diviseur dans une expression.

Considérez le code suivant:

int bigValue = Integer.MAX_VALUE;
int x = bigValue * 2 / 5;
int y = bigValue / x;

ce qui entraîne l'attribution de 0 à x et l'évaluation ultérieure de bigValue / x lève une exception, "ArithmeticException: / by zero" (c'est-à-dire division par zéro), au lieu de y attribuer la valeur 2 à y.

Le résultat attendu pour x serait de 858 993 458, ce qui est inférieur à la valeur int maximale de 2 147 483 647. Cependant, le résultat intermédiaire de l'évaluation de Integer.MAX_Value * 2 serait de 4 294 967 294, ce qui dépasse la valeur int maximale et est de -2 conformément aux représentations entières du complément 2s. L'évaluation subséquente de -2 / 5 est évaluée à 0, ce qui est attribué à x.

Réorganisation de l'expression pour calculer x en une expression qui, lorsqu'elle est évaluée, divise avant de multiplier, le code suivant:

int bigValue = Integer.MAX_VALUE;
int x = bigValue / 5 * 2;
int y = bigValue / x;

entraîne l'attribution de x à 858 993 458 et de 2 à y, ce qui est attendu.

Le résultat intermédiaire de bigValue / 5 est 429 496 729, ce qui ne dépasse pas la valeur maximale pour un int. L'évaluation ultérieure de 429 496 729 * 2 ne dépasse pas la valeur maximale pour un int et le résultat attendu est affecté à x. L'évaluation pour y ne se divise alors pas par zéro. Les évaluations pour x et y fonctionnent comme prévu.

Les valeurs entières Java sont stockées en tant que et se comportent conformément aux représentations entières signées du complément 2s. Lorsqu'une valeur résultante est plus grande ou plus petite que les valeurs entières maximales ou minimales, une valeur entière complémentaire de 2 résulte à la place. Dans les situations qui ne sont pas expressément conçues pour utiliser le comportement du complément 2s, qui est la plupart des situations arithmétiques entières ordinaires, la valeur du complément 2s qui en résulte provoquera une logique de programmation ou une erreur de calcul comme indiqué dans l'exemple ci-dessus. Un excellent article de Wikipédia décrit ici les entiers binaires du complément 2s: complément à deux - Wikipedia

Il existe des techniques pour éviter un débordement d'entier involontaire. Les techinques peuvent être classées comme utilisant des tests de précondition, la conversion ascendante et BigInteger.

Le test de pré-condition comprend l'examen des valeurs entrant dans une opération ou une expression arithmétique pour s'assurer qu'un dépassement ne se produira pas avec ces valeurs. La programmation et la conception devront créer des tests qui garantissent que les valeurs d'entrée ne provoqueront pas de débordement, puis déterminer ce qu'il faut faire si des valeurs d'entrée se produisent qui provoqueront un débordement.

La conversion ascendante consiste à utiliser un type primitif plus grand pour effectuer l'opération ou l'expression arithmétique, puis à déterminer si la valeur résultante est au-delà des valeurs maximale ou minimale pour un entier. Même avec l'upcasting, il est toujours possible que la valeur ou une valeur intermédiaire dans une opération ou une expression dépasse les valeurs maximales ou minimales pour le type d'upcast et provoque un débordement, qui ne sera pas non plus détecté et provoquera des résultats inattendus et indésirables. Grâce à l'analyse ou aux conditions préalables, il peut être possible d'empêcher le débordement avec l'upcasting lorsque la prévention sans l'upcasting n'est pas possible ou pratique. Si les entiers en question sont déjà des types primitifs longs, la conversion ascendante n'est pas possible avec les types primitifs en Java.

La technique BigInteger consiste à utiliser BigInteger pour l'opération ou l'expression arithmétique à l'aide de méthodes de bibliothèque qui utilisent BigInteger. BigInteger ne déborde pas. Il utilisera toute la mémoire disponible, si nécessaire. Ses méthodes arithmétiques ne sont normalement que légèrement moins efficaces que les opérations entières. Il est toujours possible qu'un résultat utilisant BigInteger dépasse les valeurs maximum ou minimum pour un entier, cependant, un débordement ne se produira pas dans l'arithmétique menant au résultat. La programmation et la conception devront encore déterminer ce qu'il faut faire si un résultat BigInteger dépasse les valeurs maximales ou minimales pour le type de résultat primitif souhaité, par exemple, int ou long.

Le programme CERT du Carnegie Mellon Software Engineering Institute et Oracle ont créé un ensemble de normes pour une programmation Java sécurisée. Les normes incluent des techniques de prévention et de détection du débordement d'entier. La norme est publiée en tant que ressource en ligne librement accessible ici: CERT Oracle Secure Coding Standard for Java

La section de la norme qui décrit et contient des exemples pratiques de techniques de codage pour prévenir ou détecter le dépassement d'entier est ici: NUM00-J. Détecter ou empêcher le débordement d'entier

Un livre et un PDF de la norme CERT Oracle Secure Coding Standard pour Java sont également disponibles.

Ayant un peu rencontré ce problème moi-même, voici ma solution (pour la multiplication et l'addition):

static boolean wouldOverflowOccurwhenMultiplying(int a, int b) {
    // If either a or b are Integer.MIN_VALUE, then multiplying by anything other than 0 or 1 will result in overflow
    if (a == 0 || b == 0) {
        return false;
    } else if (a > 0 && b > 0) { // both positive, non zero
        return a > Integer.MAX_VALUE / b;
    } else if (b < 0 && a < 0) { // both negative, non zero
        return a < Integer.MAX_VALUE / b;
    } else { // exactly one of a,b is negative and one is positive, neither are zero
        if (b > 0) { // this last if statements protects against Integer.MIN_VALUE / -1, which in itself causes overflow.
            return a < Integer.MIN_VALUE / b;
        } else { // a > 0
            return b < Integer.MIN_VALUE / a;
        }
    }
}

boolean wouldOverflowOccurWhenAdding(int a, int b) {
    if (a > 0 && b > 0) {
        return a > Integer.MAX_VALUE - b;
    } else if (a < 0 && b < 0) {
        return a < Integer.MIN_VALUE - b;
    }
    return false;
}

n'hésitez pas à corriger en cas d'erreur ou si cela peut être simplifié. J'ai fait quelques tests avec la méthode de multiplication, principalement des cas marginaux, mais cela pourrait toujours être faux.

Il existe des bibliothèques qui fournissent des opérations arithmétiques sûres, qui vérifient le débordement / sous-dépassement d'entier. Par exemple, Guava IntMath.checkedAdd (int a, int b) retourne la somme de aet b, à condition qu'il ne déborde pas, et lève ArithmeticExceptionsi a + bdéborde en intarithmétique signée .

Il s'enroule.

par exemple:

public class Test {

    public static void main(String[] args) {
        int i = Integer.MAX_VALUE;
        int j = Integer.MIN_VALUE;

        System.out.println(i+1);
        System.out.println(j-1);
    }
}

impressions

-2147483648
2147483647

Je pense que vous devriez utiliser quelque chose comme ça et cela s'appelle Upcasting:

public int multiplyBy2(int x) throws ArithmeticException {
    long result = 2 * (long) x;    
    if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE){
        throw new ArithmeticException("Integer overflow");
    }
    return (int) result;
}

Vous pouvez lire plus loin ici: Détecter ou empêcher le débordement d'entier

C'est une source assez fiable.

Cela ne fait rien - le sous / débordement se produit simplement.

Un "-1" qui est le résultat d'un calcul qui a débordé n'est pas différent du "-1" résultant de toute autre information. Vous ne pouvez donc pas dire via un état ou en inspectant simplement une valeur si elle déborde.

Mais vous pouvez être intelligent dans vos calculs afin d'éviter un débordement, si cela est important, ou du moins de savoir quand cela se produira. Quelle est ta situation?

static final int safeAdd(int left, int right)
                 throws ArithmeticException {
  if (right > 0 ? left > Integer.MAX_VALUE - right
                : left < Integer.MIN_VALUE - right) {
    throw new ArithmeticException("Integer overflow");
  }
  return left + right;
}

static final int safeSubtract(int left, int right)
                 throws ArithmeticException {
  if (right > 0 ? left < Integer.MIN_VALUE + right
                : left > Integer.MAX_VALUE + right) {
    throw new ArithmeticException("Integer overflow");
  }
  return left - right;
}

static final int safeMultiply(int left, int right)
                 throws ArithmeticException {
  if (right > 0 ? left > Integer.MAX_VALUE/right
                  || left < Integer.MIN_VALUE/right
                : (right < -1 ? left > Integer.MIN_VALUE/right
                                || left < Integer.MAX_VALUE/right
                              : right == -1
                                && left == Integer.MIN_VALUE) ) {
    throw new ArithmeticException("Integer overflow");
  }
  return left * right;
}

static final int safeDivide(int left, int right)
                 throws ArithmeticException {
  if ((left == Integer.MIN_VALUE) && (right == -1)) {
    throw new ArithmeticException("Integer overflow");
  }
  return left / right;
}

static final int safeNegate(int a) throws ArithmeticException {
  if (a == Integer.MIN_VALUE) {
    throw new ArithmeticException("Integer overflow");
  }
  return -a;
}
static final int safeAbs(int a) throws ArithmeticException {
  if (a == Integer.MIN_VALUE) {
    throw new ArithmeticException("Integer overflow");
  }
  return Math.abs(a);
}

Je pense que ça devrait aller.

static boolean addWillOverFlow(int a, int b) {
    return (Integer.signum(a) == Integer.signum(b)) && 
            (Integer.signum(a) != Integer.signum(a+b)); 
}

Il y a un cas, qui n'est pas mentionné ci-dessus:

int res = 1;
while (res != 0) {
    res *= 2;

}
System.out.println(res);

produira:

0

Ce cas a été discuté ici: Un débordement d'entier produit zéro.