Der beste Weg, um Javas Modul bei negativen Zahlen so zu verhalten, wie er sollte?

103

In Java, wenn Sie dies tun

a % b

Wenn a negativ ist, wird ein negatives Ergebnis zurückgegeben, anstatt wie gewünscht um b zu wickeln. Was ist der beste Weg, um dies zu beheben? Ich kann nur denken

a < 0 ? b + a : a % b
fent
quelle
12
Es gibt kein "richtiges" Modulverhalten beim Umgang mit negativen Zahlen - viele Sprachen machen es so, viele Sprachen machen es anders und einige Sprachen machen etwas völlig anderes. Zumindest die ersten beiden haben ihre Vor- und Nachteile.
4
Das ist einfach komisch für mich. Ich dachte, es sollte nur negativ zurückgeben, wenn b negativ ist.
Fent
1
mögliches Duplikat von Wie führt Java Modulberechnungen mit negativen Zahlen durch?
Erick Robertson
2
es ist. Der Titel dieser Frage sollte jedoch umbenannt werden. Ich würde nicht auf diese Frage klicken, wenn ich nach dieser suchen würde, weil ich bereits weiß, wie Java-Modul funktioniert.
10.
4
Ich habe es einfach in "Warum ist -13% 64 = 51?" Umbenannt, was in einer Million Jahren niemals etwas sein würde, wonach jemand suchen würde. Daher ist dieser Fragentitel viel besser und bei Schlüsselwörtern wie Modul, Negativ, Berechnung und Zahlen viel besser durchsuchbar.
Erick Robertson

Antworten:

144

Es verhält sich wie es sollte a% b = a - a / b * b; dh es ist der Rest.

Sie können (a% b + b)% b ausführen


Dieser Ausdruck funktioniert als Ergebnis von (a % b)ist notwendigerweise niedriger als b, egal ob apositiv oder negativ. Hinzufügen bkümmert sich um die negativen Werte a, da (a % b)zwischen ein negativer Wert ist -bund 0, (a % b + b)ist notwendigerweise niedriger als bund positiv. Das letzte Modulo ist ada, falls aes anfangs positiv war, denn wenn es positiv ist, (a % b + b)würde es größer werden als b. Daher wird (a % b + b) % bes kleiner als bwieder (und wirkt sich nicht auf negative aWerte aus).

Peter Lawrey
quelle
3
das funktioniert besser danke. und es funktioniert auch für negative Zahlen, die viel größer als b sind.
Fent
6
Es funktioniert, da das Ergebnis von (a % b)notwendigerweise niedriger ist als b(egal ob apositiv oder negativ), das Addieren bberücksichtigt die negativen Werte von a, da (a % b)niedriger als bund niedriger als 0, (a % b + b)notwendigerweise niedriger als bund positiv ist. Das letzte Modulo ist ada, falls aes anfangs positiv war, denn wenn es positiv ist, (a % b + b)würde es größer werden als b. Daher wird (a % b + b) % bes kleiner als bwieder (und wirkt sich nicht auf negative aWerte aus).
Ethanfar
1
@eitanfar Ich habe Ihre ausgezeichnete Erklärung in die Antwort aufgenommen (mit einer kleinen Korrektur für a < 0, vielleicht könnten Sie einen Blick darauf werfen)
Maarten Bodewes
5
Ich habe gerade gesehen, wie dies zu einer anderen Frage zum selben Thema kommentiert wurde. Es könnte erwähnenswert sein, dass dies (a % b + b) % bfür sehr große Werte von aund zusammenbricht b. Wenn Sie beispielsweise a = Integer.MAX_VALUE - 1und verwenden b = Integer.MAX_VALUE, erhalten Sie -3als Ergebnis eine negative Zahl, die Sie vermeiden möchten.
Thorbear
2
@Mikepote mit a whilewäre langsamer, wenn Sie es wirklich brauchen, außer Sie brauchen nur ein. ifIn diesem Fall ist es tatsächlich schneller.
Peter Lawrey
92

Ab Java 8 können Sie Math.floorMod (int x, int y) und Math.floorMod (long x, long y) verwenden . Beide Methoden liefern die gleichen Ergebnisse wie Peters Antwort.

Math.floorMod( 2,  3) =  2
Math.floorMod(-2,  3) =  1
Math.floorMod( 2, -3) = -1
Math.floorMod(-2, -3) = -2
John Krueger
quelle
1
beste Antwort für Java 8+
Charney Kaye
Cool, wusste nichts davon. Java 8 hat definitiv einige PITAs behoben.
Franz D.
4
Gute Möglichkeit. Funktioniert aber leider nicht mit floatoder doubleArgumenten. Mod binärer Operator ( %) funktioniert auch mit floatund doubleOperanden.
Mir-Ismaili
11

