Come posso verificare se moltiplicare due numeri in Java causerà un overflow?

Question

Voglio gestire il caso particolare in cui moltiplicare due numeri insieme provoca un overflow. Il codice simile a questa:

int a = 20;
long b = 30;

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

Questa è una versione semplificata. Nel vero a programma e b vengono acquistati altrove in fase di esecuzione. Quello che voglio ottenere è qualcosa di simile:

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

Come si fa a suggerire ho miglior codice questo?

Aggiornamento: a e b sono sempre non negativo nel mio scenario

.

Answer 1

Java 8 ha Math.multiplyExact, Math.addExact ecc per int e lunga. Queste gettano un ArithmeticException incontrollato in caso di overflow.

Answer 2

Se a e b sono entrambi positivi, allora è possibile utilizzare:

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

Se avete bisogno di trattare con entrambi i numeri positivi e negativi, allora è più complicato:

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
}

Ecco un piccolo tavolo ho incitato a controllare questo, facendo finta che trabocco accade a -10 o 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

Answer 3

Ci sono librerie Java che forniscono operazioni aritmetiche sicure, che verificano lungo di overflow / underflow. Ad esempio, di Guava LongMath.checkedMultiply (a lungo una, lunga b) restituisce il prodotto di a e b, a condizione che non trabocchi, e lancia ArithmeticException se overflow a * b in aritmetica long firmato.

Answer 4

Si potrebbe utilizzare java.math.BigInteger invece e verificare la dimensione del risultato (non hanno testato il codice):

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()
}

Answer 5

Utilizzare i logaritmi per verificare la dimensione del risultato.

Answer 6

La Java ha qualcosa come int.MaxValue? Se sì, allora provare

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

modifica: visto Long.MAX_VALUE in questione

Answer 7

Rubato da JRuby

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

UPDATE: Questo codice è breve e funziona bene; tuttavia, esso non riesce per a = -1, b = Long.MIN_VALUE.

Una possibile miglioramento:

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

Si noti che questo prenderà alcuni overflow senza alcuna divisione.

Answer 8

Qui è il modo più semplice che posso pensare

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"
}

Answer 9

Non sono sicuro che il motivo per cui nessuno sta guardando soluzione come:

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

Scegliere un essere più grande dei due numeri.

Answer 10

Mi piacerebbe costruire sulla risposta di John Kugelman senza sostituirlo modificando direttamente. Si lavora per il suo banco di prova (MIN_VALUE = -10, MAX_VALUE = 10) a causa della simmetria della MIN_VALUE == -MAX_VALUE, che non è il caso per due interi di complemento. In realtà, 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 viene applicato al vero MIN_VALUE e MAX_VALUE, la risposta di John Kugelman produce un caso di troppo pieno quando a == -1 e b == qualsiasi altra cosa (primo punto sollevato da Kyle). Ecco un modo per risolvere il problema:

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
}

Non è una soluzione generale per qualsiasi MIN_VALUE e MAX_VALUE, ma è generale per Long e Integer di Java e ogni valore di a e b.

Answer 11

Forse:

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

Non sono sicuro di questo "soluzione".

Modifica:!. Aggiunto b = 0

Prima downvote : a * b / b non sarà ottimizzato. Questo sarebbe compilatore bug. Io non vedo ancora un caso in cui il bug di overflow può essere mascherato.

Answer 12

forse questo ti aiuterà a:

/**
 * @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;
    }
}

Answer 13

Come è stato sottolineato, Java 8 dispone di metodi Math.xxxExact che producono eccezioni in caso di overflow.

Se non si utilizza Java 8 per il progetto, è ancora possibile "prendere in prestito" le loro implementazioni che sono abbastanza compatto.

Ecco alcuni link a queste implementazioni su un sito web 3a parte, alcuna garanzia se queste rimarranno valide ma in ogni caso si dovrebbe essere in grado di andare alla fonte di JDK e vedere come lo fanno la loro magia all'interno della classe 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

ecc, ecc.

Answer 14

C / C ++ (long * lunga):

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

java (int * int, mi dispiace non ho trovato Int64 in 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.save il risultato in caratteri grandi (int * int mettere il risultato al lungo, lungo tempo * messo a Int64)

Risultati 2.cmp >> bit e risultato >> (bit - 1)