Jak Java radzi sobie z niedopełnieniami i przepełnieniami liczb całkowitych i jak byś to sprawdził?

Jak Java radzi sobie z niedopełnieniami i przepełnieniami liczb całkowitych?

W następnej kolejności, jak byś sprawdził / przetestował, że to się dzieje?

Jeśli się przepełni, wraca do wartości minimalnej i kontynuuje od tego momentu . Jeśli się przepełni, wraca do wartości maksymalnej i kontynuuje od tego momentu .

Możesz to wcześniej sprawdzić w następujący sposób:

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

(możesz zastąpić intprzez, longaby wykonać te same kontrole long)

Jeśli uważasz, że może się to zdarzyć częściej niż często, rozważ użycie typu danych lub obiektu, który może przechowywać większe wartości, np . A longmoże java.math.BigInteger. Ostatnia nie przepełnia się, praktycznie dostępna pamięć JVM jest limitem.

Jeśli zdarzyło ci się już korzystać z Java8, możesz skorzystać z nowych Math#addExact()i Math#subtractExact()metod, które spowodują ArithmeticExceptionprzepełnienie.

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

Kod źródłowy można znaleźć odpowiednio tutaj i tutaj .

Oczywiście możesz też od razu ich użyć zamiast ukrywać je w booleanmetodzie użytecznej.

Cóż, jeśli chodzi o prymitywne typy liczb całkowitych, Java wcale nie obsługuje Over / Underflow (dla float i double zachowanie jest inne, będzie spłukiwać do +/- nieskończoności, tak jak nakazuje IEEE-754).

Dodanie dwóch liczb całkowitych nie spowoduje, że nastąpi przepełnienie. Prostą metodą sprawdzenia przepełnienia jest użycie następnego większego typu do faktycznego wykonania operacji i sprawdzenie, czy wynik jest nadal w zakresie dla typu źródłowego:

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

To, co byś zrobił zamiast klauzul dotyczących rzucania, zależy od wymagań aplikacji (rzucaj, spłucz do min / maks lub po prostu rejestruj cokolwiek). Jeśli chcesz wykryć przepełnienie przy długich operacjach, nie masz szczęścia z prymitywami, zamiast tego użyj BigInteger.

Edycja (2014-05-21): Ponieważ wydaje się, że do tego pytania często się powołuje i sam musiałem rozwiązać ten sam problem, dość łatwo jest ocenić stan przepełnienia tą samą metodą, którą CPU obliczy swoją flagę V.

Jest to w zasadzie wyrażenie boolowskie, które obejmuje znak zarówno operandów, jak i wynik:

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

W Javie łatwiej jest zastosować wyrażenie (w if) do całych 32 bitów i sprawdzić wynik, używając <0 (to skutecznie przetestuje bit znaku). Zasada działa dokładnie tak samo dla wszystkich typów pierwotnych liczb całkowitych , zmiana wszystkich deklaracji w powyższej metodzie na długą powoduje, że działa ona długo.

W przypadku mniejszych typów, ze względu na niejawną konwersję na int (szczegóły w JLS dla operacji bitowych), zamiast sprawdzania <0, czek musi jawnie maskować bit znaku (0x8000 dla krótkich argumentów, 0x80 dla bajtów, dostosuj rzutowania i deklaracja parametru odpowiednio):

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

(Należy zauważyć, że powyższy przykład wykorzystuje potrzebę ekspresji dla odjąć wykrywania przelewowego)

Jak więc / dlaczego działają te wyrażenia logiczne? Po pierwsze, niektóre logiczne myślenie ujawnia, że ​​przepełnienie może wystąpić tylko wtedy, gdy znaki obu argumentów są takie same. Ponieważ, jeśli jeden argument jest ujemny, a jeden dodatni, wynik (dodawania) musi być bliższy zeru, lub w skrajnym przypadku jeden argument jest zerowy, taki sam jak drugi argument. Ponieważ same argumenty nie mogą stworzyć warunku przepełnienia, ich suma nie może również spowodować przepełnienia.

