Wie geht Java mit ganzzahligen Unter- und Überläufen um und wie würden Sie dies überprüfen?

Wie geht Java mit ganzzahligen Unter- und Überläufen um?

Wie würden Sie vor diesem Hintergrund überprüfen / testen, ob dies geschieht?

Wenn es überläuft, kehrt es zum Mindestwert zurück und fährt von dort fort. Wenn es unterläuft, kehrt es zum Maximalwert zurück und fährt von dort fort.

Sie können dies vorab wie folgt überprüfen:

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

(Sie können ersetzen intdurch longdie gleichen Prüfungen für auszuführen long)

Wenn Sie der Meinung sind, dass dies häufiger vorkommt, sollten Sie einen Datentyp oder ein Objekt verwenden, in dem größere Werte gespeichert werden können, z . B. longoder möglicherweise java.math.BigInteger. Der letzte läuft praktisch nicht über, der verfügbare JVM-Speicher ist die Grenze.

Wenn Sie sich bereits in Java8 befinden, können Sie die neuen Methoden Math#addExact()und Math#subtractExact()Methoden verwenden, die einen ArithmeticExceptionÜberlauf auslösen .

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

Den Quellcode finden Sie hier bzw. hier .

Natürlich können Sie sie auch sofort verwenden, anstatt sie in einer booleanDienstprogrammmethode zu verstecken .

Nun, was primitive Integer-Typen angeht, verarbeitet Java Over / Underflow überhaupt nicht (für Float und Double ist das Verhalten unterschiedlich, es wird auf +/- unendlich gespült, genau wie IEEE-754-Mandate).

Wenn Sie zwei Ints hinzufügen, erhalten Sie keine Anzeige, wenn ein Überlauf auftritt. Eine einfache Methode zur Überprüfung auf Überlauf besteht darin, den nächstgrößeren Typ zu verwenden, um die Operation tatsächlich auszuführen, und zu überprüfen, ob das Ergebnis für den Quelltyp noch im Bereich liegt:

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

Was Sie anstelle der Throw-Klauseln tun würden, hängt von Ihren Anwendungsanforderungen ab (Throw, Flush auf Min / Max oder einfach alles protokollieren). Wenn Sie bei langen Vorgängen einen Überlauf feststellen möchten, haben Sie mit Grundelementen kein Glück. Verwenden Sie stattdessen BigInteger.

Edit (2014-05-21): Da diese Frage ziemlich häufig angesprochen zu werden scheint und ich das gleiche Problem selbst lösen musste, ist es ziemlich einfach, den Überlaufzustand mit der gleichen Methode zu bewerten, mit der eine CPU ihr V-Flag berechnen würde.

Es ist im Grunde ein boolescher Ausdruck, der das Vorzeichen beider Operanden sowie das Ergebnis beinhaltet:

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

In Java ist es einfacher, den Ausdruck (im if) auf die gesamten 32 Bits anzuwenden und das Ergebnis mit <0 zu überprüfen (dies testet effektiv das Vorzeichenbit). Das Prinzip funktioniert für alle ganzzahligen primitiven Typen genau gleich. Wenn Sie alle Deklarationen in der obigen Methode in long ändern, funktioniert es lange.

Bei kleineren Typen muss aufgrund der impliziten Konvertierung in int (Einzelheiten finden Sie im JLS für bitweise Operationen) anstelle von <0 das Vorzeichenbit explizit maskiert werden (0x8000 für kurze Operanden, 0x80 für Byteoperanden, Casts anpassen und Parameterdeklaration entsprechend):

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

(Beachten Sie, dass im obigen Beispiel der Ausdruck "Notwendigkeit zum Überziehen der Überlauferkennung" verwendet wird.)

Wie / warum funktionieren diese booleschen Ausdrücke? Erstens zeigt ein logisches Denken, dass ein Überlauf nur auftreten kann, wenn die Vorzeichen beider Argumente gleich sind. Denn wenn ein Argument negativ ist und eine positiv ist, ist das Ergebnis (Add) muss näher an Null ist , oder im Extremfall ein Argument Null ist , das gleiche wie das andere Argument. Da die Argumente selbst keine Überlaufbedingung erzeugen können, kann ihre Summe auch keinen Überlauf erzeugen.

