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

101

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.

Steve McLeod
źródło
6
Szkoda, że ​​Java nie zapewnia pośredniego dostępu do flagi przepełnienia procesora , jak ma to miejsce w C # .
Drew Noakes,

Odpowiedzi:

92

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

bcoughlan
źródło
59

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
John Kugelman
źródło
Powinienem wspomnieć, że a i b są zawsze nieujemne w moim scenariuszu, co nieco uprościłoby to podejście.
Steve McLeod
3
Myślę, że to może zawieść przypadek: a = -1 ib = 10. Maksymalne / a wyrażenie daje w wyniku Integer.MIN_VALUE i wykrywa przepełnienie, gdy żaden nie istnieje
Kyle
To jest naprawdę miłe. Dla tych, zastanawiając się, powodem tego jest to, że działa dla liczb całkowitych n, n > xjest taki sam jak n > floor(x). Dla dodatnich liczb całkowitych dzielenie ma niejawne piętro. (W przypadku liczb ujemnych zaokrągla się w górę)
Thomas Ahle
Aby rozwiązać problem a = -1i b = 10, zobacz moją odpowiedź poniżej.
Jim Pivarski
17

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.

przeprogramować
źródło
4
To najlepsza odpowiedź - skorzystaj z biblioteki, która została zaimplementowana przez ludzi, którzy naprawdę rozumieją arytmetykę maszynową w Javie i która została przetestowana przez wiele osób. Nie próbuj pisać własnego ani używać żadnego na wpół wypalonego, nieprzetestowanego kodu zamieszczonego w innych odpowiedziach!
Rich
@Enerccio - Nie rozumiem twojego komentarza. Chcesz powiedzieć, że guawa nie będzie działać na wszystkich systemach? Zapewniam, że będzie działać wszędzie tam, gdzie działa Java. Czy twierdzisz, że ponowne użycie kodu jest ogólnie złym pomysłem? Nie zgadzam się, jeśli tak.
Rich
2
@Rich Mówię, że włączenie ogromnej biblioteki, aby można było użyć jednej funkcji, to zły pomysł.
Enerccio,
Czemu? Jeśli piszesz dużą aplikację, na przykład dla firmy, dodatkowy plik JAR na ścieżce klas nic nie zaszkodzi, a Guava zawiera wiele bardzo przydatnego kodu. O wiele lepiej jest ponownie wykorzystać ich dokładnie przetestowany kod, niż spróbować napisać własną wersję tego samego (co, jak sądzę, polecasz?). Jeśli piszesz w środowisku, w którym dodatkowy plik JAR będzie bardzo drogi (gdzie? Osadzona Java?), Być może powinieneś wyodrębnić tylko tę klasę z Guavy. Czy kopiowanie nieprzetestowanej odpowiedzi ze StackOverflow jest lepsze niż kopiowanie starannie przetestowanego kodu Guavy?
Rich
Czy rzucanie wyjątku nie jest trochę przesadą dla czegoś, co warunkowe, jeśli-to może sobie poradzić?
Victim
6

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()
}
Ulf Lindback
źródło
7
Uważam,
Jednak to chyba najlepszy sposób na zrobienie tego. Założyłem, że to aplikacja numeryczna, dlatego nie polecałem jej od ręki, ale to naprawdę jest prawdopodobnie najlepszy sposób rozwiązania tego problemu.
Stefan Kendall
2
Nie jestem pewien, czy można użyć operatora „>” z BigInteger. należy użyć metody compareTo.
Pierre
zmieniono na compareTo, a prędkość może mieć znaczenie lub nie, zależy od okoliczności, w których kod będzie używany.
Ulf Lindback
5

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

