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

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

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 ).

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

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.

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.

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 .

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łę.)