Co się stanie, jeśli oba argumenty będą miały ten sam znak? Przyjrzyjmy się, że oba są dodatnie: dodanie dwóch argumentów, które tworzą sumę większą niż typy MAX_VALUE, zawsze da wartość ujemną, więc przepełnienie występuje, jeśli arg1 + arg2> MAX_VALUE. Teraz maksymalna wartość, która mogłaby wynikać, to MAX_VALUE + MAX_VALUE (skrajny przypadek obu argumentów to MAX_VALUE). W przypadku bajtu (przykład) oznaczałoby to 127 + 127 = 254. Patrząc na reprezentacje bitowe wszystkich wartości, które mogą wynikać z dodania dwóch wartości dodatnich, można stwierdzić, że wszystkie te, które przepełniają (128 do 254), mają ustawiony bit 7, podczas gdy wszystkie nie przepełnione (od 0 do 127) mają wyczyszczony bit 7 (najwyższy, znak). Dokładnie to sprawdza pierwsza (prawa) część wyrażenia:

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

(~ s & ~ d & r) staje się prawdą, tylko jeśli oba operandy (s, d) są dodatnie, a wynik (r) jest ujemny (wyrażenie działa na wszystkich 32 bitach, ale jedynym bitem, który nas interesuje to najwyższy bit (znak), który jest sprawdzany przez <0).

Teraz, jeśli oba argumenty są ujemne, ich suma nigdy nie może być bliższa zeru niż którykolwiek z argumentów, suma musi być bliższa minus nieskończoności. Najbardziej ekstremalną wartością, jaką możemy wytworzyć, jest MIN_VALUE + MIN_VALUE, co (ponownie dla przykładu bajtu) pokazuje, że dla dowolnej wartości z zakresu (-1 do -128) bit znaku jest ustawiony, a każda możliwa przepełniona wartość (-129 do -256 ) ma wyczyszczony bit znaku. Zatem znak wyniku ponownie pokazuje stan przepełnienia. To właśnie sprawdza lewa połowa (s & d & ~ r) w przypadku, gdy oba argumenty (s, d) są ujemne, a wynik jest dodatni. Logika jest w dużej mierze równoważna z przypadkiem pozytywnym; wszystkie wzorce bitowe, które mogą wynikać z dodania dwóch wartości ujemnych, będą wyczyszczone bity znaku, jeśli i tylko w przypadku wystąpienia niedopełnienia.

Domyślnie int i długa matematyka Javy po cichu owija się przy przepełnieniu i niedopełnieniu. (Operacje na liczbach całkowitych na innych typach liczb całkowitych są wykonywane przez promowanie operandów jako int lub long, zgodnie z JLS 4.2.2 .)

Jak Java 8, java.lang.Mathzapewnia addExact, subtractExact, multiplyExact, incrementExact, decrementExacti negateExactstatyczne metody zarówno dla int i długich argumentów, które wykonują pracę w nazwie, rzucając ArithmeticException na przepełnienie. (Nie ma metody divideExact - sam musisz sprawdzić jeden specjalny przypadek ( MIN_VALUE / -1).)

Począwszy od Java 8, java.lang.Math zapewnia także toIntExactrzutowanie wartości int na wartość int, rzucając ArithmeticException, jeśli wartość parametru long nie mieści się w wartości int. Może to być przydatne np. Do obliczenia sumy liczb całkowitych przy użyciu niezaznaczonej długiej matematyki, a następnie użycia toIntExactrzutowania na liczbę całkowitą na końcu (ale uważaj, aby nie przelać sumy).

Jeśli nadal używasz starszej wersji Java, Google Guava zapewnia statyczne metody IntMath i LongMath do sprawdzania dodawania, odejmowania, mnożenia i potęgowania (wyrzucanie przy przepełnieniu). Klasy te zapewniają również metody obliczania silni i współczynników dwumianowych, które zwracają się MAX_VALUEpo przepełnieniu (co jest mniej wygodne do sprawdzenia). Pierwotne użytecznych klas guawy, w SignedBytes, UnsignedBytes, Shortsi Intsdostarczają checkedCastmetody zwężenie większych typów (rzucania IllegalArgumentException na mocy / przelewem, nie ArithmeticException), jak również saturatingCastmetody powrotne MIN_VALUElub MAX_VALUEna przepełnienie.

Java nie robi nic z przepełnieniem liczb całkowitych dla typów pierwotnych int lub długich i ignoruje przepełnienie dodatnimi i ujemnymi liczbami całkowitymi.

Ta odpowiedź najpierw opisuje przepełnienie liczb całkowitych, podaje przykład, jak to może się zdarzyć, nawet przy wartościach pośrednich w ocenie wyrażenia, a następnie podaje linki do zasobów, które zapewniają szczegółowe techniki zapobiegania przepełnieniu liczb całkowitych i wykrywania ich.

