Лучший способ заставить модуль Java вести себя так, как должен, с отрицательными числами?

103

В java, когда вы делаете

a % b

Если a отрицательно, он вернет отрицательный результат, вместо того, чтобы оборачиваться до b, как должно. Как лучше всего это исправить? Я могу думать только так

a < 0 ? b + a : a % b
фент
источник
12
При работе с отрицательными числами не существует «правильного» модульного поведения - многие языки делают это так, многие языки делают это по-другому, а некоторые языки делают что-то совершенно другое. По крайней мере, у первых двух есть свои плюсы и минусы.
4
для меня это просто странно. Я думал, что он должен возвращать отрицательный результат, только если b отрицательно.
fent
2
это. но название этого вопроса следует переименовать. Я бы не стал нажимать на этот вопрос, если бы искал его, потому что я уже знаю, как работает модуль java.
fent
4
Я просто переименовал его в «Почему -13% 64 = 51?», Который никогда и за миллион лет не стал бы чем-то, что можно было бы найти. Таким образом, заголовок этого вопроса намного лучше, и его гораздо удобнее искать по таким ключевым словам, как модуль, минус, расчет, числа.
Эрик Робертсон

Ответы:

144

Он ведет себя так, как должен a% b = a - a / b * b; т.е. это остаток.

Вы можете сделать (a% b + b)% b


Это выражение работает, поскольку результат (a % b)обязательно ниже чем b, независимо от того a, положительный он или отрицательный. Добавление bзаботится о отрицательных значениях a, так как (a % b)имеет отрицательное значение между -bи 0, (a % b + b)обязательно ниже bи положительный результат . Последний модуль присутствует в случае, если aс самого начала было положительным, так как если aположительное значение (a % b + b)станет больше, чем b. Следовательно, (a % b + b) % bпревращает его в меньшее, чем bснова (и не влияет на отрицательные aзначения).

Питер Лоури
источник
3
это работает лучше, спасибо. и это работает и для отрицательных чисел, которые намного больше, чем b.
fent
6
Это работает, поскольку результат (a % b)обязательно меньше чем b(независимо от того a, положительный он или отрицательный), добавление bучитывает отрицательные значения a, поскольку (a % b)меньше bи меньше чем 0, (a % b + b)обязательно меньше bи положительно. Последний модуль присутствует в случае, если aс самого начала было положительным, так как если aположительное значение (a % b + b)станет больше, чем b. Следовательно, (a % b + b) % bпревращает его в меньшее, чем bснова (и не влияет на отрицательные aзначения).
ethanfar
1
@eitanfar Я включил ваше превосходное объяснение в ответ (с небольшими поправками a < 0, может быть, вы могли бы взглянуть)
Maarten Bodewes
5
Я только что видел этот комментарий по другому вопросу, касающемуся той же темы; Возможно, стоит упомянуть, что он (a % b + b) % bраспадается на очень большие значения aи b. Например, использование a = Integer.MAX_VALUE - 1и b = Integer.MAX_VALUEдаст в -3качестве результата отрицательное число, чего вы хотели избежать.
Thorbear
2
@Mikepote с использованием a whileбудет медленнее, если он вам действительно нужен, за исключением того, что вам нужен только, и ifв этом случае он действительно быстрее.
Питер Лоури 08
92

Начиная с Java 8, вы можете использовать Math.floorMod (int x, int y) и Math.floorMod (long x, long y) . Оба эти метода возвращают те же результаты, что и ответ Питера.

Math.floorMod( 2,  3) =  2
Math.floorMod(-2,  3) =  1
Math.floorMod( 2, -3) = -1
Math.floorMod(-2, -3) = -2
Джон Крюгер
источник
1
лучший ответ для Java 8+
Чарни Кэй
Круто, не знал об этом. В Java 8 окончательно исправлены некоторые ошибки PITA.
Franz D.
4
Хороший способ. Но , к сожалению , не работает с floatили doubleаргументами. Mod бинарный оператор ( %) также работает с floatи doubleоперанды.
Мир-Исмаили
11

Для тех, кто еще не использует (или не может использовать) Java 8, Guava пришел на помощь с IntMath.mod () , доступным с Guava 11.0.

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

Одно предостережение: в отличие от Java 8 Math.floorMod (), делитель (второй параметр) не может быть отрицательным.

Ибрагим Ариф
источник
7

В теории чисел результат всегда положительный. Я предполагаю, что это не всегда так в компьютерных языках, потому что не все программисты являются математиками. Мои два цента, я бы посчитал это конструктивным дефектом языка, но вы не можете его сейчас изменить.

= МОД (-4,180) = 176 = МОД (176, 180) = 176

потому что 180 * (-1) + 176 = -4 то же самое, что 180 * 0 + 176 = 176

Используя пример часов здесь, http://mathworld.wolfram.com/Congruence.html, вы бы не сказали, что duration_of_time mod cycle_length составляет -45 минут, вы бы сказали 15 минут, даже если оба ответа удовлетворяют базовому уравнению.

Крис Голледж
источник
1
В теории чисел это не всегда положительно ... Они попадают в классы конгруэнтности. Вы можете выбрать любого кандидата из этого класса для своих целей нотации, но идея состоит в том, что он отображается на весь этот класс, и если использование конкретного другого кандидата из него значительно упрощает определенную проблему (выбор -1вместо, n-1например) тогда займись этим.
BeUndead
2

В Java 8 есть Math.floorMod, но он очень медленный (в его реализации есть несколько делений, умножений и условное выражение). Вполне возможно, что JVM имеет внутреннюю оптимизированную заглушку для нее, однако, что значительно ускорит ее.

Самый быстрый способ обойтись без этого floorMod- как и некоторые другие ответы здесь, но без условных переходов и только с одной медленной %операцией.

Предполагая, что n положительно, а x может быть любым:

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;

Результаты при n = 3:

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

Если вам нужно только равномерное распределение между 0и, n-1а не точным оператором мода, и ваши операторы xне сгруппированы рядом 0, следующее будет еще быстрее, так как параллелизм на уровне инструкций больше, и медленные %вычисления будут происходить параллельно с другим частей, поскольку они не зависят от его результата.

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

Результаты для вышеуказанного с 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

Если вход является случайным во всем диапазоне int, распределение обоих двух решений будет одинаковым. Если входные кластеры близки к нулю, n - 1в последнем решении будет слишком мало результатов .

Скотт Кэри
источник
1

Вот альтернатива:

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

Это может быть или не быть быстрее, чем другая формула [(a% b + b)% b]. В отличие от другой формулы, она содержит ветвь, но использует на одну операцию по модулю меньше. Вероятно, выигрыш, если компьютер сможет правильно предсказать <0.

(Изменить: исправлена ​​формула.)

Стефан Райх
источник
1
Но операция по модулю требует деления, которое может быть еще медленнее (особенно, если процессор почти все время правильно угадывает ветвь). Так что, возможно, лучше.
Дэйв
@KarstenR. Ты прав! Я исправил формулу, теперь она работает нормально (но нужно еще два вычитания).
Стефан Райх
Это правда @dave
Стефан Райх