Перейти к основному содержимому

Переполнение и недополнение в Java

· 9 мин. чтения

Задача: Наибольшая подстрока палиндром

Для заданной строки s, верните наибольшую подстроку палиндром входящую в s. Подстрока — это непрерывная непустая последовательность символов внутри строки. Стока является палиндромом, если она читается одинаково в обоих направлениях...

ANDROMEDA 42

1. Введение

В этом руководстве мы рассмотрим переполнение и потерю значимости числовых типов данных в Java.

Мы не будем углубляться в более теоретические аспекты — мы просто сосредоточимся на том, когда это происходит в Java.

Сначала мы рассмотрим целочисленные типы данных, а затем типы данных с плавающей запятой. Для обоих мы также увидим, как мы можем определить, когда происходит переполнение или недостаточный объем.

2. Переполнение и недополнение

Проще говоря, переполнение и потеря значимости происходят, когда мы присваиваем значение, выходящее за пределы объявленного типа данных переменной.

Если (абсолютное) значение слишком велико, мы называем это переполнением, если значение слишком мало, мы называем это недостатком.

Давайте рассмотрим пример, в котором мы пытаемся присвоить значение 10 1000 ( 1 с 1000 нулей) переменной типа int или double . Значение слишком велико для переменной типа int или double в Java, и произойдет переполнение.

В качестве второго примера предположим, что мы пытаемся присвоить значение 10-1000 (что очень близко к 0) переменной типа double . Это значение слишком мало для двойной переменной в Java, и будет потеря значимости.

Давайте посмотрим, что происходит в Java в этих случаях более подробно.

3. Целочисленные типы данных

Целочисленные типы данных в Java: byte (8 бит), short (16 бит), int (32 бита) и long (64 бита).

Здесь мы сосредоточимся на типе данных int . То же самое относится и к другим типам данных, за исключением того, что минимальное и максимальное значения различаются.

Целое число типа int в Java может быть отрицательным или положительным, что означает, что с его 32 битами мы можем присваивать значения от -2 31 ( -2147483648 ) до 2 31 -1 ( 2147483647 ).

Класс-оболочка Integer определяет две константы, которые содержат эти значения: Integer.MIN_VALUE и Integer.MAX_VALUE .

3.1. Пример

Что произойдет, если мы определим переменную m типа int и попытаемся присвоить ей слишком большое значение (например, 21474836478 = MAX_VALUE + 1)?

Возможным результатом этого присвоения является то, что значение m будет неопределенным или возникнет ошибка.

Оба являются действительными результатами; однако в Java значение m будет равно -2 147 483 648 (минимальное значение). С другой стороны, если мы попытаемся присвоить значение -2147483649 ( = MIN_VALUE – 1 ), m будет равно 2147483647 (максимальное значение). Такое поведение называется целочисленным переносом.

Давайте рассмотрим следующий фрагмент кода, чтобы лучше проиллюстрировать это поведение:

int value = Integer.MAX_VALUE-1;
for(int i = 0; i < 4; i++, value++) {
System.out.println(value);
}

Мы получим следующий вывод, демонстрирующий переполнение:

2147483646
2147483647
-2147483648
-2147483647

4. Обработка недополнения и переполнения целочисленных типов данных

Java не генерирует исключение при переполнении; поэтому может быть трудно найти ошибки, возникающие в результате переполнения. Мы также не можем получить прямой доступ к флагу переполнения, который имеется в большинстве процессоров.

Однако существуют различные способы обработки возможного переполнения. Давайте рассмотрим несколько таких возможностей.

4.1. Используйте другой тип данных

Если мы хотим разрешить значения больше 2147483647 (или меньше -2147483648 ), мы можем просто использовать вместо этого тип данных long или BigInteger .

Хотя переменные типа long также могут переполняться, минимальное и максимальное значения намного больше и, вероятно, достаточны в большинстве ситуаций.

Диапазон значений BigInteger не ограничен, за исключением объема памяти, доступной для JVM.

Давайте посмотрим, как переписать наш приведенный выше пример с BigInteger :