Znak wysokiej wydajności
źródło
masz na myśli ceil(log(a)) + ceil(log(b)) > log(Long.MAX):?
Thomas Jung
1
Sprawdziłem to. Dla małych wartości jest 20% szybszy niż BigInteger, a dla wartości bliskich MAX jest prawie taki sam (5% szybciej). Kod Yossariana jest najszybszy (95% i 75% szybciej niż BigInteger).
Thomas Jung
Podejrzewam raczej, że w niektórych przypadkach może się to nie udać.
Tom Hawtin - tackline
Pamiętaj, że dziennik całkowitoliczbowy faktycznie liczy tylko liczbę wiodących zer i możesz zoptymalizować niektóre typowe przypadki (np. Jeśli ((a | b) & 0xffffffff00000000L) == 0) wiesz, że jesteś bezpieczny). Z drugiej strony, jeśli nie możesz obniżyć optymalizacji do 30/40 cykli zegara dla najczęstszych przypadków, metoda Johna Kugelmana prawdopodobnie będzie działać lepiej (dzielenie liczb całkowitych to ok. 2 bity / cykl zegara, o czym pamiętam).
Neil Coffey
PS Sorr, myślę, że potrzebuję dodatkowego zestawu w masce AND (0xffffffff80000000L) - jest trochę późno, ale masz pomysł ...
Neil Coffey
4

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

nothrow
źródło
Nie głosowałem przeciw, ale Math.Abs(a)nie działa, jeśli atak Long.MIN_VALUE.
John Kugelman
@John - a i b są> 0. Myślę, że podejście Yossariana (b! = 0 && a> Long.MAX_VALUE / b) jest najlepsze.
Thomas Jung
@Thomas, a i b są> = 0, czyli nieujemne.
Steve McLeod
2
Racja, ale w tym przypadku nie potrzeba Abs. Jeśli dozwolone są liczby ujemne, to kończy się to niepowodzeniem dla co najmniej jednego przypadku skrajnego. To wszystko, co mówię, po prostu bycie czubkiem.
John Kugelman
w Javie musisz używać Math.abs, a nie Math.Abs ​​(C # guy?)
dfa
4

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"
}
Naren
źródło
3

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.

rogerdpack
źródło
Możesz użyć Long.signum zamiast Math.signum
aditsu zakończyło, ponieważ SE jest ZŁEM.
3

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.

StFS
źródło
2

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.

fastcodejava
źródło
2
Nie sądzę, że ma to znaczenie, czy ajest większy czy mniejszy?
Thomas Ahle
2

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.

Jim Pivarski
źródło
Pomyślałem, że to niepotrzebnie skomplikuje sprawę, ponieważ to rozwiązanie działa tylko wtedy MIN_VALUE = -MAX_VALUE - 1, gdy nie ma innego przypadku (w tym przykładowego przypadku testowego). Musiałbym dużo zmienić.
Jim Pivarski
1
Z przyczyn niezależnych od oryginalnego plakatu; dla ludzi takich jak ja, którzy znaleźli tę stronę, ponieważ potrzebowali rozwiązania dla bardziej ogólnego przypadku (obsługa liczb ujemnych, a nie ściśle Java 8). W rzeczywistości, ponieważ to rozwiązanie nie obejmuje żadnych funkcji poza czystą arytmetyką i logiką, może być używane również w C lub innych językach.
Jim Pivarski
1

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.

Thomas Jung
źródło
Zawodzi również, gdy przepełnienie powoduje idealną pętlę.
Stefan Kendall
Czy masz przykład tego, co miałeś na myśli?
Thomas Jung
Właśnie napisałem mały test: użycie BigInteger jest 6 razy wolniejsze niż użycie tego podejścia do dzielenia. Zakładam więc, że dodatkowe sprawdzenie skrzynek narożnych jest tego warte pod względem wydajności.
mhaller
Nie wiem zbyt wiele o kompilatorach java, ale wyrażenie takie jak a * b / bprawdopodobnie zostanie zoptymalizowane tylko aw wielu innych kontekstach.
SingleNegationElimination
TokenMacGuy - nie można go tak zoptymalizować, jeśli istnieje niebezpieczeństwo przepełnienia.
Tom Hawtin - tackline
1

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;
    }
}
dfa
źródło
Nie pomoże, jak jeden z operandów long.
Tom Hawtin - tackline
1
Czy w ogóle to przetestowałeś? W przypadku dużych, ale nie przepełnionych wartości a & b zakończy się to niepowodzeniem z powodu błędów zaokrąglania w podwójnej wersji mnożenia (spróbuj np. 123456789123L i 74709314L). Jeśli nie rozumiesz arytmetyki maszynowej, odgadnięcie odpowiedzi na tego rodzaju precyzyjne pytanie jest gorsze niż jej brak, ponieważ wprowadzi ludzi w błąd.
Rich
-1

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)

xuan
źródło