Für diejenigen, die Java 8 noch nicht verwenden (oder noch nicht verwenden können), kam Guava mit IntMath.mod () , das seit Guava 11.0 verfügbar ist , zur Rettung .

IntMath.mod( 2, 3) = 2
IntMath.mod(-2, 3) = 1

Eine Einschränkung: Im Gegensatz zu Math.floorMod () von Java 8 kann der Divisor (der zweite Parameter) nicht negativ sein.

Ibrahim Arief
quelle
7

In der Zahlentheorie ist das Ergebnis immer positiv. Ich würde vermuten, dass dies in Computersprachen nicht immer der Fall ist, da nicht alle Programmierer Mathematiker sind. Meine zwei Cent, ich würde es als Designfehler der Sprache betrachten, aber Sie können es jetzt nicht ändern.

= MOD (-4.180) = 176 = MOD (176, 180) = 176

weil 180 * (-1) + 176 = -4 das gleiche wie 180 * 0 + 176 = 176

Anhand des Uhrbeispiels hier, http://mathworld.wolfram.com/Congruence.html , würden Sie nicht sagen, dass die Dauer_der_Zeitmod-Zykluslänge -45 Minuten beträgt, sondern 15 Minuten, obwohl beide Antworten die Basisgleichung erfüllen.

Chris Golledge
quelle
1
In der Zahlentheorie ist es nicht immer positiv ... Sie fallen in Kongruenzklassen. Es steht Ihnen frei, einen beliebigen Kandidaten aus dieser Klasse für Ihre Notationszwecke auszuwählen. Die Idee ist jedoch, dass er der gesamten Klasse zugeordnet wird. Wenn Sie einen bestimmten anderen Kandidaten aus dieser Klasse verwenden, wird ein bestimmtes Problem erheblich vereinfacht (Auswahl -1statt n-1zum Beispiel). dann hab es drauf.
BeUndead
2

Java 8 hat Math.floorMod, aber es ist sehr langsam (seine Implementierung hat mehrere Unterteilungen, Multiplikationen und eine Bedingung). Es ist jedoch möglich, dass die JVM über einen intrinsisch optimierten Stub verfügt, der sie erheblich beschleunigen würde.

Der schnellste Weg, dies ohne zu tun, floorModist wie einige andere Antworten hier, aber ohne bedingte Verzweigungen und nur eine langsame %Operation.

Angenommen, n ist positiv und x kann alles sein:

int remainder = (x % n); // may be negative if x is negative
//if remainder is negative, adds n, otherwise adds 0
return ((remainder >> 31) & n) + remainder;

Die Ergebnisse, wenn n = 3:

x | result
----------
-4| 2
-3| 0
-2| 1
-1| 2
 0| 0
 1| 1
 2| 2
 3| 0
 4| 1

Wenn Sie nur eine gleichmäßige Verteilung zwischen 0und n-1nicht dem exakten Mod-Operator benötigen und Ihre xnicht in der Nähe gruppieren 0, ist das Folgende noch schneller, da mehr Parallelität auf Befehlsebene besteht und die langsame %Berechnung parallel zum anderen erfolgt Teile, da sie nicht vom Ergebnis abhängen.

return ((x >> 31) & (n - 1)) + (x % n)

Die Ergebnisse für die oben genannten mit n = 3:

x | result
----------
-5| 0
-4| 1
-3| 2
-2| 0
-1| 1
 0| 0
 1| 1
 2| 2
 3| 0
 4| 1
 5| 2

Wenn die Eingabe im gesamten Bereich eines int zufällig ist, ist die Verteilung beider beiden Lösungen gleich. Wenn sich die Eingangscluster nahe Null befinden, gibt es bei n - 1der letzteren Lösung zu wenige Ergebnisse .

Scott Carey
quelle
1

Hier ist eine Alternative:

a < 0 ? b-1 - (-a-1) % b : a % b

Dies kann schneller sein oder auch nicht als die andere Formel [(a% b + b)% b]. Im Gegensatz zur anderen Formel enthält sie einen Zweig, verwendet jedoch eine Modulo-Operation weniger. Wahrscheinlich ein Gewinn, wenn der Computer eine <0 richtig vorhersagen kann.

(Bearbeiten: Die Formel wurde korrigiert.)

Stefan Reich
quelle
1
Die Modulo-Operation erfordert jedoch eine Teilung, die noch langsamer sein kann (insbesondere wenn der Prozessor den Zweig fast immer richtig errät). Das ist also möglicherweise besser.
Dave
@KarstenR. Sie haben Recht! Ich habe die Formel korrigiert, jetzt funktioniert sie einwandfrei (benötigt aber zwei weitere Subtraktionen).
Stefan Reich
Das ist wahr @dave
Stefan Reich