BigInteger largeValue = new BigInteger(Integer.MAX_VALUE + "");
for(int i = 0; i < 4; i++) {
System.out.println(largeValue);
largeValue = largeValue.add(BigInteger.ONE);
}

Мы увидим следующий вывод:

2147483647
2147483648
2147483649
2147483650

Как видно из вывода, здесь нет переполнения. В нашей статье BigDecimal и BigInteger в Java BigInteger рассматривается более подробно.

4.2. Выбросить исключение

Бывают ситуации, когда мы не хотим допускать больших значений и не хотим, чтобы произошло переполнение, и вместо этого мы хотим создать исключение.

Начиная с Java 8, мы можем использовать методы для точных арифметических операций. Сначала рассмотрим пример:

int value = Integer.MAX_VALUE-1;
for(int i = 0; i < 4; i++) {
System.out.println(value);
value = Math.addExact(value, 1);
}

Статический метод addExact() выполняет обычное сложение, но выдает исключение, если операция приводит к переполнению или потере значимости:

2147483646
2147483647
Exception in thread "main" java.lang.ArithmeticException: integer overflow
at java.lang.Math.addExact(Math.java:790)
at foreach.underoverflow.OverUnderflow.main(OverUnderflow.java:115)

В дополнение к addExact() пакет Math в Java 8 предоставляет соответствующие точные методы для всех арифметических операций. См. документацию по Java для получения списка всех этих методов.

Кроме того, существуют точные методы преобразования, которые выдают исключение, если во время преобразования в другой тип данных происходит переполнение.

Для преобразования из long в int :

public static int toIntExact(long a)

И для преобразования из BigInteger в int или long :

BigInteger largeValue = BigInteger.TEN;
long longValue = largeValue.longValueExact();
int intValue = largeValue.intValueExact();

4.3. До Java 8

Точные арифметические методы были добавлены в Java 8. Если мы используем более раннюю версию, мы можем просто создать эти методы сами. Один из вариантов сделать это — реализовать тот же метод, что и в Java 8:

public static int addExact(int x, int y) {
int r = x + y;
if (((x ^ r) & (y ^ r)) < 0) {
throw new ArithmeticException("int overflow");
}
return r;
}

5. Нецелочисленные типы данных

Нецелочисленные типы float и double ведут себя не так, как целые типы данных, когда речь идет об арифметических операциях.

Одно отличие состоит в том, что арифметические операции над числами с плавающей запятой могут привести к NaN . У нас есть специальная статья о NaN в Java , поэтому в этой статье мы не будем углубляться в это. Кроме того, в пакете Math нет точных арифметических методов, таких как addExact или multipleExact для нецелочисленных типов . ``

Java следует стандарту IEEE для арифметики с плавающей запятой (IEEE 754) для своих типов данных float и double . Этот стандарт является основой для того, как Java обрабатывает переполнения и потери значимости чисел с плавающей запятой.

В следующих разделах мы сосредоточимся на переполнении и недостатке данных типа double и на том, что мы можем сделать, чтобы справиться с ситуациями, в которых они возникают.

5.1. Переполнение

Что касается целочисленных типов данных, мы можем ожидать, что:

assertTrue(Double.MAX_VALUE + 1 == Double.MIN_VALUE);

Однако это не относится к переменным с плавающей запятой. Верно следующее:

assertTrue(Double.MAX_VALUE + 1 == Double.MAX_VALUE);

Это связано с тем, что значение типа double имеет ограниченное число значащих битов . Если мы увеличим значение большого двойного значения только на единицу, мы не изменим ни один из значащих битов. Поэтому значение остается прежним.

Если мы увеличим значение нашей переменной так, что мы увеличим один из значащих битов переменной, переменная будет иметь значение INFINITY :

assertTrue(Double.MAX_VALUE * 2 == Double.POSITIVE_INFINITY);

и NEGATIVE_INFINITY для отрицательных значений:

assertTrue(Double.MAX_VALUE * -2 == Double.NEGATIVE_INFINITY);

Мы видим, что, в отличие от целых чисел, здесь нет переноса, а есть два разных возможных результата переполнения: значение остается прежним или мы получаем одно из специальных значений, POSITIVE_INFINITY или NEGATIVE_INFINITY .

