Как я могу проверить, не вызовет ли умножение двух чисел в Java переполнение?

101

Я хочу рассмотреть особый случай, когда умножение двух чисел приводит к переполнению. Код выглядит примерно так:

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всегда неотрицательны в моем сценарии.

Стив Маклеод
источник
7
Жаль, что Java не предоставляет косвенный доступ к флагу переполнения ЦП , как это сделано в C # .
Дрю Ноукс,

Ответы:

92

В Java 8 есть Math.multiplyExactи Math.addExactт.д. для int и long. Они вызывают неконтролируемое ArithmeticExceptionпереполнение.

Bcoughlan
источник
59

Если 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
Джон Кугельман
источник
Я должен упомянуть, что в моем сценарии a и b всегда неотрицательны, что несколько упростило бы этот подход.
Steve McLeod
3
Я думаю, что это может потерпеть неудачу в случае: a = -1 и b = 10. Выражение максимум / a приводит к Integer.MIN_VALUE и обнаруживает переполнение, когда его не было,
Кайл
Это действительно здорово. Для тех , кому интересно, почему это работает в том , что для целого числа n, n > xтакое же , как n > floor(x). Для положительных целых чисел деление делает неявный пол. (Для отрицательных чисел вместо этого округляется)
Томас Але
Для решения проблемы a = -1и b = 10проблемы, увидеть мой ответ ниже.
Джим Пиварски
17

Существуют библиотеки Java, которые обеспечивают безопасные арифметические операции, которые проверяют длительное переполнение / потеря значимости. Например, LongMath.checkedMultiply (long a, long b) Guava возвращает произведение aи b, при условии, что оно не переполняется, и выбрасывает ArithmeticExceptionпри a * bпереполнении в знаковой longарифметике.

перепрограммист
источник
4
Это лучший ответ - используйте библиотеку, которая была реализована людьми, которые действительно разбираются в машинной арифметике на Java, и которая была протестирована множеством людей. Не пытайтесь написать свой собственный или использовать какой-либо недоработанный непроверенный код, опубликованный в других ответах!
Rich
@Enerccio - я не понимаю ваш комментарий. Вы хотите сказать, что Guava не будет работать на всех системах? Могу заверить вас, что он будет работать везде, где работает Java. Вы хотите сказать, что повторное использование кода - плохая идея? Я не согласен, если это так.
Rich
2
@Rich Я говорю, что включать огромную библиотеку, чтобы вы могли использовать одну функцию, - плохая идея.
Enerccio
Зачем? Если вы пишете большое приложение, например, для бизнеса, то дополнительный JAR в пути к классам не причинит никакого вреда, а в Guava есть много очень полезного кода. Гораздо лучше повторно использовать их тщательно протестированный код, чем пытаться написать свою собственную версию того же самого (что, я полагаю, вы рекомендуете?). Если вы пишете в среде, где дополнительный JAR будет очень дорогим (где? Встроенная Java?), То, возможно, вам следует извлечь только этот класс из Guava. Лучше ли копировать непроверенный ответ из StackOverflow, чем копировать тщательно проверенный код Guava?
Rich
Разве создание исключения не является излишним для чего-то, с чем может справиться условное if-then?
victtim
6

Вместо этого вы можете использовать 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()
}
Ульф Линдбек
источник
7
я считаю это решение довольно медленным
nothrow 01
Хотя, вероятно, это лучший способ сделать это. Я предположил, что это числовое приложение, поэтому я не рекомендовал его сразу, но это действительно, вероятно, лучший способ решить эту проблему.
Стефан Кендалл
2
Я не уверен, что вы можете использовать оператор '>' с BigInteger. следует использовать метод compareTo.
Пьер
изменено на compareTo, и скорость может иметь значение, а может и не иметь значения, в зависимости от обстоятельств, в которых будет использоваться код.
Ульф Линдбек 01
5

Используйте логарифмы, чтобы проверить размер результата.

Знак высокой эффективности
источник
ты имеешь ввиду ceil(log(a)) + ceil(log(b)) > log(Long.MAX):?
Thomas Jung
1
Я проверил это. Для малых значений он на 20% быстрее, чем BigInteger, а для значений, близких к MAX, он почти такой же (на 5% быстрее). Код Йоссариана самый быстрый (на 95% и 75% быстрее, чем BigInteger).
Thomas Jung
Я скорее подозреваю, что в некоторых случаях он может выйти из строя.
Том Хотин - tackline
Помните, что целочисленный журнал фактически просто подсчитывает количество ведущих нулей, и вы можете оптимизировать некоторые распространенные случаи (например, if ((a | b) & 0xffffffff00000000L) == 0) вы знаете, что вы в безопасности). С другой стороны, если вы не сможете добиться оптимизации до 30/40 тактовых циклов для наиболее распространенных случаев, метод Джона Кугельмана, вероятно, будет работать лучше (целочисленное деление составляет примерно 2 бита / тактовый цикл, насколько я помню).
Нил Коффи
PS Извините, я думаю, мне нужен дополнительный бит, установленный в маске AND (0xffffffff80000000L) - это немного поздно, но вы поняли идею ...
Нил Коффи
4