Was passiert also, wenn beide Argumente das gleiche Vorzeichen haben? Schauen wir uns den Fall an, bei dem beide positiv sind: Wenn Sie zwei Argumente hinzufügen, die eine Summe erzeugen, die größer als die Typen MAX_VALUE ist, ergibt sich immer ein negativer Wert, sodass ein Überlauf auftritt, wenn arg1 + arg2> MAX_VALUE. Der maximale Wert, der sich ergeben könnte, wäre nun MAX_VALUE + MAX_VALUE (im Extremfall sind beide Argumente MAX_VALUE). Für ein Byte (Beispiel) würde dies 127 + 127 = 254 bedeuten. Wenn man die Bitdarstellungen aller Werte betrachtet, die sich aus der Addition von zwei positiven Werten ergeben können, stellt man fest, dass für diejenigen, die überlaufen (128 bis 254), Bit 7 gesetzt ist, während Bei allen, die nicht überlaufen (0 bis 127), ist Bit 7 (oberstes Vorzeichen) gelöscht. Genau das prüft der erste (rechte) Teil des Ausdrucks:

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

(~ s & ~ d & r) wird nur dann wahr, wenn beide Operanden (s, d) positiv und das Ergebnis (r) negativ sind (der Ausdruck funktioniert auf allen 32 Bits, aber das einzige Bit, an dem wir interessiert sind ist das oberste (Vorzeichen-) Bit, gegen das mit <0 geprüft wird.

Wenn nun beide Argumente negativ sind, kann ihre Summe niemals näher an Null liegen als eines der Argumente. Die Summe muss näher an minus unendlich sein. Der extremste Wert, den wir erzeugen können, ist MIN_VALUE + MIN_VALUE, was (wiederum für das Byte-Beispiel) zeigt, dass für jeden Wert im Bereich (-1 bis -128) das Vorzeichenbit gesetzt ist, während jeder mögliche Überlaufwert (-129 bis -256) ) hat das Vorzeichenbit gelöscht. Das Vorzeichen des Ergebnisses zeigt also erneut den Überlaufzustand. Das ist es, was die linke Hälfte (s & d & ~ r) auf den Fall prüft, in dem beide Argumente (s, d) negativ und ein positives Ergebnis sind. Die Logik entspricht weitgehend dem positiven Fall; Bei allen Bitmustern, die sich aus der Addition von zwei negativen Werten ergeben können, wird das Vorzeichenbit genau dann gelöscht, wenn ein Unterlauf aufgetreten ist.

Standardmäßig werden Javas int und long math stillschweigend um Überlauf und Unterlauf herumlaufen. (Integer-Operationen für andere Integer-Typen werden ausgeführt, indem zuerst die Operanden gemäß JLS 4.2.2 auf int oder long heraufgestuft werden .)

Wie von Java 8 java.lang.Mathbietet addExact, subtractExact, multiplyExact, incrementExact, decrementExactund negateExactstatische Methoden sowohl für int und lange Argumente , die die benannte Operation durchführen, ArithmeticException bei Überlauf zu werfen. (Es gibt keine DivideExact-Methode - Sie müssen den einen Sonderfall ( MIN_VALUE / -1) selbst überprüfen .)

Ab Java 8 bietet java.lang.Math auch die Möglichkeit toIntExact, ein Long in ein Int umzuwandeln und eine ArithmeticException auszulösen, wenn der Long-Wert nicht in ein Int passt. Dies kann nützlich sein, um z. B. die Summe der Ints mit ungeprüfter langer Mathematik zu berechnen und dann toIntExactam Ende mit to in int umzuwandeln (aber achten Sie darauf, dass Ihre Summe nicht überläuft).

Wenn Sie noch eine ältere Java-Version verwenden, bietet Google Guava statische IntMath- und LongMath- Methoden für die überprüfte Addition, Subtraktion, Multiplikation und Exponentiation (Überlauf). Diese Klassen bieten auch Methoden zur Berechnung von Fakultäten und Binomialkoeffizienten, die MAX_VALUEbeim Überlauf zurückkehren (was weniger bequem zu überprüfen ist). Guava primitive Utility - Klassen, SignedBytes, UnsignedBytes, Shortsund Intsbieten checkedCastMethoden für größere Arten Verengung (werfen Illegal auf unter / Überlauf, nicht ArithmeticException) sowie saturatingCastMethoden , die Rückkehr MIN_VALUEoder MAX_VALUEbei Überlauf.

Java macht nichts mit dem Integer-Überlauf für int- oder long-primitive Typen und ignoriert den Überlauf mit positiven und negativen Ganzzahlen.

Diese Antwort beschreibt zunächst den Überlauf von Ganzzahlen, gibt ein Beispiel dafür, wie dies auch bei Zwischenwerten bei der Ausdrucksbewertung geschehen kann, und enthält dann Links zu Ressourcen, die detaillierte Techniken zum Verhindern und Erkennen eines Überlaufs von Ganzzahlen enthalten.

