Najlepszy sposób, aby moduł Java zachowywał się tak, jak powinien, z liczbami ujemnymi?

103

W Javie, kiedy to robisz

a % b

Jeśli a jest ujemne, zwróci wynik ujemny, zamiast zawijać się do b, tak jak powinno. Jak najlepiej to naprawić? Jedyny sposób, w jaki mogę myśleć, to

a < 0 ? b + a : a % b
fent
źródło
12
Nie ma „właściwego” zachowania modułu, gdy mamy do czynienia z liczbami ujemnymi - wiele języków robi to w ten sposób, wiele języków robi to inaczej, a kilka języków robi coś zupełnie innego. Przynajmniej dwa pierwsze mają swoje wady i zalety.
4
to jest po prostu dziwne dla mnie. Pomyślałem, że powinno zwrócić wartość ujemną tylko wtedy, gdy b jest ujemne.
wypuszczony
2
to jest. ale tytuł tego pytania powinien zostać zmieniony. nie klikałbym tego pytania, gdybym szukał tego, ponieważ już wiem, jak działa moduł Java.
święto
4
Właśnie zmieniłem nazwę na „Dlaczego -13% 64 = 51?”, Co nigdy nie byłoby czymś, czego ktoś szukałby za milion lat. Tak więc tytuł pytania jest znacznie lepszy i dużo łatwiejszy do wyszukania na podstawie słów kluczowych, takich jak moduł, wartość ujemna, obliczenia, liczby.
Erick Robertson

Odpowiedzi:

144

Zachowuje się tak, jak powinien a% b = a - a / b * b; tj. to reszta.

Możesz zrobić (a% b + b)% b


To wyrażenie działa, ponieważ wynik (a % b)jest koniecznie niższy niż b, bez względu na ato, czy jest dodatni czy ujemny. Dodawanie buwzględnia ujemne wartości a, ponieważ (a % b)jest wartością ujemną między -bi 0, (a % b + b)jest z konieczności mniejsze niż bi dodatnie. Ostatni modulo jest tam na wypadek, gdyby abył dodatni na początku, ponieważ jeśli ajest dodatnie, (a % b + b)stałoby się większe niż b. Dlatego (a % b + b) % bzmienia go na mniejszy niż bponownie (i nie wpływa na awartości ujemne ).

Peter Lawrey
źródło
3
to działa lepiej, dzięki. i działa również dla liczb ujemnych, które są znacznie większe niż b.
wypuszczony
6
Działa, ponieważ wynik (a % b)jest koniecznie niższy niż b(nieważne, czy ajest dodatni czy ujemny), dodawanie buwzględnia ujemne wartości a, ponieważ (a % b)jest niższe bi niższe niż 0, (a % b + b)jest z konieczności niższe bi dodatnie. Ostatni modulo jest tam na wypadek, gdyby abył dodatni na początku, ponieważ jeśli ajest dodatnie, (a % b + b)stałoby się większe niż b. Dlatego (a % b + b) % bzmienia go na mniejszy niż bponownie (i nie wpływa na awartości ujemne ).
ethanfar
1
@eitanfar W odpowiedzi zawarłem twoje doskonałe wyjaśnienie (z niewielką poprawką a < 0, może mógłbyś rzucić okiem)
Maarten Bodewes
5
Właśnie widziałem, jak to skomentowało inne pytanie dotyczące tego samego tematu; Warto wspomnieć, że (a % b + b) % brozkłada się na bardzo duże wartości ai b. Na przykład użycie a = Integer.MAX_VALUE - 1i b = Integer.MAX_VALUEda -3jako wynik, czyli liczbę ujemną, czego chciałeś uniknąć.
Thorbear
2
@Mikepote używanie a whilebyłoby wolniejsze, jeśli naprawdę go potrzebujesz, z wyjątkiem tego, że potrzebujesz tylko wtedy, ifgdy jest to faktycznie szybsze.
Peter Lawrey
92

Od wersji Java 8 można używać Math.floorMod (int x, int y) i Math.floorMod (long x, long y) . Obie te metody zwracają te same wyniki, co odpowiedź Petera.

