Wie kann ich überprüfen, ob das Multiplizieren von zwei Zahlen in Java zu einem Überlauf führt?

Ich möchte den Sonderfall behandeln, bei dem das Multiplizieren zweier Zahlen einen Überlauf verursacht. Der Code sieht ungefähr so ​​aus:

int a = 20;
long b = 30;

// if a or b are big enough, this result will silently overflow
long c = a * b;

Das ist eine vereinfachte Version. Im realen Programm aund bwerden zur Laufzeit an anderer Stelle bezogen. Was ich erreichen möchte, ist ungefähr so:

long c;
if (a * b will overflow) {
    c = Long.MAX_VALUE;
} else {
    c = a * b;
}

Wie schlagen Sie vor, dass ich dies am besten codiere?

Update: aund bsind in meinem Szenario immer nicht negativ.

Java 8 hat Math.multiplyExact, Math.addExactusw. für ints und lang. Diese werfen einen ungeprüften ArithmeticExceptionÜberlauf auf.

Wenn aund bbeide positiv sind, können Sie verwenden:

if (a != 0 && b > Long.MAX_VALUE / a) {
    // Overflow
}

Wenn Sie sowohl mit positiven als auch mit negativen Zahlen umgehen müssen, ist dies komplizierter:

long maximum = Long.signum(a) == Long.signum(b) ? Long.MAX_VALUE : Long.MIN_VALUE;

if (a != 0 && (b > 0 && b > maximum / a ||
               b < 0 && b < maximum / a))
{
    // Overflow
}

Hier ist eine kleine Tabelle, die ich zusammengestellt habe, um dies zu überprüfen, und so getan habe, als ob ein Überlauf bei -10 oder +10 auftritt:

a =  5   b =  2     2 >  10 /  5
a =  2   b =  5     5 >  10 /  2
a = -5   b =  2     2 > -10 / -5
a = -2   b =  5     5 > -10 / -2
a =  5   b = -2    -2 < -10 /  5
a =  2   b = -5    -5 < -10 /  2
a = -5   b = -2    -2 <  10 / -5
a = -2   b = -5    -5 <  10 / -2

Es gibt Java-Bibliotheken, die sichere arithmetische Operationen bereitstellen und lange Über- / Unterläufe überprüfen. Zum Beispiel gibt Guavas LongMath.checkedMultiply (long a, long b) das Produkt von aund zurück b, sofern es nicht überläuft, und wirft, ArithmeticExceptionwenn es a * bin vorzeichenbehafteter longArithmetik überläuft .

Sie können stattdessen java.math.BigInteger verwenden und die Größe des Ergebnisses überprüfen (den Code wurde nicht getestet):

BigInteger bigC = BigInteger.valueOf(a) * multiply(BigInteger.valueOf(b));
if(bigC.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) > 0) {
  c = Long.MAX_VALUE;
} else {
  c = bigC.longValue()
}

Verwenden Sie Logarithmen, um die Größe des Ergebnisses zu überprüfen.

Hat Java so etwas wie int.MaxValue? Wenn ja, dann versuchen Sie es

if (b != 0 && Math.abs(a) > Math.abs(Long.MAX_VALUE / b))
{
 // it will overflow
}

edit: gesehen Long.MAX_VALUE in Frage

Hier ist der einfachste Weg, den ich mir vorstellen kann

int a = 20;
long b = 30;
long c = a * b;

if(c / b == a) {
   // Everything fine.....no overflow
} else {
   // Overflow case, because in case of overflow "c/b" can't equal "a"
}

Von jruby gestohlen

    long result = a * b;
    if (a != 0 && result / a != b) {
       // overflow
    }

UPDATE: Dieser Code ist kurz und funktioniert gut. es schlägt jedoch für a = -1, b = Long.MIN_VALUE fehl.

Eine mögliche Verbesserung:

long result = a * b;
if( (Math.signum(a) * Math.signum(b) != Math.signum(result)) || 
    (a != 0L && result / a != b)) {
    // overflow
}

Beachten Sie, dass dies einige Überläufe ohne Teilung auffängt.