Arytmetyka liczb całkowitych i wyrażenia będące wynikiem nieoczekiwanego lub niewykrytego przepełnienia są częstym błędem programowania. Nieoczekiwane lub niewykryte przepełnienie liczb całkowitych jest również dobrze znanym problemem bezpieczeństwa, który można wykorzystać, zwłaszcza, że ​​wpływa na obiekty tablic, stosów i list.

Przepełnienie może wystąpić w kierunku dodatnim lub ujemnym, gdzie wartość dodatnia lub ujemna byłaby wyższa niż wartości maksymalne lub minimalne dla danego typu pierwotnego. Przepełnienie może wystąpić w wartości pośredniej podczas oceny wyrażenia lub operacji i wpłynąć na wynik wyrażenia lub operacji, w przypadku gdy oczekiwana wartość końcowa będzie w zakresie.

Czasami przepełnienie ujemne jest błędnie nazywane niedopełnieniem. Niedomiar występuje wtedy, gdy wartość byłaby bliższa zeru, niż pozwala na to reprezentacja. Niedomiar występuje w arytmetyce liczb całkowitych i jest oczekiwany. Niedopełnienie liczb całkowitych występuje, gdy ocena liczb całkowitych będzie wynosić od -1 do 0 lub 0 i 1. To, co będzie ułamkowym wynikiem, zostanie obcięte do 0. Jest to normalne i oczekiwane z arytmetyką liczb całkowitych i nie jest uważane za błąd. Może to jednak prowadzić do zgłoszenia wyjątku przez kod. Jednym z przykładów jest wyjątek „ArithmeticException: / by zero”, jeśli wynik niedopełnienia liczby całkowitej jest używany jako dzielnik w wyrażeniu.

Rozważ następujący kod:

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

co powoduje, że x ma przypisane 0, a następnie ocena bigValue / x zgłasza wyjątek, „ArithmeticException: / by zero” (tzn. dzielenie przez zero), zamiast y przypisano wartość 2.

Oczekiwany wynik dla x wyniósłby 858 993 458, czyli mniej niż maksymalna wartość int wynosząca 2 147 483 647. Jednak wynik pośredni z oceny liczby całkowitej.MAX_Value * 2 wyniósłby 4 294 967 294, co przekracza maksymalną wartość całkowitą i wynosi -2 zgodnie z reprezentacjami liczb całkowitych dopełniających 2s. Kolejna ocena -2 / 5 daje wynik 0, który zostaje przypisany do x.

Zmiana kolejności wyrażenia do obliczenia x na wyrażenie, które po obliczeniu dzieli się przed pomnożeniem, następujący kod:

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

skutkuje przypisaniem x 858,993,458 iy przypisaniem 2, co jest oczekiwane.

Wynik pośredni z bigValue / 5 wynosi 429,496,729, co nie przekracza maksymalnej wartości int. Późniejsza ocena 429,496,729 * 2 nie przekracza maksymalnej wartości int, a oczekiwany wynik zostaje przypisany do x. Ocena dla y nie dzieli się przez zero. Oceny dla xiy działają zgodnie z oczekiwaniami.

Wartości całkowite Java są przechowywane jako i zachowują się zgodnie z uzupełnieniami 2-częściowymi podpisanymi reprezentacjami liczb całkowitych. Gdy wynikowa wartość byłaby większa lub mniejsza od maksymalnej lub minimalnej wartości całkowitej, zamiast tego otrzymywana jest wartość całkowita 2 z uzupełnieniem. W sytuacjach, które nie zostały wyraźnie zaprojektowane do użycia zachowania uzupełnienia 2s, co jest najczęstszą sytuacją arytmetyczną na liczbach całkowitych, wynikowa wartość uzupełnienia 2s spowoduje błąd logiki programowania lub błąd obliczeniowy, jak pokazano w powyższym przykładzie. Doskonały artykuł w Wikipedii opisuje komplementarne liczby całkowite 2s tutaj: Uzupełnienie dwóch - Wikipedia

Istnieją techniki pozwalające uniknąć niezamierzonego przepełnienia liczb całkowitych. Techniki można sklasyfikować jako wykorzystujące testy warunków wstępnych, upcasting i BigInteger.

Testowanie warunków wstępnych polega na sprawdzeniu wartości przechodzących w operację lub wyrażenie arytmetyczne, aby upewnić się, że nie nastąpi przepełnienie tymi wartościami. Programowanie i projektowanie będą musiały utworzyć testy, które zapewnią, że wartości wejściowe nie spowodują przepełnienia, a następnie określą, co zrobić, jeśli wystąpią wartości wejściowe, które spowodują przepełnienie.

