Como o Java lida com estoques e estouros inteiros e como você o verificaria?

226

Como o Java lida com estoques e estouros inteiros?

A partir disso, como você verificaria / testaria se isso está ocorrendo?

KushalP
fonte
28
É uma pena que o Java não forneça acesso indireto ao sinalizador de estouro da CPU , como é feito em C # .
Drew Noakes
@DrewNoakes E é muito ruim que o C # não seja o padrão até checkedonde eu sei. Não o vejo muito usado, e digitar checked { code; }é tão trabalho quanto chamar um método.
Maarten Bodewes
2
@MaartenBodewes, você pode defini-lo como padrão durante a compilação de um assembly. csc /checked ...ou defina a propriedade no painel de propriedades do projeto no Visual Studio.
de Drew Noakes
@DrewNoakes OK, interessante. Um pouco estranho que seja uma configuração fora do código. Em geral, eu gostaria de ter o mesmo comportamento de um programa, independentemente de tais configurações (possivelmente, exceto afirmações).
Maarten Bodewes
@MaartenBodewes, acho que o raciocínio é que há uma sobrecarga de desempenho não trivial para verificação. Portanto, talvez você o habilite nas compilações de depuração e a desabilite nas compilações de versão, assim como muitos outros tipos de asserções.
precisa

Respostas:

217

Se estourar, retornará ao valor mínimo e continuará a partir daí. Se o fluxo for insuficiente, ele retornará ao valor máximo e continuará a partir daí.

Você pode verificar isso da seguinte maneira:

public static boolean willAdditionOverflow(int left, int right) {
    if (right < 0 && right != Integer.MIN_VALUE) {
        return willSubtractionOverflow(left, -right);
    } else {
        return (~(left ^ right) & (left ^ (left + right))) < 0;
    }
}

public static boolean willSubtractionOverflow(int left, int right) {
    if (right < 0) {
        return willAdditionOverflow(left, -right);
    } else {
        return ((left ^ right) & (left ^ (left - right))) < 0;
    }
}

(você pode substituir intpor longpara executar as mesmas verificações long)

Se você acha que isso pode ocorrer com mais frequência, considere usar um tipo de dados ou objeto que possa armazenar valores maiores, por exemplo, longou talvez java.math.BigInteger. O último não transborda, praticamente, a memória JVM disponível é o limite.


Se você já estiver no Java8, poderá usar os métodos new Math#addExact()e new Math#subtractExact()que lançarão um ArithmeticExceptionoverflow.

public static boolean willAdditionOverflow(int left, int right) {
    try {
        Math.addExact(left, right);
        return false;
    } catch (ArithmeticException e) {
        return true;
    }
}

public static boolean willSubtractionOverflow(int left, int right) {
    try {
        Math.subtractExact(left, right);
        return false;
    } catch (ArithmeticException e) {
        return true;
    }
}

O código fonte pode ser encontrado aqui e aqui, respectivamente.

Obviamente, você também pode usá-los imediatamente, em vez de ocultá-los em um booleanmétodo utilitário.

BalusC
fonte
13
@ dhblah, digamos que os valores máximo e mínimo que o Java permite para um int sejam +100, -100, respectivamente. Se você estivesse adicionando um a um número inteiro Java, o processo ficaria assim quando estourasse. 98, 99, 100, -100, -99, -98, .... Isso faz mais sentido?
Austin A
6
Eu recomendo usar os métodos utilitários em vez de usar o código imediatamente. Os métodos utilitários são intrínsecos e serão substituídos pelo código específico da máquina. Um teste rápido mostrou que Math.addExact era 30% mais rápido que um método copiado (Java 1.8.0_40).
precisa saber é o seguinte
1
@ErikE Math#addExacté a sintaxe normalmente utilizado quando se escreve javadocs - enquanto normalmente que seria convertido para Math.addExact, por vezes, a outra forma apenas fura ao redor
Pokechu22
1
If it underflows, it goes back to the maximum value and continues from there.- você parece ter confundido o estouro com o estouro negativo. underflow em números inteiros acontece o tempo todo (quando o resultado é uma fração).
nave
1
en.wikipedia.org/wiki/Arithmetic_underflow diz que Underflow é uma condição em um programa de computador em que o resultado de um cálculo é um número absoluto de valor absoluto menor do que o computador pode realmente representar na memória em sua CPU. Portanto, o fluxo insuficiente não se aplica aos números inteiros Java. @BalusC
Jingguo Yao 14/10
66

