Я хочу рассмотреть особый случай, когда умножение двух чисел приводит к переполнению. Код выглядит примерно так:
int a = 20;
long b = 30;
// if a or b are big enough, this result will silently overflow
long c = a * b;
Это упрощенная версия. В реальной программе a
и b
находятся в другом месте во время выполнения. Я хочу добиться примерно этого:
long c;
if (a * b will overflow) {
c = Long.MAX_VALUE;
} else {
c = a * b;
}
Как вы предлагаете мне лучше всего это кодировать?
Обновление: a
и b
всегда неотрицательны в моем сценарии.
java
math
long-integer
integer-overflow
Стив Маклеод
источник
источник
Ответы:
В Java 8 есть
Math.multiplyExact
иMath.addExact
т.д. для int и long. Они вызывают неконтролируемоеArithmeticException
переполнение.источник
Если
a
иb
оба положительны, вы можете использовать:Если вам нужно иметь дело как с положительными, так и с отрицательными числами, все сложнее:
Вот небольшая таблица, которую я собрал, чтобы проверить это, делая вид, что переполнение происходит при -10 или +10:
источник
n
,n > x
такое же , какn > floor(x)
. Для положительных целых чисел деление делает неявный пол. (Для отрицательных чисел вместо этого округляется)a = -1
иb = 10
проблемы, увидеть мой ответ ниже.Существуют библиотеки Java, которые обеспечивают безопасные арифметические операции, которые проверяют длительное переполнение / потеря значимости. Например, LongMath.checkedMultiply (long a, long b) Guava возвращает произведение
a
иb
, при условии, что оно не переполняется, и выбрасываетArithmeticException
приa * b
переполнении в знаковойlong
арифметике.источник
Вместо этого вы можете использовать java.math.BigInteger и проверить размер результата (код не тестировался):
источник
Используйте логарифмы, чтобы проверить размер результата.
источник
ceil(log(a)) + ceil(log(b)) > log(Long.MAX)
:?Есть ли в Java что-то вроде int.MaxValue? Если да, то попробуйте
изменить: видел Long.MAX_VALUE в вопросе
источник
Math.Abs(a)
не работает , еслиa
естьLong.MIN_VALUE
.Вот самый простой способ, который я могу придумать
источник
Украдено из джруби
ОБНОВЛЕНИЕ: этот код короткий и хорошо работает; однако он не выполняется для a = -1, b = Long.MIN_VALUE.
Одно возможное улучшение:
Обратите внимание, что это перехватит некоторые переполнения без какого-либо деления.
источник
Как уже отмечалось, в Java 8 есть методы Math.xxxExact, которые генерируют исключения при переполнении.
Если вы не используете Java 8 для своего проекта, вы все равно можете «позаимствовать» их реализации, которые довольно компактны.
Вот несколько ссылок на эти реализации в репозитории исходного кода JDK, нет гарантии, что они останутся действительными, но в любом случае вы должны иметь возможность загрузить исходный код JDK и посмотреть, как они творит чудеса внутри
java.lang.Math
класса.Math.multiplyExact(long, long)
http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/lang/Math.java#l925Math.addExact(long, long)
http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/lang/Math.java#l830и т. д. и т. д.
ОБНОВЛЕНО: отключены недействительные ссылки на сторонний веб-сайт на ссылки на репозитории Mercurial Open JDK.
источник
Я не уверен, почему никто не смотрит на такое решение, как:
Выберите большее из двух чисел.
источник
a
значение, больше или меньше?Я хотел бы опираться на ответ Джона Кугельмана, не заменяя его, редактируя его напрямую. Это работает для его тестового примера (
MIN_VALUE = -10
,MAX_VALUE = 10
) из-за симметрииMIN_VALUE == -MAX_VALUE
, которая не относится к целым числам с дополнением до двух. На самом делеMIN_VALUE == -MAX_VALUE - 1
.Применительно к истинному
MIN_VALUE
иMAX_VALUE
ответ Джона Кугельмана дает случай переполнения whena == -1
иb ==
что-либо еще (точка, впервые поднятая Кайлом). Вот способ исправить это:Это не общее решение для любого
MIN_VALUE
иMAX_VALUE
, но это является общим для Java - хLong
иInteger
и любое значениеa
иb
.источник
MIN_VALUE = -MAX_VALUE - 1
, а не в любом другом случае (включая ваш пример тестового примера). Придется многое изменить.Может быть:
Не уверен в этом «решении».
Изменить: добавлен b! = 0.
Перед тем, как вы проголосуете против : a * b / b не будут оптимизированы. Это будет ошибка компилятора. Я до сих пор не вижу случая, чтобы ошибку переполнения можно было замаскировать.
источник
a * b / b
, вероятно, будет оптимизировано толькоa
для многих других контекстов.возможно это поможет вам:
источник
long
.c / c ++ (длинный * длинный):
java (int * int, извините, я не нашел int64 в java):
1. сохранить результат в большом типе (int * int поместить результат в long, long * long положить в int64)
2. cmp результат >> биты и результат >> (биты - 1)
источник