Math.floorMod( 2,  3) =  2
Math.floorMod(-2,  3) =  1
Math.floorMod( 2, -3) = -1
Math.floorMod(-2, -3) = -2
John Krueger
źródło
1
najlepsza odpowiedź dla Java 8+
Charney Kaye
Fajnie, nie wiedziałem o tym. Java 8 ostatecznie naprawiła kilka PITA.
Franz D.
4
Dobry sposób. Ale niestety nie działa z argumentami floatani double. Operator binarny mod ( %) działa również z operandami floati double.
Mir-Ismaili
11

Dla tych, którzy jeszcze nie używają (lub nie mogą jeszcze używać) Java 8, Guava przyszedł na ratunek dzięki IntMath.mod () , dostępnym od wersji Guava 11.0.

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

Jedno zastrzeżenie: w przeciwieństwie do Math.floorMod () w Java 8, dzielnik (drugi parametr) nie może być ujemny.

Ibrahim Arief
źródło
7

W teorii liczb wynik jest zawsze pozytywny. Wydaje mi się, że nie zawsze tak jest w językach komputerowych, ponieważ nie wszyscy programiści są matematykami. Moje dwa centy, uznałbym to za defekt konstrukcyjny języka, ale nie możesz tego teraz zmienić.

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

ponieważ 180 * (-1) + 176 = -4 to samo co 180 * 0 + 176 = 176

Korzystając z przykładu zegara tutaj, http://mathworld.wolfram.com/Congruence.html , nie powiedziałbyś, że czas trwania_czasu mod długość_cyklu wynosi -45 minut, powiedziałbyś, że 15 minut, mimo że obie odpowiedzi spełniają podstawowe równanie.

Chris Golledge
źródło
1
W teorii liczb nie zawsze jest to pozytywne… Należy do klas kongruencji. Możesz wybrać dowolnego kandydata z tej klasy do celów notacji, ale chodzi o to, że mapuje on na całą tę klasę, a jeśli użycie konkretnego innego kandydata z tej klasy znacznie upraszcza pewien problem (wybór -1zamiast n-1na przykład) to mieć na to.
BeUndead,
2

Java 8 ma Math.floorMod, ale jest bardzo powolna (jej implementacja ma wiele podziałów, mnożeń i warunek). Możliwe, że JVM ma wbudowany zoptymalizowany kod pośredniczący, co znacznie przyspieszyłoby to.

Najszybszym sposobem na zrobienie tego bez floorModjest jak inne odpowiedzi tutaj, ale bez gałęzi warunkowych i tylko z jedną wolną% operacji.

Zakładając, że n jest dodatnie, a x może być dowolne:

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;

Wyniki, gdy n = 3:

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

Jeśli potrzebne jest tylko rozkład jednolity między 0a n-1i nie dokładna operatora mod, a twoje x„s nie klaster blisko 0dodaje będzie jeszcze szybciej, ponieważ nie ma więcej poziom instrukcja równoległość i powolne %obliczenie nastąpi równolegle z innymi części, ponieważ nie zależą one od wyniku.

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

Wyniki dla powyższego z 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

Jeśli dane wejściowe są losowe w pełnym zakresie liczby int, rozkład obu rozwiązań będzie taki sam. Jeśli klastry wejściowe są bliskie zeru, n - 1w tym drugim rozwiązaniu wyników będzie za mało .

Scott Carey
źródło
1

Oto alternatywa:

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

To może, ale nie musi, być szybsze niż ta inna formuła [(a% b + b)% b]. W przeciwieństwie do drugiej formuły zawiera gałąź, ale wykorzystuje jedną operację modulo mniej. Prawdopodobnie wygrana, jeśli komputer może poprawnie przewidzieć <0.

(Edycja: Poprawiono formułę.)

Stefana Reicha
źródło
1
Ale operacja modulo wymaga podziału, który mógłby być jeszcze wolniejszy (zwłaszcza jeśli procesor prawie cały czas poprawnie odgaduje gałąź). Więc to jest prawdopodobnie lepsze.
dave
@KarstenR. Masz rację! Poprawiłem formułę, teraz działa dobrze (ale wymaga jeszcze dwóch odejmowań).
Stefan Reich
To prawda @dave
Stefan Reich