5.2. недолив

Для минимальных значений двойного значения определены две константы: MIN_VALUE (4.9e-324) и MIN_NORMAL (2.2250738585072014E-308).

Стандарт IEEE для арифметики с плавающей запятой (IEEE 754) более подробно объясняет различия между ними.

Давайте сосредоточимся на том, почему нам вообще нужно минимальное значение для чисел с плавающей запятой.

Двойное значение не может быть произвольно маленьким, поскольку у нас есть только ограниченное количество битов для представления значения.

Глава о типах, значениях и переменных в спецификации языка Java SE описывает, как представляются типы с плавающей запятой. Минимальный показатель степени для двоичного представления двойного числа задается как -1074 . Это означает, что наименьшее положительное значение, которое может иметь двойное значение, равно Math.pow(2, -1074) , что равно 4.9e-324 .

Как следствие, точность числа double в Java не поддерживает значения от 0 до 4.9e-324 или от -4.9e-324 до 0 для отрицательных значений.

Так что же произойдет, если мы попытаемся присвоить слишком маленькое значение переменной типа double ? Давайте посмотрим на пример:

for(int i = 1073; i <= 1076; i++) {
System.out.println("2^" + i + " = " + Math.pow(2, -i));
}

С выходом:

2^1073 = 1.0E-323
2^1074 = 4.9E-324
2^1075 = 0.0
2^1076 = 0.0

Мы видим, что если мы присвоим слишком маленькое значение, мы получим потерю значимости, и результирующее значение равно 0,0 (положительный ноль).

Точно так же для отрицательных значений потеря значимости приведет к значению -0,0 (отрицательный ноль).

6. Обнаружение недополнения и переполнения типов данных с плавающей запятой

Поскольку переполнение приведет либо к положительной, либо к отрицательной бесконечности, а потеря значимости к положительному или отрицательному нулю, нам не нужны точные арифметические методы, как для целочисленных типов данных. Вместо этого мы можем проверить эти специальные константы для обнаружения переполнения и потери значимости.

Если мы хотим сгенерировать исключение в этой ситуации, мы можем реализовать вспомогательный метод. Давайте посмотрим, как это может выглядеть для возведения в степень:

public static double powExact(double base, double exponent) {
if(base == 0.0) {
return 0.0;
}

double result = Math.pow(base, exponent);

if(result == Double.POSITIVE_INFINITY ) {
throw new ArithmeticException("Double overflow resulting in POSITIVE_INFINITY");
} else if(result == Double.NEGATIVE_INFINITY) {
throw new ArithmeticException("Double overflow resulting in NEGATIVE_INFINITY");
} else if(Double.compare(-0.0f, result) == 0) {
throw new ArithmeticException("Double overflow resulting in negative zero");
} else if(Double.compare(+0.0f, result) == 0) {
throw new ArithmeticException("Double overflow resulting in positive zero");
}

return result;
}

В этом методе нам нужно использовать метод Double.compare() . Обычные операторы сравнения ( < и > ) не различают положительный и отрицательный нуль.

7. Положительный и отрицательный ноль

Наконец, давайте рассмотрим пример, который показывает, почему нам нужно быть осторожными при работе с положительными и отрицательными нулями и бесконечностью.

Давайте определим пару переменных для демонстрации:

double a = +0f;
double b = -0f;

Поскольку положительный и отрицательный 0 считаются равными:

assertTrue(a == b);

Принимая во внимание, что положительная и отрицательная бесконечность считаются разными:

assertTrue(1/a == Double.POSITIVE_INFINITY);
assertTrue(1/b == Double.NEGATIVE_INFINITY);

Однако верно следующее утверждение:

assertTrue(1/a != 1/b);

Что кажется противоречащим нашему первому утверждению.

8. Заключение

В этой статье мы увидели, что такое переполнение и потеря памяти, как это может произойти в Java и в чем разница между целыми типами данных и типами данных с плавающей запятой.

Мы также увидели, как мы можем обнаруживать переполнение и потерю памяти во время выполнения программы.

Как обычно, полный исходный код доступен на Github .