Bem, no que diz respeito aos tipos inteiros primitivos, o Java não suporta Over / Underflow (para float e double o comportamento é diferente, ele será liberado para +/- infinito, como exige o IEEE-754).

Ao adicionar dois int's, você não receberá nenhuma indicação quando ocorrer um estouro. Um método simples para verificar se há estouro é usar o próximo tipo maior para realmente executar a operação e verificar se o resultado ainda está dentro do intervalo para o tipo de fonte:

public int addWithOverflowCheck(int a, int b) {
    // the cast of a is required, to make the + work with long precision,
    // if we just added (a + b) the addition would use int precision and
    // the result would be cast to long afterwards!
    long result = ((long) a) + b;
    if (result > Integer.MAX_VALUE) {
         throw new RuntimeException("Overflow occured");
    } else if (result < Integer.MIN_VALUE) {
         throw new RuntimeException("Underflow occured");
    }
    // at this point we can safely cast back to int, we checked before
    // that the value will be withing int's limits
    return (int) result;
}

O que você faria no lugar das cláusulas de lançamento depende dos requisitos de seus aplicativos (lançamento, descarga para min / max ou apenas faça o log). Se você deseja detectar estouro em operações longas, não tem sorte com os primitivos, use o BigInteger.


Edit (21/05/2014): Como essa pergunta parece ser referida com bastante frequência e eu tive que resolver o mesmo problema, é muito fácil avaliar a condição de estouro pelo mesmo método que uma CPU calcula seu sinalizador V.

É basicamente uma expressão booleana que envolve o sinal de ambos os operandos e o resultado:

/**
 * Add two int's with overflow detection (r = s + d)
 */
public static int add(final int s, final int d) throws ArithmeticException {
    int r = s + d;
    if (((s & d & ~r) | (~s & ~d & r)) < 0)
        throw new ArithmeticException("int overflow add(" + s + ", " + d + ")");    
    return r;
}

Em java, é mais simples aplicar a expressão (no if) aos 32 bits inteiros e verificar o resultado usando <0 (isso testará efetivamente o bit de sinal). O princípio funciona exatamente da mesma forma para todos os tipos primitivos inteiros , alterando todas as declarações no método acima para long faz com que funcione por muito tempo.

Para tipos menores, devido à conversão implícita em int (consulte o JLS para operações bit a bit para obter detalhes), em vez de marcar <0, a verificação precisa mascarar explicitamente o bit de sinal (0x8000 para operandos curtos, 0x80 para operandos de byte, ajustar as conversões e declaração de parâmetro adequadamente):

/**
 * Subtract two short's with overflow detection (r = d - s)
 */
public static short sub(final short d, final short s) throws ArithmeticException {
    int r = d - s;
    if ((((~s & d & ~r) | (s & ~d & r)) & 0x8000) != 0)
        throw new ArithmeticException("short overflow sub(" + s + ", " + d + ")");
    return (short) r;
}

(Observe que o exemplo acima usa a expressão necessidade de subtrair a detecção de estouro)


Então, como / por que essas expressões booleanas funcionam? Primeiro, algum pensamento lógico revela que um estouro pode ocorrer se os sinais dos dois argumentos forem os mesmos. Porque, se um argumento é negativo e um positivo, o resultado (de adição) deve estar mais próximo de zero ou, no caso extremo, um argumento é zero, o mesmo que o outro argumento. Como os argumentos por si só não podem criar uma condição de estouro, sua soma também não pode criar um estouro.

Então, o que acontece se ambos os argumentos tiverem o mesmo sinal? Vamos dar uma olhada no caso em que ambos são positivos: adicionar dois argumentos que criam uma soma maior que os tipos MAX_VALUE, sempre produzirá um valor negativo; portanto, um estouro ocorrerá se arg1 + arg2> MAX_VALUE. Agora, o valor máximo que poderia resultar seria MAX_VALUE + MAX_VALUE (o caso extremo dos dois argumentos é MAX_VALUE). Para um byte (exemplo) que significaria 127 + 127 = 254. Observando as representações de bits de todos os valores que podem resultar da adição de dois valores positivos, verifica-se que aqueles que excedem (128 a 254) possuem o bit 7 definido, enquanto tudo o que não transborda (0 a 127) tem o bit 7 (mais alto, sinal) limpo. É exatamente isso que a primeira parte (direita) da expressão verifica:

