Como posso verificar se a multiplicação de dois números em Java causará um estouro?

101

Quero lidar com o caso especial em que a multiplicação de dois números causa um estouro. O código é parecido com este:

int a = 20;
long b = 30;

// if a or b are big enough, this result will silently overflow
long c = a * b;

Essa é uma versão simplificada. No programa real ae bsão obtidos em outro lugar em tempo de execução. O que eu quero alcançar é algo assim:

long c;
if (a * b will overflow) {
    c = Long.MAX_VALUE;
} else {
    c = a * b;
}

Como você sugere que eu codifique melhor isso?

Update: ae bsão sempre não negativos no meu cenário.

Steve McLeod
fonte
6
É uma pena que o Java não forneça acesso indireto ao sinalizador de estouro da CPU , como é feito em C # .
Drew Noakes de

Respostas:

92

Java 8 tem Math.multiplyExact, Math.addExactetc. para ints e long. Estes lançam um ArithmeticExceptionestouro desmarcado .

Bcoughlan
fonte
59

Se ae bforem positivos, você pode usar:

if (a != 0 && b > Long.MAX_VALUE / a) {
    // Overflow
}

Se você precisa lidar com números positivos e negativos, é mais complicado:

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
}

Aqui está uma pequena mesa que criei para verificar isso, fingindo que o estouro acontece em -10 ou +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
John Kugelman
fonte
Devo mencionar que aeb são sempre não negativos em meu cenário, o que simplificaria um pouco essa abordagem.
Steve McLeod
3
Acho que isso pode falhar em um caso: a = -1 eb = 10. O resultado de expressão máxima / a em Integer.MIN_VALUE e detecta estouro quando não existia
Kyle
Isso é muito bom. Para quem está se perguntando, o motivo pelo qual isso funciona é que, para inteiro n, n > xé o mesmo que n > floor(x). Para números inteiros positivos, a divisão é um piso implícito. (Para números negativos, ele arredonda para cima)
Thomas Ahle
Para resolver o problema a = -1e b = 10, veja minha resposta abaixo.
Jim Pivarski
17

Existem bibliotecas Java que fornecem operações aritméticas seguras, que verificam longo estouro / estouro negativo. Por exemplo, LongMath.checkedMultiply (long a, long b) do Guava retorna o produto de ae b, desde que não estourou, e lança ArithmeticExceptionse a * bestourou na longaritmética assinada .

reprogramador
fonte
4
Esta é a melhor resposta - use uma biblioteca que foi implementada por pessoas que realmente entendem de aritmética de máquina em Java e que foi testada por muitas pessoas. Não tente escrever seu próprio código ou usar qualquer código não testado e incompleto postado nas outras respostas!
Rica
@Enerccio - Não entendi seu comentário. Você está dizendo que o Guava não funciona em todos os sistemas? Posso garantir que funcionará em qualquer lugar que o Java faça. Você está dizendo que reutilizar código é uma má ideia em geral? Eu discordo se sim.
Rico de
2
@Rich estou dizendo que incluir uma biblioteca enorme para que você possa usar uma função é uma má ideia.
Enerccio de
Por quê? Se você estiver escrevendo um grande aplicativo, por exemplo, para um negócio, um JAR extra no caminho de classe não causará nenhum dano e o Guava contém muitos códigos úteis. É muito melhor reutilizar seu código cuidadosamente testado do que tentar escrever sua própria versão do mesmo (o que presumo que seja o que você recomenda?). Se você está escrevendo em um ambiente onde um JAR extra vai ser muito caro (onde? Java embutido?), Talvez você deva extrair apenas esta classe do Guava. Copiar uma resposta não testada do StackOverflow é melhor do que copiar o código cuidadosamente testado do Guava?
Rico de
Não é um exagero lançar uma exceção para algo que um se-então condicional pode controlar?
victtim
6