Ganzzahlige Arithmetik und Ausdrücke, die zu einem unerwarteten oder unerkannten Überlauf führen, sind ein häufiger Programmierfehler. Ein unerwarteter oder nicht erkannter Überlauf von Ganzzahlen ist ebenfalls ein bekanntes ausnutzbares Sicherheitsproblem, insbesondere da es Array-, Stapel- und Listenobjekte betrifft.

Ein Überlauf kann entweder in positiver oder negativer Richtung auftreten, wobei der positive oder negative Wert über den Maximal- oder Minimalwerten für den betreffenden primitiven Typ liegen würde. Ein Überlauf kann in einem Zwischenwert während der Ausdrucks- oder Operationsbewertung auftreten und sich auf das Ergebnis eines Ausdrucks oder einer Operation auswirken, bei der erwartet wird, dass der Endwert innerhalb des Bereichs liegt.

Manchmal wird ein negativer Überlauf fälschlicherweise als Unterlauf bezeichnet. Unterlauf ist das, was passiert, wenn ein Wert näher an Null liegt, als es die Darstellung zulässt. Der Unterlauf tritt in der Ganzzahlarithmetik auf und wird erwartet. Ein ganzzahliger Unterlauf tritt auf, wenn eine ganzzahlige Auswertung zwischen -1 und 0 oder 0 und 1 liegt. Was ein gebrochenes Ergebnis wäre, wird auf 0 abgeschnitten. Dies ist normal und wird mit ganzzahliger Arithmetik erwartet und nicht als Fehler betrachtet. Dies kann jedoch dazu führen, dass Code eine Ausnahme auslöst. Ein Beispiel ist eine Ausnahme "ArithmeticException: / by zero", wenn das Ergebnis eines ganzzahligen Unterlaufs als Divisor in einem Ausdruck verwendet wird.

Betrachten Sie den folgenden Code:

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

Dies führt dazu, dass x 0 zugewiesen wird und die anschließende Auswertung von bigValue / x eine Ausnahme "ArithmeticException: / by zero" (dh durch Null teilen) auslöst, anstatt y den Wert 2 zuzuweisen.

Das erwartete Ergebnis für x wäre 858.993.458, was weniger als der maximale int-Wert von 2.147.483.647 ist. Das Zwischenergebnis aus der Auswertung von Integer.MAX_Value * 2 wäre jedoch 4.294.967.294, was den maximalen int-Wert überschreitet und gemäß 2s-Komplement-Integer-Darstellungen -2 beträgt. Die nachfolgende Auswertung von -2 / 5 ergibt 0, die x zugewiesen wird.

Neuanordnen des Ausdrucks für die Berechnung von x in einen Ausdruck, der bei Auswertung vor dem Multiplizieren den folgenden Code teilt:

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

führt dazu, dass x 858.993.458 und y 2 zugewiesen wird, was erwartet wird.

Das Zwischenergebnis von bigValue / 5 ist 429.496.729, was den Maximalwert für ein int nicht überschreitet. Die nachfolgende Auswertung von 429.496.729 * 2 überschreitet nicht den Maximalwert für ein int und das erwartete Ergebnis wird x zugewiesen. Die Auswertung für y wird dann nicht durch Null geteilt. Die Auswertungen für x und y funktionieren wie erwartet.

Java-Ganzzahlwerte werden als 2s-Komplement-Ganzzahldarstellungen mit Vorzeichen gespeichert und verhalten sich entsprechend. Wenn ein resultierender Wert größer oder kleiner als die maximalen oder minimalen Ganzzahlwerte wäre, ergibt sich stattdessen der Komplement-Ganzzahlwert einer 2. In Situationen, die nicht ausdrücklich für die Verwendung des 2s-Komplementverhaltens ausgelegt sind, was die meisten gewöhnlichen ganzzahligen arithmetischen Situationen sind, verursacht der resultierende 2s-Komplementwert eine Programmierlogik oder einen Berechnungsfehler, wie im obigen Beispiel gezeigt. Ein ausgezeichneter Wikipedia-Artikel beschreibt hier binäre Ganzzahlen mit 2 Komplimenten: Zweierkomplement - Wikipedia

Es gibt Techniken, um einen unbeabsichtigten Ganzzahlüberlauf zu vermeiden. Techinques können als Pre-Condition-Tests, Upcasting und BigInteger kategorisiert werden.

Das Testen vor der Bedingung umfasst das Untersuchen der Werte, die in eine arithmetische Operation oder einen arithmetischen Ausdruck eingehen, um sicherzustellen, dass bei diesen Werten kein Überlauf auftritt. Programmierung und Design müssen Tests erstellen, die sicherstellen, dass Eingabewerte keinen Überlauf verursachen, und dann bestimmen, was zu tun ist, wenn Eingabewerte auftreten, die einen Überlauf verursachen.