if (((s & d & ~r) | (~s & ~d & r)) < 0)

(~ s & ~ d & r) se torna verdadeiro, somente se os dois operandos (s, d) forem positivos e o resultado (r) for negativo (a expressão funciona em todos os 32 bits, mas é o único bit em que estamos interessados) é o bit mais alto (sinal), que é verificado pelo <0).

Agora, se ambos os argumentos são negativos, sua soma nunca pode estar mais próxima de zero do que qualquer um dos argumentos, a soma deve estar mais próxima de menos infinito. O valor mais extremo que podemos produzir é MIN_VALUE + MIN_VALUE, que (novamente para exemplo de byte) mostra que, para qualquer valor no intervalo (-1 a -128), o bit de sinal é definido, enquanto qualquer valor transbordante possível (-129 a -256 ) tem o sinal limpo. Portanto, o sinal do resultado novamente revela a condição de estouro. É o que a metade esquerda (s & d & r) verifica para o caso em que ambos os argumentos (s, d) são negativos e um resultado positivo. A lógica é amplamente equivalente ao caso positivo; todos os padrões de bits que podem resultar da adição de dois valores negativos terão o bit de sinal limpo, se e somente se ocorrer um estouro.

Durandal
fonte
1
Você pode verificá-lo com operadores bit a bit, bem betterlogic.com/roger/2011/05/...
rogerdpack
1
Isso vai funcionar, mas estou assumindo que ele terá um desempenho desagradável.
Chessofnerd
33

Por padrão, a matemática int e long do Java envolve silenciosamente o estouro e o estouro. (Operações de número inteiro em outros tipos de número inteiro são executadas promovendo primeiro os operandos para int ou long, conforme JLS 4.2.2 .)

A partir de Java 8, java.lang.Mathfornece addExact, subtractExact, multiplyExact, incrementExact, decrementExacte negateExactmétodos estáticos para ambos int e longos argumentos que realizam a operação denominada, jogando ArithmeticException no estouro. (Não existe um método divideExact - você deverá verificar o caso especial ( MIN_VALUE / -1).)

No Java 8, o java.lang.Math também fornece toIntExacta conversão de um long para um int, lançando ArithmeticException se o valor do long não se encaixar em um int. Isso pode ser útil para, por exemplo, calcular a soma de entradas usando matemática longa não verificada e depois usar toIntExactpara converter para int no final (mas tome cuidado para não deixar sua soma transbordar).

Se você ainda estiver usando uma versão mais antiga do Java, o Google Guava fornecerá métodos estáticos IntMath e LongMath para adição, subtração, multiplicação e exponenciação verificadas (jogando em excesso). Essas classes também fornecem métodos para calcular fatoriais e coeficientes binomiais que retornam MAX_VALUEao estouro (o que é menos conveniente para verificar). Classes utilitárias primitivos de goiaba, SignedBytes, UnsignedBytes, Shortse Ints, proporcionar checkedCastmétodos para estreitar tipos maiores (jogando sobre IllegalArgumentException sob / descarga, não ArithmeticException), bem como saturatingCastmétodos que retorno MIN_VALUEou MAX_VALUEem excesso.

Jeffrey Bosboom
fonte
32

Java não faz nada com excesso de número inteiro para tipos primitivos int ou long e ignora o excesso com números inteiros positivos e negativos.

Esta resposta descreve primeiro o excesso de número inteiro, fornece um exemplo de como isso pode acontecer, mesmo com valores intermediários na avaliação da expressão e, em seguida, fornece links para recursos que fornecem técnicas detalhadas para prevenir e detectar o excesso de número inteiro.

Aritmética inteira e expressões que resultam em estouro inesperado ou não detectado são um erro de programação comum. O excesso inesperado ou não detectado de números inteiros também é um problema de segurança explorável bem conhecido, especialmente porque afeta objetos de matriz, pilha e lista.