Есть ли в Java что-то вроде int.MaxValue? Если да, то попробуйте

if (b != 0 && Math.abs(a) > Math.abs(Long.MAX_VALUE / b))
{
 // it will overflow
}

изменить: видел Long.MAX_VALUE в вопросе

ничто
источник
Я не downvote , но Math.Abs(a)не работает , если aесть Long.MIN_VALUE.
Джон Кугельман 01
@John - a и b> 0. Я думаю, что подход Йоссариана (b! = 0 && a> Long.MAX_VALUE / b) является лучшим.
Thomas Jung
@Thomas, a и b> = 0, то есть неотрицательны.
Steve McLeod
2
Верно, но в этом случае Абс не нужен. Если разрешены отрицательные числа, то это не удается хотя бы в одном пограничном случае. Это все, что я говорю, просто придираюсь.
Джон Кугельман 01
в Java вы должны использовать Math.abs, а не Math.Abs ​​(C # парень?)
dfa
4

Вот самый простой способ, который я могу придумать

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"
}
Нарен
источник
3

Украдено из джруби

    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
}

Обратите внимание, что это перехватит некоторые переполнения без какого-либо деления.

Роджердпак
источник
Вы можете использовать Long.signum вместо Math.signum
aditsu quit, потому что SE is EVIL
3

Как уже отмечалось, в 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#l925

Math.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.

StFS
источник
2

Я не уверен, почему никто не смотрит на такое решение, как:

if (Long.MAX_VALUE/a > b) {
     // overflows
} 

Выберите большее из двух чисел.

fastcodejava
источник
2
Я не думаю, что это имеет aзначение, больше или меньше?
Thomas Ahle
2

Я хотел бы опираться на ответ Джона Кугельмана, не заменяя его, редактируя его напрямую. Это работает для его тестового примера ( 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ответ Джона Кугельмана дает случай переполнения when 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.

Джим Пиварски
источник
Я просто подумал, что это излишне усложнит его, поскольку это решение работает только в том случае MIN_VALUE = -MAX_VALUE - 1, а не в любом другом случае (включая ваш пример тестового примера). Придется многое изменить.
Джим Пиварски
1
По причинам, выходящим за рамки потребностей оригинального плаката; для людей вроде меня, которые нашли эту страницу, потому что им нужно было решение для более общего случая (обработка отрицательных чисел, а не строго Java 8). Фактически, поскольку это решение не включает никаких функций, кроме чистой арифметики и логики, его также можно использовать для C или других языков.
Джим Пиварски
1

Может быть:

if(b!= 0 && a * b / b != a) //overflow

Не уверен в этом «решении».

Изменить: добавлен b! = 0.

Перед тем, как вы проголосуете против : a * b / b не будут оптимизированы. Это будет ошибка компилятора. Я до сих пор не вижу случая, чтобы ошибку переполнения можно было замаскировать.

Томас Юнг
источник
Также не работает, когда переполнение вызывает идеальный цикл.
Стефан Кендалл
У вас есть пример того, что вы имели в виду?
Thomas Jung
Просто написал небольшой тест: использование BigInteger в 6 раз медленнее, чем использование этого подхода к делению. Поэтому я полагаю, что дополнительные проверки для угловых случаев стоят того, что касается производительности.
mhaller 01
Не знаю много о компиляторах java, но выражение вроде a * b / b, вероятно, будет оптимизировано только aдля многих других контекстов.
SingleNegationElimination
TokenMacGuy - его нельзя так оптимизировать, если есть опасность переполнения.
Том Хотин - tackline
1

возможно это поможет вам:

/**
 * @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;
    }
}
DFA
источник
Не поможет, как один из операндов long.
Том Хотин - tackline
1
Вы даже это тестировали? Для любых больших, но не переполняющихся значений a и b это не удастся из-за ошибок округления в двойной версии умножения (попробуйте, например, 123456789123L и 74709314L). Если вы не разбираетесь в машинной арифметике, угадать ответ на такой точный вопрос хуже, чем не отвечать, поскольку это введет людей в заблуждение.
Rich
-1

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)

Сюань
источник