Wie bereits erwähnt, verfügt Java 8 über Math.xxxExact-Methoden, die beim Überlauf Ausnahmen auslösen.

Wenn Sie Java 8 nicht für Ihr Projekt verwenden, können Sie die recht kompakten Implementierungen trotzdem "ausleihen".

Hier sind einige Links zu diesen Implementierungen im JDK-Quellcode-Repository. Keine Garantie, ob diese gültig bleiben. In jedem Fall sollten Sie jedoch in der Lage sein, die JDK-Quelle herunterzuladen und zu sehen, wie sie ihre Magie innerhalb der java.lang.MathKlasse entfalten.

Math.multiplyExact(long, long) http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/lang/Math.java#l925

Math.addExact(long, long) http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/lang/Math.java#l830

usw. usw.

AKTUALISIERT: Es wurden ungültige Links zur Website eines Drittanbieters zu Links zu den Mercurial-Repositorys von Open JDK ausgetauscht.

Ich bin mir nicht sicher, warum niemand nach einer Lösung sucht wie:

if (Long.MAX_VALUE/a > b) {
     // overflows
} 

Wählen Sie eine der beiden Zahlen, um größer zu sein.

Ich möchte auf John Kugelmans Antwort aufbauen, ohne sie durch direkte Bearbeitung zu ersetzen. Es funktioniert für seinen Testfall ( MIN_VALUE = -10, MAX_VALUE = 10) aufgrund der Symmetrie von MIN_VALUE == -MAX_VALUE, was bei Zweierkomplement-Ganzzahlen nicht der Fall ist. In Wirklichkeit MIN_VALUE == -MAX_VALUE - 1.

scala> (java.lang.Integer.MIN_VALUE, java.lang.Integer.MAX_VALUE)
res0: (Int, Int) = (-2147483648,2147483647)

scala> (java.lang.Long.MIN_VALUE, java.lang.Long.MAX_VALUE)
res1: (Long, Long) = (-9223372036854775808,9223372036854775807)

Wenn John Kugelmans Antwort auf das wahre MIN_VALUEund angewendet wird, MAX_VALUEergibt sich ein Überlauf, wann a == -1und b ==was auch immer (Punkt, der zuerst von Kyle angesprochen wurde). Hier ist eine Möglichkeit, dies zu beheben:

long maximum = Long.signum(a) == Long.signum(b) ? Long.MAX_VALUE : Long.MIN_VALUE;

if ((a == -1 && b == Long.MIN_VALUE) ||
    (a != -1 && a != 0 && ((b > 0 && b > maximum / a) ||
                           (b < 0 && b < maximum / a))))
{
    // Overflow
}

Es ist keine allgemeine Lösung für irgendein MIN_VALUEund MAX_VALUE, aber es ist allgemein für Java Longund Integerund jeden Wert von aund b.

Vielleicht:

if(b!= 0 && a * b / b != a) //overflow

Ich bin mir nicht sicher über diese "Lösung".

Bearbeiten: Hinzugefügt b! = 0.

Bevor Sie abstimmen : a * b / b wird nicht optimiert. Dies wäre ein Compiler-Fehler. Ich sehe immer noch keinen Fall, in dem der Überlauffehler maskiert werden kann.

Vielleicht hilft dir das:

/**
 * @throws ArithmeticException on integer overflow
 */
static long multiply(long a, long b) {
    double c = (double) a * b;
    long d = a * b;

    if ((long) c != d) {
        throw new ArithmeticException("int overflow");
    } else {
        return d;
    }
}

c / c ++ (lang * lang):

const int64_ w = (int64_) a * (int64_) b;    
if ((long) (w >> sizeof(long) * 8) != (long) w >> (sizeof(long) * 8 - 1))
    // overflow

java (int * int, sorry, ich habe int64 in java nicht gefunden):

const long w = (long) a * (long) b;    
int bits = 32; // int is 32bits in java    
if ( (int) (w >> bits) ！= (int) (w >> (bits - 1))) {
   // overflow
}

1. Speichern Sie das Ergebnis in großer Schrift (int * int setzt das Ergebnis auf long, long * long auf int64)

2.cmp Ergebnis >> Bits und Ergebnis >> (Bits - 1)