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

101

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.

Steve McLeod
quelle
6
Es ist schade, dass Java keinen indirekten Zugriff auf das Überlaufflag der CPU bietet, wie dies in C # der Fall ist .
Drew Noakes

Antworten:

92

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

bcoughlan
quelle
59

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
John Kugelman
quelle
Ich sollte erwähnen, dass a und b in meinem Szenario immer nicht negativ sind, was diesen Ansatz etwas vereinfachen würde.
Steve McLeod
3
Ich denke, dies kann in einem Fall fehlschlagen: a = -1 und b = 10. Das Maximum / a-Ausdruck führt zu Integer.MIN_VALUE und erkennt einen Überlauf, wenn keiner existiert
Kyle
Das ist wirklich schön. Für diejenigen fragen, ist der Grund , dies funktioniert , dass für integer n, n > xist das gleiche wie n > floor(x). Für positive ganze Zahlen ergibt die Division eine implizite Untergrenze. (Für negative Zahlen wird stattdessen
aufgerundet
Um die Adresse a = -1und b = 10Ausgabe, siehe meine Antwort unten.
Jim Pivarski
17

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 .

Umprogrammierer
quelle
4
Dies ist die beste Antwort: Verwenden Sie eine Bibliothek, die von Personen implementiert wurde, die die Maschinenarithmetik in Java wirklich verstehen und die von vielen Personen getestet wurde. Versuchen Sie nicht, Ihren eigenen zu schreiben oder einen der halbgebackenen ungetesteten Codes zu verwenden, die in den anderen Antworten angegeben sind!
Rich
@Enerccio - Ich verstehe deinen Kommentar nicht. Wollen Sie damit sagen, dass Guava nicht auf allen Systemen funktioniert? Ich kann Ihnen versichern, dass es überall funktionieren wird, wo Java es tut. Wollen Sie damit sagen, dass die Wiederverwendung von Code im Allgemeinen eine schlechte Idee ist? Ich bin anderer Meinung, wenn ja.
Rich
2
@Rich Ich sage, dass es eine schlechte Idee ist, eine riesige Bibliothek einzuschließen, damit Sie eine Funktion verwenden können.
Enerccio
Warum? Wenn Sie eine große Anwendung schreiben, zum Beispiel für ein Unternehmen, schadet eine zusätzliche JAR im Klassenpfad nicht und Guava enthält viele sehr nützliche Codes. Es ist viel besser, den sorgfältig getesteten Code wiederzuverwenden, als zu versuchen, eine eigene Version desselben zu schreiben (was Sie vermutlich empfehlen?). Wenn Sie in einer Umgebung schreiben, in der eine zusätzliche JAR sehr teuer sein wird (wo? Embedded Java?), Sollten Sie vielleicht nur diese Klasse aus Guava extrahieren. Ist das Kopieren einer nicht getesteten Antwort von StackOverflow besser als das Kopieren des sorgfältig getesteten Codes von Guava?
Rich
Ist das Auslösen einer Ausnahme nicht ein bisschen übertrieben für etwas, mit dem ein bedingtes Wenn-Dann umgehen kann?
Opfer
6

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()
}
Ulf Lindback
quelle
7
Ich finde diese Lösung ziemlich langsam
nothrow
Es ist jedoch wahrscheinlich der beste Weg, dies zu tun. Ich nahm an, dass dies eine numerische Anwendung war, weshalb ich sie nicht ohne weiteres empfohlen habe, aber dies ist wahrscheinlich der beste Weg, um dieses Problem zu lösen.
Stefan Kendall
2
Ich bin nicht sicher, ob Sie den Operator '>' mit BigInteger verwenden können. Die compareTo-Methode sollte verwendet werden.
Pierre
geändert zu compareTo, und Geschwindigkeit kann wichtig sein oder auch nicht, hängt von den Umständen ab, unter denen der Code verwendet wird.
Ulf Lindback
5

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

