Как я могу проверить, приведет ли умножение двух чисел в Java к переполнению?
-
11-09-2019 - |
Вопрос
Я хочу обработать особый случай, когда умножение двух чисел вызывает переполнение.Код выглядит примерно так:
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 8 есть Math.multiplyExact
, Math.addExact
и т. д.для целых и длинных.Они бросают неконтролируемый ArithmeticException
при переполнении.
Другие советы
Если a
и b
оба положительны, то вы можете использовать:
if (a != 0 && b > Long.MAX_VALUE / a) {
// Overflow
}
Если вам нужно иметь дело как с положительными, так и с отрицательными числами, тогда все сложнее:
long maximum = Long.signum(a) == Long.signum(b) ? Long.MAX_VALUE : Long.MIN_VALUE;
if (a != 0 && (b > 0 && b > maximum / a ||
b < 0 && b < maximum / a))
{
// Overflow
}
Чтобы проверить это, я составил небольшую таблицу, притворяясь, что переполнение происходит при -10 или +10:
a = 5 b = 2 2 > 10 / 5
a = 2 b = 5 5 > 10 / 2
a = -5 b = 2 2 > -10 / -5
a = -2 b = 5 5 > -10 / -2
a = 5 b = -2 -2 < -10 / 5
a = 2 b = -5 -5 < -10 / 2
a = -5 b = -2 -2 < 10 / -5
a = -2 b = -5 -5 < 10 / -2
Существуют библиотеки Java, которые обеспечивают безопасные арифметические операции и проверяют длинные переполнения/недополнения.Например, Гуава LongMath.checkedMultiply(длинный a, длинный b) возвращает продукт a
и b
, при условии, что он не переполняется и выбрасывает ArithmeticException
если a * b
переполнение в подписанном long
арифметика.
Вместо этого вы можете использовать java.math.BigInteger и проверить размер результата (код не проверялся):
BigInteger bigC = BigInteger.valueOf(a) * multiply(BigInteger.valueOf(b));
if(bigC.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) > 0) {
c = Long.MAX_VALUE;
} else {
c = bigC.longValue()
}
Используйте логарифмы, чтобы проверить размер результата.
Есть ли в Java что-то вроде int.MaxValue?Если да, то попробуйте
if (b != 0 && Math.abs(a) > Math.abs(Long.MAX_VALUE / b))
{
// it will overflow
}
редактировать:видел Long.MAX_VALUE под вопросом
Украдено у jruby
long result = a * b;
if (a != 0 && result / a != b) {
// overflow
}
ОБНОВЛЯТЬ:Этот код короткий и работает хорошо;однако это не удается для a = -1, b = Long.MIN_VALUE.
Одно из возможных улучшений:
long result = a * b;
if( (Math.signum(a) * Math.signum(b) != Math.signum(result)) ||
(a != 0L && result / a != b)) {
// overflow
}
Обратите внимание, что при этом будут обнаружены некоторые переполнения без какого-либо деления.
Вот самый простой способ, который я могу придумать
int a = 20;
long b = 30;
long c = a * b;
if(c / b == a) {
// Everything fine.....no overflow
} else {
// Overflow case, because in case of overflow "c/b" can't equal "a"
}
Я не уверен, почему никто не смотрит на такое решение, как:
if (Long.MAX_VALUE/a > b) {
// overflows
}
Выберите большее из двух чисел.
Я хотел бы опираться на ответ Джона Кугельмана, не заменяя его, редактируя его напрямую.Это работает для его тестового примера (MIN_VALUE = -10
, MAX_VALUE = 10
) из-за симметрии MIN_VALUE == -MAX_VALUE
, что не относится к целым числам с дополнением до двух.В действительности, MIN_VALUE == -MAX_VALUE - 1
.
scala> (java.lang.Integer.MIN_VALUE, java.lang.Integer.MAX_VALUE)
res0: (Int, Int) = (-2147483648,2147483647)
scala> (java.lang.Long.MIN_VALUE, java.lang.Long.MAX_VALUE)
res1: (Long, Long) = (-9223372036854775808,9223372036854775807)
Применительно к истинному MIN_VALUE
и MAX_VALUE
, ответ Джона Кугельмана приводит к случаю переполнения, когда a == -1
и b ==
что-нибудь еще (пункт, впервые поднятый Кайлом).Вот способ исправить это:
long maximum = Long.signum(a) == Long.signum(b) ? Long.MAX_VALUE : Long.MIN_VALUE;
if ((a == -1 && b == Long.MIN_VALUE) ||
(a != -1 && a != 0 && ((b > 0 && b > maximum / a) ||
(b < 0 && b < maximum / a))))
{
// Overflow
}
Это не общее решение для любого MIN_VALUE
и MAX_VALUE
, но это общее для Java Long
и Integer
и любое значение a
и b
.
Может быть:
if(b!= 0 && a * b / b != a) //overflow
Не уверен насчет этого «решения».
Редактировать:Добавлен b != 0.
Прежде чем проголосовать против:a*b/b не будет оптимизирован.Это будет ошибка компилятора.Я до сих пор не вижу случая, когда ошибку переполнения можно было бы замаскировать.
возможно, это вам поможет:
/**
* @throws ArithmeticException on integer overflow
*/
static long multiply(long a, long b) {
double c = (double) a * b;
long d = a * b;
if ((long) c != d) {
throw new ArithmeticException("int overflow");
} else {
return d;
}
}
Как уже отмечалось, в Java 8 есть методы Math.xxxExact, которые выдают исключения при переполнении.
Если вы не используете Java 8 для своего проекта, вы все равно можете «позаимствовать» их реализации, которые довольно компактны.
Вот несколько ссылок на эти реализации на стороннем веб-сайте, нет гарантии, что они останутся действительными, но в любом случае у вас должна быть возможность зайти в исходный код JDK и посмотреть, как они творят чудеса внутри java.lang.Math
сорт.
Math.multiplyExact(long, long)
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/lang/Math.java?av=f#882
Math.addExact
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/lang/Math.java?av=f#805
и т. д. и т. д.
c/c++ (длинный * длинный):
const int64_ w = (int64_) a * (int64_) b;
if ((long) (w >> sizeof(long) * 8) != (long) w >> (sizeof(long) * 8 - 1))
// overflow
java (int * int, извините, int64 в java я не нашел):
const long w = (long) a * (long) b;
int bits = 32; // int is 32bits in java
if ( (int) (w >> bits) != (int) (w >> (bits - 1))) {
// overflow
}
1.сохраните результат крупным шрифтом (int*int поместите результат в long, long*long поместите в int64)
2.cmp результат >> биты и результат >> (биты - 1)