Умножение двух целочисленных переполнений приводит к отрицательному числу

Question

Рассмотрим этот фрагмент из спецификации языка Java.

class Test {
    public static void main(String[] args) {
        int i = 1000000;
        System.out.println(i * i);
        long l = i;
        System.out.println(l * l);
    }
}

Выход

-727379968
1000000000000

Почему результат -727379968 для (i*i)? В идеале это должно быть 1000000000000.

Я знаю, что диапазон целых чисел составляет от –2147483648 до 2147483647. Поэтому очевидно, 1000000000000 не находится в данном диапазоне.

Почему результат становится -727379968?

Answer 1

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

Answer 2

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

Что касается причины, по которой это так в языке Java, то, как всегда, это компромисс между простотой дизайна языка и производительностью. Но в Java головоломках (головоломка 3) авторы критикуют тот факт, что переполнения в Java молчат:

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

Answer 3

Некоторые другие ответы правильно объясняют, почему это происходит (т. Е. Двоичная логика комплимента со знаком двух).

Фактическое решение проблемы и как получить правильный ответ в Java при использовании действительно больших чисел - это использовать класс BigInteger, который также работает для длинных значений.

package com.craigsdickson.scratchpad;

import java.math.BigInteger;

public class BigIntegerExample {

    public static void main(String[] args) {

        int bigInt = Integer.MAX_VALUE;
        // prints incorrect answer
        System.out.println(bigInt * bigInt);

        BigInteger bi = BigInteger.valueOf(bigInt);
        // prints correct answer
        System.out.println(bi.multiply(bi));

        long bigLong = Long.MAX_VALUE;
        // prints incorrect answer
        System.out.println(bigLong * bigLong);

        BigInteger bl = BigInteger.valueOf(bigLong);
        // prints correct answer
        System.out.println(bl.multiply(bl));

    }

}

Answer 4

Давайте посмотрим на двоичный файл:

1000000 - это 1111 0100 0010 0100 0000.
1000000000000 - это 1110 1000 1101 0100 1010 0101 0001 0000 0000 0000

Однако первые две секции по 4 бита не будутпоместите в int (поскольку int имеет ширину 32 бита в Java), и поэтому они отбрасываются, оставляя только 1101 0100 1010 0101 0001 0000 0000 0000, что составляет -727379968.

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

Answer 5

Причины возникновения целочисленного переполнения уже были объяснены в других ответах.

Практический способ обеспечить длинную арифметику в вычислениях - это использовать числовые литералы с суффиксом l, которые объявляют литералы как long.

Обычное целочисленное умножение, которое переполняется:

jshell> 100000 * 100000
$1 ==> -727379968

Умножение, где один из мультипликатов имеет суффикс l, который не переполняется:

jshell> 100000 * 100000l
$1 ==> 1000000000000

Обратите внимание, что long s также подвержены переполнению, но диапазон намного больше, от -9,223,372,036,854,775,808 до 9,223,372,036,854,775,807.