O estouro pode ocorrer em uma direção positiva ou negativa, onde o valor positivo ou negativo estaria além dos valores máximos ou mínimos do tipo primitivo em questão. O estouro pode ocorrer em um valor intermediário durante a avaliação da expressão ou operação e afetar o resultado de uma expressão ou operação em que o valor final deveria estar dentro do intervalo.

Às vezes, o estouro negativo é chamado erroneamente de estouro. Subfluxo é o que acontece quando um valor está mais próximo de zero do que a representação permite. O subfluxo ocorre na aritmética inteira e é esperado. O fluxo insuficiente inteiro acontece quando uma avaliação inteira está entre -1 e 0 ou 0 e 1. O que seria um resultado fracionário trunca para 0. Isso é normal e esperado com aritmética inteira e não é considerado um erro. No entanto, isso pode levar ao código que lança uma exceção. Um exemplo é uma exceção "ArithmeticException: / by zero" se o resultado do underflow inteiro for usado como um divisor em uma expressão.

Considere o seguinte código:

int bigValue = Integer.MAX_VALUE;
int x = bigValue * 2 / 5;
int y = bigValue / x;

que resulta na atribuição de x a 0 e na avaliação subsequente de bigValue / x lança uma exceção, "ArithmeticException: / by zero" (ou seja, divide por zero), em vez de y receber o valor 2.

O resultado esperado para x seria 858.993.458, que é menor que o valor int máximo de 2.147.483.647. No entanto, o resultado intermediário da avaliação de Integer.MAX_Value * 2 seria 4.294.967.294, que excede o valor máximo int e é -2 de acordo com 2s, complementando representações inteiras. A avaliação subsequente de -2 / 5 é avaliada como 0 e é atribuída a x.

Reorganizando a expressão para computar x para uma expressão que, quando avaliada, divide antes da multiplicação, o seguinte código:

int bigValue = Integer.MAX_VALUE;
int x = bigValue / 5 * 2;
int y = bigValue / x;

resulta em x sendo atribuído 858.993.458 e y sendo atribuído 2, o que é esperado.

O resultado intermediário de bigValue / 5 é 429.496.729, que não excede o valor máximo para um int. A avaliação subsequente de 429.496.729 * 2 não excede o valor máximo de um int e o resultado esperado é atribuído a x. A avaliação para y então não se divide por zero. As avaliações para x e y funcionam conforme o esperado.

Os valores inteiros Java são armazenados e se comportam de acordo com o 2s complementam representações inteiras assinadas. Quando um valor resultante for maior ou menor que o valor inteiro máximo ou mínimo, o valor inteiro do complemento de 2 resultará. Em situações não expressamente projetadas para usar o comportamento do complemento 2s, que é a maioria das situações aritméticas inteiras comuns, o valor resultante do complemento 2s causará uma lógica de programação ou erro de computação, como foi mostrado no exemplo acima. Um excelente artigo da Wikipedia descreve números inteiros binários de 2s aqui: Complemento de dois - Wikipedia

Existem técnicas para evitar o excesso não intencional de números inteiros. As técnicas podem ser categorizadas como teste de pré-condição, upcasting e BigInteger.

O teste de pré-condição compreende examinar os valores que entram em uma operação ou expressão aritmética para garantir que um estouro não ocorra com esses valores. A programação e o design precisarão criar testes que garantam que os valores de entrada não causem estouro e, em seguida, determinem o que fazer se ocorrerem valores de entrada que causarão estouro.

A upcasting compreende o uso de um tipo primitivo maior para executar a operação ou expressão aritmética e, em seguida, determinar se o valor resultante está além dos valores máximo ou mínimo para um número inteiro. Mesmo com upcasting, ainda é possível que o valor ou algum valor intermediário em uma operação ou expressão esteja além dos valores máximos ou mínimos para o tipo de upcast e cause excesso, o que também não será detectado e causará resultados inesperados e indesejados. Por meio de análise ou pré-condições, pode ser possível evitar o transbordamento com upcasting quando a prevenção sem upcasting não for possível ou prática. Se os números inteiros em questão já forem do tipo primitivo longo, não será possível fazer upcast com os tipos primitivos em Java.

