¿La mejor manera de hacer que el módulo de Java se comporte como debería con números negativos?

103

En java cuando lo hagas

a % b

Si a es negativo, devolverá un resultado negativo, en lugar de ajustarse a b como debería. ¿Cuál es la mejor forma de solucionar este problema? La única forma en que puedo pensar es

a < 0 ? b + a : a % b
fingir
fuente
12
No hay un comportamiento de módulo "correcto" cuando se trata de números negativos: muchos idiomas lo hacen de esta manera, muchos idiomas lo hacen de manera diferente y algunos idiomas hacen algo completamente diferente. Al menos los dos primeros tienen sus pros y sus contras.
4
esto es extraño para mí. Pensé que solo debería devolver negativo si b es negativo.
Fent
2
es. pero el título de esa pregunta debería cambiarse de nombre. No haría clic en esa pregunta si estuviera buscando esta porque ya sé cómo funciona el módulo Java.
Fent
4
Simplemente lo renombré a eso de "¿Por qué -13% 64 = 51?", Que nunca en un millón de años sería algo en lo que alguien buscaría. Así que el título de esta pregunta es mucho mejor y se puede buscar mucho más en palabras clave como módulo, negativo, cálculo, números.
Erick Robertson

Respuestas:

144

Se comporta como debería a% b = a - a / b * b; es decir, es el resto.

Puedes hacer (a% b + b)% b


Esta expresión funciona porque (a % b)es necesariamente menor que b, sin importar si aes positivo o negativo. La suma bse ocupa de los valores negativos de a, ya que (a % b)es un valor negativo entre -by 0, (a % b + b)es necesariamente menor que by positivo. El último módulo está ahí en caso de que afuera positivo al principio, ya que si aes positivo (a % b + b)se volvería más grande que b. Por lo tanto, lo (a % b + b) % bconvierte en más pequeño que bnuevamente (y no afecta los avalores negativos ).

Peter Lawrey
fuente
3
esto funciona mejor gracias. y también funciona para números negativos que son mucho más grandes que b.
Fent
6
Funciona porque el resultado de (a % b)es necesariamente menor que b(no importa si aes positivo o negativo), la suma bse encarga de los valores negativos de a, ya que (a % b)es menor que by menor que 0, (a % b + b)es necesariamente menor que by positivo. El último módulo está ahí en caso de que afuera positivo para empezar, ya que si aes positivo (a % b + b)se volvería más grande que b. Por lo tanto, lo (a % b + b) % bconvierte en más pequeño que bnuevamente (y no afecta los avalores negativos ).
ethanfar
1
@eitanfar He incluido su excelente explicación en la respuesta (con una pequeña corrección para a < 0, tal vez podría echar un vistazo)
Maarten Bodewes
5
Acabo de ver esto comentado sobre otra pregunta sobre el mismo tema; Vale la pena mencionar que (a % b + b) % bse desglosa para valores muy grandes de ay b. Por ejemplo, usar a = Integer.MAX_VALUE - 1y b = Integer.MAX_VALUEdará -3como resultado, que es un número negativo, que es lo que quería evitar.
Thorbear
2
@Mikepote usando un whilesería más lento si realmente lo necesita, excepto que solo necesita un, ifen cuyo caso es más rápido.
Peter Lawrey
92

A partir de Java 8, puede usar Math.floorMod (int x, int y) y Math.floorMod (long x, long y) . Ambos métodos arrojan los mismos resultados que la respuesta de Peter.

Math.floorMod( 2,  3) =  2
Math.floorMod(-2,  3) =  1
Math.floorMod( 2, -3) = -1
Math.floorMod(-2, -3) = -2
John Krueger
fuente
1
mejor respuesta para Java 8+
Charney Kaye
Genial, no sabía nada de eso. Java 8 solucionó definitivamente algunos PITA.
Franz D.
4
Buen camino. Pero, por desgracia no funciona con floato doubleargumentos. El operador binario Mod ( %) también funciona con operandos floaty double.
Mir-Ismaili
11

Para aquellos que aún no usan (o no pueden usar) Java 8, Guava vino al rescate con IntMath.mod () , disponible desde Guava 11.0.

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

Una advertencia: a diferencia de Math.floorMod () de Java 8, el divisor (el segundo parámetro) no puede ser negativo.

Ibrahim Arief
fuente
7

En teoría de números, el resultado siempre es positivo. Supongo que este no es siempre el caso en los lenguajes informáticos porque no todos los programadores son matemáticos. Mis dos centavos, lo consideraría un defecto de diseño del lenguaje, pero no puedes cambiarlo ahora.

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

porque 180 * (-1) + 176 = -4 lo mismo que 180 * 0 + 176 = 176

Usando el ejemplo del reloj aquí, http://mathworld.wolfram.com/Congruence.html , no diría que duration_of_time mod cycle_length es -45 minutos, diría que 15 minutos, aunque ambas respuestas satisfacen la ecuación base.

Chris Golledge
fuente
1
En teoría de números no siempre es positivo ... Se clasifican en clases de congruencia. Eres libre de elegir cualquier candidato de esa clase para tus propósitos de notación, pero la idea es que se asigne a toda esa clase, y si el uso de otro candidato específico hace que un determinado problema sea significativamente más simple (elegir en -1lugar de, n-1por ejemplo) entonces hágalo.
BeUndead
2

Java 8 tiene Math.floorMod, pero es muy lento (su implementación tiene múltiples divisiones, multiplicaciones y un condicional). Sin embargo, es posible que la JVM tenga un código auxiliar optimizado intrínseco, lo que lo aceleraría significativamente.

La forma más rápida de hacer esto sin floorModes como algunas otras respuestas aquí, pero sin ramas condicionales y solo una %operación lenta .

Suponiendo que n es positivo y x puede ser cualquier cosa:

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;

Los resultados cuando n = 3:

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

Si solo necesita una distribución uniforme entre 0y n-1y no el operador de mod exacto, y xlos suyos no se agrupan cerca 0, lo siguiente será aún más rápido, ya que hay más paralelismo a nivel de instrucción y el %cálculo lento ocurrirá en paralelo con el otro partes ya que no dependen de su resultado.

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

Los resultados de lo anterior con 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

Si la entrada es aleatoria en el rango completo de un int, la distribución de ambas soluciones será la misma. Si los grupos de entrada se acercan a cero, habrá muy pocos resultados n - 1en la última solución.

Scott Carey
fuente
1

Aquí hay una alternativa:

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

Esto podría ser más rápido o no que la otra fórmula [(a% b + b)% b]. A diferencia de la otra fórmula, contiene una rama, pero usa una operación de módulo menos. Probablemente sea una victoria si la computadora puede predecir un <0 correctamente.

(Editar: se corrigió la fórmula).

Stefan Reich
fuente
1
Pero la operación de módulo requiere una división que podría ser incluso más lenta (especialmente si el procesador adivina la rama correctamente casi todo el tiempo). Entonces esto es posiblemente mejor.
dave
@KarstenR. ¡Tienes razón! Arreglé la fórmula, ahora funciona bien (pero necesita dos restas más).
Stefan Reich
Eso es cierto @dave
Stefan Reich