Jak mogę sprawdzić, czy pomnożenie dwóch liczb w Javie spowoduje przepełnienie?

Chcę zająć się specjalnym przypadkiem, w którym pomnożenie dwóch liczb razem powoduje przepełnienie. Kod wygląda mniej więcej tak:

int a = 20;
long b = 30;

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

To uproszczona wersja. W prawdziwym programie ai bsą pozyskiwane gdzie indziej w czasie wykonywania. To, co chcę osiągnąć, to coś takiego:

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

Jak sugerujesz, żebym najlepiej to zakodował?

Aktualizacja: ai bzawsze są nieujemne w moim scenariuszu.

Java 8 ma Math.multiplyExact, Math.addExactitd. Za wskazówki i długie. Te rzucają niesprawdzone ArithmeticExceptionna przepełnienie.

Jeśli ai bto zarówno pozytywne, wówczas można użyć:

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

Jeśli musisz radzić sobie zarówno z liczbami dodatnimi, jak i ujemnymi, jest to bardziej skomplikowane:

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
}

Oto mały stolik, który podniosłem, aby to sprawdzić, udając, że przepełnienie ma miejsce przy -10 lub +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

Istnieją biblioteki Java, które zapewniają bezpieczne operacje arytmetyczne, które sprawdzają długie przepełnienie / niedomiar. Na przykład LongMath.checkedMultiply Guawy (long a, long b) zwraca iloczyn ai b, pod warunkiem, że nie przepełnia, i zgłasza, ArithmeticExceptionjeśli a * bprzepełnia się w longarytmetyce ze znakiem.

Możesz zamiast tego użyć java.math.BigInteger i sprawdzić rozmiar wyniku (kod nie został przetestowany):

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

Użyj logarytmów, aby sprawdzić rozmiar wyniku.

Czy Java ma coś takiego jak int.MaxValue? Jeśli tak, spróbuj

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

edit: widziano Long.MAX_VALUE w pytaniu

Oto najprostszy sposób, jaki przychodzi mi do głowy

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

Skradziony z jrub

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

UPDATE: Ten kod jest krótki i działa dobrze; jednak nie powiedzie się dla a = -1, b = Long.MIN_VALUE.

Jedno możliwe ulepszenie:

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

Zwróć uwagę, że spowoduje to wyłapanie niektórych przepełnień bez podziału.

Jak już wspomniano, Java 8 ma metody Math.xxxExact, które generują wyjątki w przypadku przepełnienia.

Jeśli nie używasz Java 8 w swoim projekcie, nadal możesz „pożyczyć” ich implementacje, które są dość kompaktowe.

Oto kilka linków do tych implementacji w repozytorium kodu źródłowego JDK. Nie ma gwarancji, że pozostaną one prawidłowe, ale w każdym razie powinieneś być w stanie pobrać źródło JDK i zobaczyć, jak wykonują swoją magię wewnątrz java.lang.Mathklasy.

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

itd itd.

AKTUALIZACJA: zmieniono nieprawidłowe linki do stron internetowych osób trzecich na linki do repozytoriów Mercurial Open JDK.

Nie jestem pewien, dlaczego nikt nie szuka rozwiązania takiego jak:

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

Wybierz jedną, aby była większa z dwóch liczb.

Chciałbym wykorzystać odpowiedź Johna Kugelmana bez zastępowania jej przez bezpośrednią edycję. Działa to w przypadku jego przypadku testowego ( MIN_VALUE = -10, MAX_VALUE = 10) ze względu na symetrię MIN_VALUE == -MAX_VALUE, co nie ma miejsca w przypadku liczb całkowitych z dopełnieniem do dwóch. W rzeczywistości 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)

Po zastosowaniu do prawdziwych MIN_VALUEi MAX_VALUE, odpowiedź Johna Kugelmana daje przypadek przepełnienia kiedy a == -1i b ==cokolwiek innego (punkt podniesiony najpierw przez Kyle'a). Oto sposób, aby to naprawić:

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
}

Nie jest to ogólne rozwiązanie dla każdego MIN_VALUEa MAX_VALUE, ale to ogólnie dla Javy Longi Integeroraz każda wartość ai b.

Może:

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

Nie jestem pewien co do tego „rozwiązania”.

Edycja: dodano b! = 0.

Zanim zagłosujesz przeciw : a * b / b nie zostanie zoptymalizowany. Byłby to błąd kompilatora. Nadal nie widzę przypadku, w którym można by zamaskować błąd przepełnienia.

może to ci pomoże:

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

c / c ++ (long * long):

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

java (int * int, przepraszam, nie znalazłem int64 w 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. zapisz wynik w dużym typie (int * int wstaw wynik do long, long * long put do int64)

2. wynik cmp >> bity i wynik >> (bity - 1)