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 a
i b
są 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: a
i b
zawsze są nieujemne w moim scenariuszu.
java
math
long-integer
integer-overflow
Steve McLeod
źródło
źródło
Odpowiedzi:
Java 8 ma
Math.multiplyExact
,Math.addExact
itd. Za wskazówki i długie. Te rzucają niesprawdzoneArithmeticException
na przepełnienie.źródło
Jeśli
a
ib
to zarówno pozytywne, wówczas można użyć:Jeśli musisz radzić sobie zarówno z liczbami dodatnimi, jak i ujemnymi, jest to bardziej skomplikowane:
Oto mały stolik, który podniosłem, aby to sprawdzić, udając, że przepełnienie ma miejsce przy -10 lub +10:
źródło
n
,n > x
jest taki sam jakn > floor(x)
. Dla dodatnich liczb całkowitych dzielenie ma niejawne piętro. (W przypadku liczb ujemnych zaokrągla się w górę)a = -1
ib = 10
, zobacz moją odpowiedź poniżej.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
a
ib
, pod warunkiem, że nie przepełnia, i zgłasza,ArithmeticException
jeślia * b
przepełnia się wlong
arytmetyce ze znakiem.źródło
Możesz zamiast tego użyć java.math.BigInteger i sprawdzić rozmiar wyniku (kod nie został przetestowany):
źródło
Użyj logarytmów, aby sprawdzić rozmiar wyniku.
źródło
ceil(log(a)) + ceil(log(b)) > log(Long.MAX)
:?Czy Java ma coś takiego jak int.MaxValue? Jeśli tak, spróbuj
edit: widziano Long.MAX_VALUE w pytaniu
źródło
Math.Abs(a)
nie działa, jeślia
takLong.MIN_VALUE
.Oto najprostszy sposób, jaki przychodzi mi do głowy
źródło
Skradziony z jrub
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:
Zwróć uwagę, że spowoduje to wyłapanie niektórych przepełnień bez podziału.
źródło
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.Math
klasy.Math.multiplyExact(long, long)
http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/lang/Math.java#l925Math.addExact(long, long)
http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/lang/Math.java#l830itd itd.
AKTUALIZACJA: zmieniono nieprawidłowe linki do stron internetowych osób trzecich na linki do repozytoriów Mercurial Open JDK.
źródło
Nie jestem pewien, dlaczego nikt nie szuka rozwiązania takiego jak:
Wybierz jedną, aby była większa z dwóch liczb.
źródło
a
jest większy czy mniejszy?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ściMIN_VALUE == -MAX_VALUE - 1
.Po zastosowaniu do prawdziwych
MIN_VALUE
iMAX_VALUE
, odpowiedź Johna Kugelmana daje przypadek przepełnienia kiedya == -1
ib ==
cokolwiek innego (punkt podniesiony najpierw przez Kyle'a). Oto sposób, aby to naprawić:Nie jest to ogólne rozwiązanie dla każdego
MIN_VALUE
aMAX_VALUE
, ale to ogólnie dla JavyLong
iInteger
oraz każda wartośća
ib
.źródło
MIN_VALUE = -MAX_VALUE - 1
, gdy nie ma innego przypadku (w tym przykładowego przypadku testowego). Musiałbym dużo zmienić.Może:
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.
źródło
a * b / b
prawdopodobnie zostanie zoptymalizowane tylkoa
w wielu innych kontekstach.może to ci pomoże:
źródło
long
.c / c ++ (long * long):
java (int * int, przepraszam, nie znalazłem int64 w java):
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)
źródło