Upcasting obejmuje użycie większego typu pierwotnego do wykonania operacji arytmetycznej lub wyrażenia, a następnie ustalenie, czy wynikowa wartość przekracza wartości maksymalne lub minimalne dla liczby całkowitej. Nawet w przypadku upcastingu nadal możliwe jest, że wartość lub jakaś wartość pośrednia w operacji lub wyrażeniu będzie przekraczać maksymalne lub minimalne wartości dla typu upcast i spowoduje przepełnienie, które również nie zostanie wykryte i spowoduje nieoczekiwane i niepożądane wyniki. Dzięki analizie lub warunkom wstępnym może być możliwe zapobieganie przepełnieniu dzięki upcastingowi, gdy zapobieganie bez upcastingu nie jest możliwe lub praktyczne. Jeśli liczby całkowite są już długimi typami pierwotnymi, upcasting nie jest możliwy w przypadku typów pierwotnych w Javie.

Technika BigInteger polega na użyciu BigInteger do operacji arytmetycznej lub wyrażenia przy użyciu metod bibliotecznych wykorzystujących BigInteger. BigInteger nie przepełnia się. W razie potrzeby wykorzysta całą dostępną pamięć. Jego metody arytmetyczne są zwykle tylko nieco mniej wydajne niż operacje na liczbach całkowitych. Nadal możliwe jest, że wynik wykorzystujący BigInteger może przekraczać wartości maksymalne lub minimalne dla liczby całkowitej, jednak przepełnienie nie wystąpi w arytmetyce prowadzącej do wyniku. Programowanie i projektowanie będą nadal musiały określić, co zrobić, jeśli wynik BigInteger przekroczy maksymalne lub minimalne wartości dla pożądanego pierwotnego typu wyniku, np. Int lub long.

Program CERT Carnegie Mellon Software Engineering Institute i Oracle stworzyły zestaw standardów bezpiecznego programowania Java. Standardy obejmują techniki zapobiegania i wykrywania przepełnienia liczb całkowitych. Standard został opublikowany tutaj jako ogólnodostępny zasób online: CERT Oracle Secure Coding Standard for Java

Sekcja standardu, która opisuje i zawiera praktyczne przykłady technik kodowania w celu zapobiegania lub wykrywania przepełnienia liczb całkowitych, jest tutaj: NUM00-J. Wykryj lub zapobiegaj przepełnieniu liczb całkowitych

Dostępne są również formularze książkowe i PDF w CERT Oracle Secure Coding Standard for Java.

Po tym, jak sam wpadłem na ten problem, oto moje rozwiązanie (zarówno dla mnożenia, jak i dodawania):

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

nie krępuj się poprawić, jeśli jest źle lub jeśli można to uprościć. Przeprowadziłem pewne testy z wykorzystaniem metody mnożenia, głównie przypadków na krawędziach, ale nadal może być źle.

Istnieją biblioteki, które zapewniają bezpieczne operacje arytmetyczne, które sprawdzają przepełnienie / niedopełnienie liczb całkowitych. Na przykład GuMa IntMath.checkedAdd (int a, int b) zwraca sumę ai b, pod warunkiem, że się nie przepełnia, i wyrzuca, ArithmeticExceptionjeśli a + bprzepełnia się intarytmetyką ze znakiem.

Owija się wokół.

na przykład:

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

odciski

-2147483648
2147483647

Myślę, że powinieneś użyć czegoś takiego i nazywa się to 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;
}

Możesz przeczytać więcej tutaj: Wykryj lub zapobiegaj przepełnieniu liczb całkowitych

Jest to dość wiarygodne źródło.

Nic nie robi - po prostu zdarza się niedopełnienie / przepełnienie.

„-1”, które jest wynikiem przepełnionego obliczenia, nie różni się od „-1” wynikającego z innych informacji. Nie możesz więc stwierdzić za pomocą jakiegoś statusu lub sprawdzając tylko wartość, czy jest przepełniona.

Ale możesz być mądry w swoich obliczeniach, aby uniknąć przepełnienia, jeśli ma to znaczenie, lub przynajmniej wiedzieć, kiedy to nastąpi. Jaka jest twoja sytuacja

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

Myślę, że powinno być dobrze.

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

Jest jeden przypadek, o którym nie wspomniano powyżej:

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

}
System.out.println(res);

będzie produkować:

0

Przypadek ten omówiono tutaj: Przepełnienie liczb całkowitych powoduje wyzerowanie.