Você pode usar java.math.BigInteger em vez disso e verificar o tamanho do resultado (não testei o código):

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()
}
Ulf Lindback
fonte
7
Acho
No entanto, é provavelmente a melhor maneira de fazer isso. Presumi que fosse um aplicativo numérico, por isso não o recomendei de imediato, mas essa realmente é provavelmente a melhor maneira de resolver o problema.
Stefan Kendall
2
Não tenho certeza se você pode usar o operador '>' com BigInteger. o método compareTo deve ser usado.
Pierre
alterado para compareTo, e a velocidade pode ser importante ou não, depende das circunstâncias em que o código será usado.
Ulf Lindback
5

Use logaritmos para verificar o tamanho do resultado.

Marca de alto desempenho
fonte
você quer dizer ceil(log(a)) + ceil(log(b)) > log(Long.MAX):?
Thomas Jung
1
Eu verifiquei. Para valores pequenos, é 20% mais rápido do que BigInteger e para valores próximos a MAX é quase o mesmo (5% mais rápido). O código de Yossarian é o mais rápido (95% e 75% mais rápido do que BigInteger).
Thomas Jung
Prefiro suspeitar que pode falhar em alguns casos.
Tom Hawtin - tackline em
Lembre-se de que um log de inteiros está contando apenas o número de zeros à esquerda, e você pode otimizar alguns casos comuns (por exemplo, se ((a | b) & 0xffffffff00000000L) == 0) você sabe que está seguro). Por outro lado, a menos que você consiga reduzir sua otimização para ciclos de clock de 30/40 para os casos mais comuns, o método de John Kugelman provavelmente terá um desempenho melhor (uma divisão inteira é de c. 2 bits / ciclo de clock, pelo que me lembro).
Neil Coffey
PS Sorr, acho que preciso de um conjunto extra de bits na máscara AND (0xffffffff80000000L) - é um pouco tarde, mas você entendeu ...
Neil Coffey
4

Java tem algo como int.MaxValue? Se sim, então tente

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

editar: visto Long.MAX_VALUE em questão

nothrow
fonte
Eu não fiz downvote, mas Math.Abs(a)não funciona se afor Long.MIN_VALUE.
John Kugelman
@John - aeb são> 0. Acho que a abordagem de Yossarian (b! = 0 && a> Long.MAX_VALUE / b) é a melhor.
Thomas Jung
@Thomas, aeb são> = 0, ou seja, não negativos.
Steve McLeod
2
Certo, mas nesse caso não há necessidade do Abs. Se números negativos forem permitidos, isso falhará para pelo menos um caso extremo. Isso é tudo que estou dizendo, apenas sendo minucioso.
John Kugelman
em Java, você deve usar Math.abs, não Math.Abs ​​(cara do C #?)
dfa
4

Aqui está a maneira mais simples que posso pensar

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"
}
Naren
fonte
3

Roubado de jruby

    long result = a * b;
    if (a != 0 && result / a != b) {
       // overflow
    }

ATUALIZAÇÃO: Este código é curto e funciona bem; no entanto, ele falha para a = -1, b = Long.MIN_VALUE.

Um possível aprimoramento:

long result = a * b;
if( (Math.signum(a) * Math.signum(b) != Math.signum(result)) || 
    (a != 0L && result / a != b)) {
    // overflow
}

Observe que isso irá capturar alguns overflows sem qualquer divisão.

rogerdpack
fonte
Você pode usar Long.signum em vez de Math.signum
aditsu quit porque SE é EVIL
3

Como foi apontado, o Java 8 possui métodos Math.xxxExact que lançam exceções no estouro.

Se você não estiver usando Java 8 para o seu projeto, ainda pode "pegar emprestado" suas implementações, que são bastante compactas.

Aqui estão alguns links para essas implementações no repositório de código-fonte JDK, nenhuma garantia se eles permanecerão válidos, mas em qualquer caso, você deve ser capaz de baixar o código-fonte JDK e ver como eles fazem sua mágica dentro da java.lang.Mathclasse.

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