Hochleistungsmarke
quelle
meinst du : ceil(log(a)) + ceil(log(b)) > log(Long.MAX)?
Thomas Jung
1
Ich habe nachgeschaut. Für kleine Werte ist es 20% schneller als BigInteger und für Werte nahe MAX ist es fast gleich (5% schneller). Yossarians Code ist der schnellste (95% & 75% schneller als BigInteger).
Thomas Jung
Ich vermute eher, dass es in einigen Fällen scheitern kann.
Tom Hawtin - Tackline
Denken Sie daran, dass ein ganzzahliges Protokoll effektiv nur die Anzahl der führenden Nullen zählt und Sie einige häufige Fälle optimieren können (z. B. wenn ((a | b) & 0xffffffff00000000L) == 0) Sie wissen, dass Sie sicher sind). Auf der anderen Seite wird die Methode von John Kugelman wahrscheinlich besser abschneiden, wenn Sie Ihre Optimierung nicht für die häufigsten Fälle auf 30/40-Taktzyklen reduzieren können (eine Ganzzahldivision beträgt, wie ich mich erinnere, ca. 2 Bit / Taktzyklus).
Neil Coffey
PS Sorr, ich glaube, ich brauche ein zusätzliches Bit in der UND-Maske (0xffffffff80000000L) - es ist ein bisschen spät, aber Sie haben die Idee ...
Neil Coffey
4

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

nothrow
quelle
Ich habe nicht abgelehnt, aber es Math.Abs(a)funktioniert nicht, wenn es so aist Long.MIN_VALUE.
John Kugelman
@ John - a und b sind> 0. Ich denke, Yossarians Ansatz (b! = 0 && a> Long.MAX_VALUE / b) ist der beste.
Thomas Jung
@Thomas, a und b sind> = 0, dh nicht negativ.
Steve McLeod
2
Richtig, aber in diesem Fall werden die Abs nicht benötigt. Wenn negative Zahlen zulässig sind, schlägt dies für mindestens einen Kantenfall fehl. Das ist alles, was ich sage, nur pingelig zu sein.
John Kugelman
In Java müssen Sie Math.abs verwenden, nicht Math.Abs ​​(C # guy?)
dfa
4

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"
}
Naren
quelle
3

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.

Rogerdpack
quelle
Sie können Long.signum anstelle von Math.signum verwenden
aditsu beenden, weil SE am
3

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.

StFS
quelle
2

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.

fastcodejava
quelle
2
Ich denke nicht, dass es wichtig ist, ob ader größere oder der kleinere ist?
Thomas Ahle
2

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.

Jim Pivarski
quelle
Ich dachte nur, es würde es unnötig komplizieren, da diese Lösung nur funktioniert, wenn MIN_VALUE = -MAX_VALUE - 1kein anderer Fall (einschließlich Ihres Beispieltestfalls). Ich würde viel ändern müssen.
Jim Pivarski
1
Aus Gründen, die über die Bedürfnisse des Originalplakats hinausgehen; für Leute wie mich, die diese Seite gefunden haben, weil sie eine Lösung für einen allgemeineren Fall brauchten (Umgang mit negativen Zahlen und nicht ausschließlich Java 8). Da diese Lösung keine Funktionen enthält, die über reine Arithmetik und Logik hinausgehen, kann sie auch für C oder andere Sprachen verwendet werden.
Jim Pivarski
1

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.

Thomas Jung
quelle
Scheitert auch, wenn ein Überlauf eine perfekte Schleife verursacht.
Stefan Kendall
Haben Sie ein Beispiel dafür, was Sie gemeint haben?
Thomas Jung
Ich habe gerade einen kleinen Test geschrieben: Die Verwendung von BigInteger ist sechsmal langsamer als die Verwendung dieses Divisionsansatzes. Daher gehe ich davon aus, dass sich zusätzliche Überprüfungen für Eckfälle in Bezug auf die Leistung lohnen.
mhaller
Ich weiß nicht viel über Java-Compiler, aber ein Ausdruck wie a * b / bwird wahrscheinlich nur ain vielen anderen Kontexten optimiert .
SingleNegationElimination
TokenMacGuy - kann nicht so optimiert werden, wenn die Gefahr eines Überlaufs besteht.
Tom Hawtin - Tackline
1

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;
    }
}
dfa
quelle
Wird nicht helfen, wie einer der Operanden ist long.
Tom Hawtin - Tackline
1
Hast du das überhaupt getestet? Bei großen, aber nicht überlaufenden Werten von a & b schlägt dies aufgrund von Rundungsfehlern in der Doppelversion der Multiplikation fehl (versuchen Sie z. B. 123456789123L und 74709314L). Wenn Sie die Maschinenarithmetik nicht verstehen, ist es schlimmer, eine Antwort auf diese Art von präziser Frage zu erraten, als sie nicht zu beantworten, da dies die Menschen irreführen wird.
Rich
-1

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)

Xuan
quelle