Upcasting umfasst die Verwendung eines größeren primitiven Typs zum Ausführen der arithmetischen Operation oder des Ausdrucks und das anschließende Bestimmen, ob der resultierende Wert über den Maximal- oder Minimalwerten für eine Ganzzahl liegt. Selbst beim Upcasting ist es immer noch möglich, dass der Wert oder ein Zwischenwert in einer Operation oder einem Ausdruck über den Maximal- oder Minimalwerten für den Upcast-Typ liegt und einen Überlauf verursacht, der ebenfalls nicht erkannt wird und unerwartete und unerwünschte Ergebnisse verursacht. Durch Analyse oder Vorbedingungen kann es möglich sein, einen Überlauf mit Upcasting zu verhindern, wenn eine Prävention ohne Upcasting nicht möglich oder praktisch ist. Wenn die fraglichen Ganzzahlen bereits lange primitive Typen sind, ist ein Upcasting mit primitiven Typen in Java nicht möglich.

Die BigInteger-Technik umfasst die Verwendung von BigInteger für die arithmetische Operation oder den Ausdruck unter Verwendung von Bibliotheksmethoden, die BigInteger verwenden. BigInteger läuft nicht über. Bei Bedarf wird der gesamte verfügbare Speicher verwendet. Seine arithmetischen Methoden sind normalerweise nur geringfügig weniger effizient als ganzzahlige Operationen. Es ist weiterhin möglich, dass ein Ergebnis mit BigInteger über den Maximal- oder Minimalwerten für eine Ganzzahl liegt. In der zum Ergebnis führenden Arithmetik tritt jedoch kein Überlauf auf. Programmierung und Design müssen noch festlegen, was zu tun ist, wenn ein BigInteger-Ergebnis über den Maximal- oder Minimalwerten für den gewünschten primitiven Ergebnistyp liegt, z. B. int oder long.

Das CERT-Programm des Carnegie Mellon Software Engineering Institute und Oracle haben eine Reihe von Standards für die sichere Java-Programmierung erstellt. In den Standards sind Techniken zum Verhindern und Erkennen eines Ganzzahlüberlaufs enthalten. Der Standard wird hier als frei zugängliche Online-Ressource veröffentlicht: Der CERT Oracle Secure Coding Standard für Java

Der Abschnitt des Standards, der praktische Beispiele für Codierungstechniken zum Verhindern oder Erkennen eines Ganzzahlüberlaufs beschreibt und enthält, ist hier: NUM00-J. Erkennen oder verhindern Sie einen Ganzzahlüberlauf

Buchform und PDF-Form des CERT Oracle Secure Coding Standard für Java sind ebenfalls verfügbar.

Nachdem ich selbst auf dieses Problem gestoßen bin, ist hier meine Lösung (sowohl für die Multiplikation als auch für die 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;
}

Fühlen Sie sich frei zu korrigieren, wenn falsch oder vereinfacht werden kann. Ich habe einige Tests mit der Multiplikationsmethode durchgeführt, hauptsächlich Randfälle, aber es könnte immer noch falsch sein.

Es gibt Bibliotheken, die sichere arithmetische Operationen bereitstellen und den Ganzzahlüberlauf / -unterlauf überprüfen. Zum Beispiel gibt Guavas IntMath.checkedAdd (int a, int b) die Summe von aund zurück b, sofern es nicht überläuft, und wirft, ArithmeticExceptionwenn es a + bin vorzeichenbehafteter intArithmetik überläuft .

Es wickelt sich herum.

z.B:

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

druckt

-2147483648
2147483647

Ich denke, Sie sollten so etwas verwenden und es heißt 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;
}

Lesen Sie hier weiter: Erkennen oder verhindern Sie einen Ganzzahlüberlauf

Es ist eine ziemlich zuverlässige Quelle.

Es macht nichts - der Unter- / Überlauf passiert einfach.

Ein "-1", das das Ergebnis einer übergelaufenen Berechnung ist, unterscheidet sich nicht von dem "-1", das sich aus anderen Informationen ergibt. Sie können also nicht anhand eines Status oder anhand eines Werts feststellen, ob dieser übergelaufen ist.

Sie können jedoch bei Ihren Berechnungen klug sein, um einen Überlauf zu vermeiden, wenn dies wichtig ist, oder zumindest zu wissen, wann er eintreten wird. Wie ist deine 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);
}

Ich denke das sollte in Ordnung sein.

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

Es gibt einen Fall, der oben nicht erwähnt wurde:

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

}
System.out.println(res);

wird herstellen:

0

Dieser Fall wurde hier diskutiert: Ein ganzzahliger Überlauf erzeugt Null.