etc etc.

ATUALIZADO: foram removidos links inválidos para sites de terceiros para links para os repositórios Mercurial do Open JDK.

StFS
fonte
2

Não sei por que ninguém está olhando para uma solução como:

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

Escolha a para ser o maior dos dois números.

fastcodejava
fonte
2
Eu não acho que importa se aé o maior ou o menor?
Thomas Ahle
2

Eu gostaria de desenvolver a resposta de John Kugelman sem substituí-la editando-a diretamente. Isso funciona para seu caso de teste ( MIN_VALUE = -10, MAX_VALUE = 10) por causa da simetria de MIN_VALUE == -MAX_VALUE, que não é o caso para inteiros de complemento de dois. Na realidade 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)

Quando aplicada ao verdadeiro MIN_VALUEe MAX_VALUE, a resposta de John Kugelman produz um caso de estouro quando a == -1e b ==qualquer outra coisa (ponto levantado pela primeira vez por Kyle). Esta é uma maneira de consertar:

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
}

Não é uma solução geral para qualquer MIN_VALUEe MAX_VALUE, mas é geral para Java de Longe Integere qualquer valor de ae b.

Jim Pivarski
fonte
Eu apenas pensei que iria complicar desnecessariamente, já que essa solução só funciona se MIN_VALUE = -MAX_VALUE - 1, não em qualquer outro caso (incluindo seu caso de teste de exemplo). Eu teria que mudar muito.
Jim Pivarski
1
Por razões além das necessidades do autor original; para pessoas como eu que encontraram esta página porque precisavam de uma solução para um caso mais geral (lidar com números negativos e não estritamente Java 8). Na verdade, como essa solução não envolve nenhuma função além da aritmética e lógica puras, ela também pode ser usada para C ou outras linguagens.
Jim Pivarski
1

Talvez:

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

Não tenho certeza sobre esta "solução".

Editar: Adicionado b! = 0.

Antes de fazer downvote : a * b / b não será otimizado. Isso seria um bug do compilador. Ainda não vejo um caso em que o bug de estouro possa ser mascarado.

Thomas Jung
fonte
Também falha quando o estouro causa um loop perfeito.
Stefan Kendall
Você tem um exemplo do que quis dizer?
Thomas Jung
Acabei de escrever um pequeno teste: Usar BigInteger é 6 vezes mais lento do que usar essa abordagem de divisão. Portanto, suponho que verificações adicionais para casos secundários valem a pena em termos de desempenho.
mhaller 01 de
Não sei muito sobre compiladores java, mas uma expressão como a * b / bprovavelmente será otimizada apenas apara muitos outros contextos.
SingleNegationElimination 01 de
TokenMacGuy - não pode ser otimizado assim se houver perigo de estouro.
Tom Hawtin - tackline em
1

talvez isso te ajude:

/**
 * @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
fonte
Não vai ajudar como um dos operandos long.
Tom Hawtin - tackline
1
Você ao menos testou isso? Para quaisquer valores grandes, mas não excessivos de a & b, isso falhará devido a erros de arredondamento na versão dupla da multiplicação (tente, por exemplo, 123456789123L e 74709314L). Se você não entende de aritmética de máquina, adivinhar uma resposta para esse tipo de pergunta precisa é pior do que não responder, pois pode enganar as pessoas.
Rica
-1

c / c ++ (longo * longo):

const int64_ w = (int64_) a * (int64_) b;    
if ((long) (w >> sizeof(long) * 8) != (long) w >> (sizeof(long) * 8 - 1))
    // overflow

java (int * int, desculpe, não encontrei int64 em 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. salve o resultado em tipo grande (int * int coloque o resultado em long, long * long coloque em int64)

2.cmp result >> bits e result >> (bits - 1)

xuan
fonte