Melhor maneira de fazer o módulo do Java se comportar como deveria com números negativos?

103

Em java quando você faz

a % b

Se a for negativo, ele retornará um resultado negativo, em vez de voltar para b como deveria. Qual é a melhor maneira de consertar isso? A única maneira de pensar é

a < 0 ? b + a : a % b
fent
fonte
12
Não existe um comportamento de módulo "correto" ao lidar com números negativos - muitas linguagens fazem isso dessa forma, muitas linguagens fazem de forma diferente e algumas linguagens fazem algo completamente diferente. Pelo menos os dois primeiros têm seus prós e contras.
4
isso é estranho para mim. Achei que só deveria retornar negativo se b for negativo.
fentou de
1
possível duplicata de Como o java faz cálculos de módulo com números negativos?
Erick Robertson
2
isto é. mas o título dessa pergunta deve ser renomeado. Eu não clicaria nessa pergunta se estivesse procurando por este porque já sei como funciona o módulo java.
fento de
4
Acabei de renomeá-lo de "Por que -13% 64 = 51?", Que nunca, em um milhão de anos, seria algo que alguém pesquisaria. Portanto, o título da pergunta é muito melhor e muito mais pesquisável em palavras-chave como módulo, negativo, cálculo, números.
Erick Robertson

Respostas:

144

Ele se comporta como deveria a% b = a - a / b * b; ou seja, é o restante.

Você pode fazer (a% b + b)% b


Esta expressão funciona como o resultado de (a % b)é necessariamente menor que b, não importa se aé positivo ou negativo. Adicionar bcuida dos valores negativos de a, já que (a % b)é um valor negativo entre -be 0, (a % b + b)é necessariamente menor que be positivo. O último módulo está lá caso afosse positivo para começar, pois se afosse positivo (a % b + b)se tornaria maior que b. Portanto, o (a % b + b) % btransforma em menor do que bnovamente (e não afeta os avalores negativos ).

Peter Lawrey
fonte
3
isso funciona melhor, obrigado. e funciona com números negativos muito maiores do que b também.
fentou de
6
Funciona porque o resultado de (a % b)é necessariamente menor que b(não importa se aé positivo ou negativo), a adição bcuida dos valores negativos de a, pois (a % b)é menor que be menor que 0, (a % b + b)é necessariamente menor que be positivo. O último módulo está lá caso afosse positivo para começar, pois se afosse positivo (a % b + b)se tornaria maior que b. Portanto, o (a % b + b) % btransforma em menor do que bnovamente (e não afeta os avalores negativos ).
ethanfar
1
@eitanfar Eu incluí sua explicação excelente na resposta (com uma pequena correção para a < 0, talvez você pudesse dar uma olhada)
Maarten Bodewes
5
Acabei de ver isso comentado em outra questão referente ao mesmo assunto; Pode valer a pena mencionar que se (a % b + b) % bdivide para valores muito grandes de ae b. Por exemplo, usar a = Integer.MAX_VALUE - 1e b = Integer.MAX_VALUEdará -3como resultado, que é um número negativo, que é o que você queria evitar.
Thorbear,
2
@Mikepote usando a whileseria mais lento se você realmente precisar, exceto que você só precisa de um if, caso em que é realmente mais rápido.
Peter Lawrey
92

A partir do Java 8, você pode usar Math.floorMod (int x, int y) e Math.floorMod (long x, long y) . Ambos os métodos retornam os mesmos resultados da resposta de Peter.

Math.floorMod( 2,  3) =  2
Math.floorMod(-2,  3) =  1
Math.floorMod( 2, -3) = -1
Math.floorMod(-2, -3) = -2
John Krueger
fonte
1
melhor resposta para Java 8+
Charney Kaye
Legal, não sabia sobre esse. Java 8 corrigiu definitivamente alguns PITAs.
Franz D.
4
Bom caminho. Mas infelizmente não funciona com floatou doubleargumentos. O operador binário mod ( %) também funciona com operandos floate double.
Mir-Ismaili
11

Para aqueles que ainda não usam (ou não podem usar) o Java 8, o Guava veio ao resgate com IntMath.mod () , disponível desde o Guava 11.0.

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

Uma advertência: ao contrário do Math.floorMod () do Java 8, o divisor (o segundo parâmetro) não pode ser negativo.

Ibrahim Arief
fonte
7

Na teoria dos números, o resultado é sempre positivo. Eu diria que nem sempre é o caso em linguagens de computador, porque nem todos os programadores são matemáticos. Meus dois centavos, eu consideraria um defeito de design da linguagem, mas você não pode mudar isso agora.

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

porque 180 * (-1) + 176 = -4 o mesmo que 180 * 0 + 176 = 176

Usando o exemplo do relógio aqui, http://mathworld.wolfram.com/Congruence.html você não diria duration_of_time mod cycle_length é -45 minutos, você diria 15 minutos, embora ambas as respostas satisfaçam a equação básica.

Chris Golledge
fonte
1
Na teoria dos números nem sempre é positivo ... Eles se enquadram nas classes de congruência. Você é livre para escolher qualquer candidato daquela classe para seus propósitos de notação, mas a ideia é que ele mapeie para toda aquela classe, e se usar um outro candidato específico torna um certo problema significativamente mais simples (escolha em -1vez de, n-1por exemplo) então faça isso.
BeUndead de
2

O Java 8 tem Math.floorMod, mas é muito lento (sua implementação tem várias divisões, multiplicações e uma condicional). É possível que a JVM tenha um stub otimizado intrínseco para ela, no entanto, o que a aceleraria significativamente.

A maneira mais rápida de fazer isso sem floorModé como algumas outras respostas aqui, mas sem ramificações condicionais e apenas uma %operação lenta .

Supondo que n seja positivo, e x pode ser qualquer coisa:

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;

Os resultados quando n = 3:

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

Se você só precisa de uma distribuição uniforme entre 0e n-1e não o operador mod exato, e seu xnão agrupa próximo 0, o seguinte será ainda mais rápido, pois há mais paralelismo de nível de instrução e o %cálculo lento ocorrerá em paralelo com o outro partes, pois não dependem de seu resultado.

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

Os resultados para o acima com 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

Se a entrada for aleatória em todo o intervalo de um int, a distribuição das duas soluções será a mesma. Se os clusters de entrada próximos de zero, haverá poucos resultados na n - 1última solução.

Scott Carey
fonte
1

Aqui está uma alternativa:

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

Isso pode ou não ser mais rápido do que a outra fórmula [(a% b + b)% b]. Ao contrário da outra fórmula, ela contém uma ramificação, mas usa uma operação de módulo a menos. Provavelmente uma vitória se o computador puder prever um <0 corretamente.

(Editar: corrigida a fórmula.)

Stefan Reich
fonte
1
Mas a operação do módulo requer uma divisão que pode ser ainda mais lenta (especialmente se o processador adivinhar o branch corretamente quase o tempo todo). Então isso é possivelmente melhor.
Dave
@KarstenR. Você está certo! Corrigi a fórmula, agora funciona bem (mas precisa de mais duas subtrações).
Stefan Reich
Isso é verdade @dave
Stefan Reich