A técnica BigInteger compreende o uso do BigInteger para a operação ou expressão aritmética usando métodos de biblioteca que usam o BigInteger. O BigInteger não transborda. Ele usará toda a memória disponível, se necessário. Seus métodos aritméticos são normalmente apenas um pouco menos eficientes que as operações com números inteiros. Ainda é possível que um resultado usando o BigInteger possa estar além dos valores máximo ou mínimo para um número inteiro; no entanto, o excesso não ocorrerá na aritmética que leva ao resultado. A programação e o design ainda precisam determinar o que fazer se um resultado do BigInteger estiver além dos valores máximos ou mínimos para o tipo de resultado primitivo desejado, por exemplo, int ou long.

O programa CERT do Instituto de Engenharia de Software Carnegie Mellon e a Oracle criaram um conjunto de padrões para a programação segura de Java. Incluídas nos padrões estão as técnicas para prevenir e detectar o excesso de número inteiro. O padrão é publicado como um recurso on-line acessível gratuitamente aqui: O CERT Oracle Secure Coding Standard for Java

A seção da norma que descreve e contém exemplos práticos de técnicas de codificação para impedir ou detectar o excesso de número inteiro está aqui: NUM00-J. Detectar ou impedir o estouro de números inteiros

Também estão disponíveis o formulário de livro e o formato PDF do CERT Oracle Secure Coding Standard para Java.

Jim
fonte
esta é a melhor resposta aqui como ele afirma claramente que underflow é (a resposta aceita não) e também lista as técnicas para lidar com o estouro / estouro negativo
nave
12

Tendo acabado de me deparar com esse problema, aqui está minha solução (para multiplicação e adição):

static boolean wouldOverflowOccurwhenMultiplying(int a, int b) {
    // If either a or b are Integer.MIN_VALUE, then multiplying by anything other than 0 or 1 will result in overflow
    if (a == 0 || b == 0) {
        return false;
    } else if (a > 0 && b > 0) { // both positive, non zero
        return a > Integer.MAX_VALUE / b;
    } else if (b < 0 && a < 0) { // both negative, non zero
        return a < Integer.MAX_VALUE / b;
    } else { // exactly one of a,b is negative and one is positive, neither are zero
        if (b > 0) { // this last if statements protects against Integer.MIN_VALUE / -1, which in itself causes overflow.
            return a < Integer.MIN_VALUE / b;
        } else { // a > 0
            return b < Integer.MIN_VALUE / a;
        }
    }
}

boolean wouldOverflowOccurWhenAdding(int a, int b) {
    if (a > 0 && b > 0) {
        return a > Integer.MAX_VALUE - b;
    } else if (a < 0 && b < 0) {
        return a < Integer.MIN_VALUE - b;
    }
    return false;
}

fique à vontade para corrigir se está errado ou se pode ser simplificado. Fiz alguns testes com o método de multiplicação, principalmente casos extremos, mas ainda pode estar errado.

fragorl
fonte
A divisão costuma ser lenta em relação à multiplicação. Pois int*int, eu acho que simplesmente lançar longe ver se o resultado se encaixa intseria a abordagem mais rápida. Pois long*long, se alguém normaliza os operandos para serem positivos, pode-se dividir cada uma nas metades superior e inferior de 32 bits, promover cada uma delas por muito tempo (tenha cuidado com as extensões de sinal!) E depois calcular dois produtos parciais [uma das metades superiores deve seja zero].
Supercat
Quando você diz "Por muito * longo, se um normalizar operandos para ser positivo ...", como você normalizaria Long.MIN_VALUE?
fragorl
Esses métodos podem ser interessantes se for necessário testar se algo transborda antes de realmente executar o cálculo. Poderia ser bom para testar, por exemplo, a entrada do usuário usada para esses cálculos, em vez de capturar a exceção quando isso acontece.
Maarten Bodewes
8

Existem bibliotecas que fornecem operações aritméticas seguras, que verificam o excesso / o excesso de números inteiros. Por exemplo, IntMath.checkedAdd (int a, int b) do Guava retorna a soma de ae b, desde que não transborde, e lança ArithmeticExceptionse a + bexceder na intaritmética assinada .

reprogramador
fonte
Sim, é uma boa ideia, a menos que você seja Java 8 ou superior; nesse caso, a Mathclasse contém código semelhante.
Maarten Bodewes
6

Envolve.

por exemplo:

public class Test {

    public static void main(String[] args) {
        int i = Integer.MAX_VALUE;
        int j = Integer.MIN_VALUE;

        System.out.println(i+1);
        System.out.println(j-1);
    }
}

impressões

-2147483648
2147483647
Peter Tillemans
fonte
Bem! E agora, você pode responder, como detectá-lo em cálculos complexos?
Aubin
5

Eu acho que você deve usar algo parecido com isto e é chamado Upcasting:

public int multiplyBy2(int x) throws ArithmeticException {
    long result = 2 * (long) x;    
    if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE){
        throw new ArithmeticException("Integer overflow");
    }
    return (int) result;
}

Você pode ler mais aqui: Detectar ou impedir o excesso de números inteiros

É uma fonte bastante confiável.

Dusan
fonte
3

Ele não faz nada - o under / overflow simplesmente acontece.

Um "-1" resultante de uma computação que estourou demais não é diferente do "-1" resultante de qualquer outra informação. Portanto, você não pode dizer através de algum status ou inspecionando apenas um valor se está excedendo.

Mas você pode ser inteligente em relação aos seus cálculos para evitar transbordamentos, se isso interessar, ou pelo menos saber quando isso acontecerá. Qual é a sua situação?

Sean Owen
fonte
Não é realmente uma situação, apenas algo que me interessa e me faz pensar. Se você precisar de um exemplo de caso de uso, aqui está um: Eu tenho uma classe com sua própria variável interna chamada 'seconds'. Eu tenho dois métodos que tomam um número inteiro como parâmetro e aumentam ou diminuem (respectivamente) 'segundos' por esse valor. Como você testaria unitariamente se um estouro / estouro de fluxo está ocorrendo e como impediria que isso ocorresse?
precisa saber é o seguinte
1
static final int safeAdd(int left, int right)
                 throws ArithmeticException {
  if (right > 0 ? left > Integer.MAX_VALUE - right
                : left < Integer.MIN_VALUE - right) {
    throw new ArithmeticException("Integer overflow");
  }
  return left + right;
}

static final int safeSubtract(int left, int right)
                 throws ArithmeticException {
  if (right > 0 ? left < Integer.MIN_VALUE + right
                : left > Integer.MAX_VALUE + right) {
    throw new ArithmeticException("Integer overflow");
  }
  return left - right;
}

static final int safeMultiply(int left, int right)
                 throws ArithmeticException {
  if (right > 0 ? left > Integer.MAX_VALUE/right
                  || left < Integer.MIN_VALUE/right
                : (right < -1 ? left > Integer.MIN_VALUE/right
                                || left < Integer.MAX_VALUE/right
                              : right == -1
                                && left == Integer.MIN_VALUE) ) {
    throw new ArithmeticException("Integer overflow");
  }
  return left * right;
}

static final int safeDivide(int left, int right)
                 throws ArithmeticException {
  if ((left == Integer.MIN_VALUE) && (right == -1)) {
    throw new ArithmeticException("Integer overflow");
  }
  return left / right;
}

static final int safeNegate(int a) throws ArithmeticException {
  if (a == Integer.MIN_VALUE) {
    throw new ArithmeticException("Integer overflow");
  }
  return -a;
}
static final int safeAbs(int a) throws ArithmeticException {
  if (a == Integer.MIN_VALUE) {
    throw new ArithmeticException("Integer overflow");
  }
  return Math.abs(a);
}
user4267316
fonte
2
Isso lida com o teste. Embora não explique como o Java lida com estoques e estouros inteiros (adicione algum texto para explicar).
Spencer Wieczorek
1

Eu acho que isso deve ficar bem.

static boolean addWillOverFlow(int a, int b) {
    return (Integer.signum(a) == Integer.signum(b)) && 
            (Integer.signum(a) != Integer.signum(a+b)); 
}
John Woo
fonte
0

Há um caso, que não é mencionado acima:

int res = 1;
while (res != 0) {
    res *= 2;

}
System.out.println(res);

vai produzir:

0

Este caso foi discutido aqui: O excesso de número inteiro produz Zero.

lobzik
fonte