Руководство по Java BigInteger

1. Введение

Java предоставляет некоторые примитивы, такие как int или long , для выполнения целочисленных операций. Но иногда нам нужно хранить числа, которые превышают доступные ограничения для этих типов данных.

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

2. Класс BigInteger

Как мы знаем, класс BigInteger используется для математических операций, включающих вычисления очень больших целых чисел, больших, чем примитивный тип long . Он представляет неизменяемые целые числа произвольной точности .

Прежде чем идти дальше, давайте вспомним, что в Java все байты представлены в системе с дополнением до двух с использованием нотации с прямым порядком байтов . Он хранит старший байт слова по наименьшему адресу памяти (наименьший индекс). Более того, первый бит байта также является битом знака. Давайте проверим примерные значения байтов:

• 1000 0000 представляет -128
• 0111 1111 представляет 127
• 1111 1111 представляет -1

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

2.1. инт сигнум

Свойство signum определяет знак `` BigInteger . Три целых числа представляют знак значения: -1 для отрицательных чисел, 0 для нуля, 1 для положительных чисел:

assertEquals(1, BigInteger.TEN.signum());
assertEquals(-1, BigInteger.TEN.negate().signum());
assertEquals(0, BigInteger.ZERO.signum());

Следует помнить, что BigInteger.ZERO должен иметь сигнум 0 из -за массива величин. Это значение гарантирует, что для каждого значения BigInteger существует ровно одно представление `` .

2.2. int[] маг

Вся магия класса BigInteger начинается со свойства mag . Он хранит заданное значение в массиве, используя двоичное представление , что позволяет опустить ограничения примитивных типов данных.

Более того, BigInteger группирует их в 32-битные порции — набор из четырех байтов. Из-за этого величина внутри определения класса объявляется как массив int :

int[] mag;

Этот массив содержит величину заданного значения в записи с обратным порядком байтов . Нулевой элемент этого массива является самым значительным целым числом величины. Давайте проверим это с помощью BigInteger(byte[] bytes) :

assertEquals(new BigInteger("1"), new BigInteger(new byte[]{0b1}))
assertEquals(new BigInteger("2"), new BigInteger(new byte[]{0b10}))
assertEquals(new BigInteger("4"), new BigInteger(new byte[]{0b100}))

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

Поскольку существует переменная величины знака ( signum ), мы не используем первый бит в качестве бита знака значения . Давайте быстро проверим это:

byte[] bytes = { -128 }; // 1000 0000
assertEquals(new BigInteger("128"), new BigInteger(1, bytes));
assertEquals(new BigInteger("-128"), new BigInteger(-1, bytes));

Мы создали два разных значения, используя конструктор BigInteger(int signum, byte[] величина) . Он переводит представление величины знака в BigInteger. Мы повторно использовали тот же массив байтов, изменив только значение знака.

Мы также можем напечатать величину, используя метод toString(int radix) :

assertEquals("10000000", new BigInteger(1, bytes));
assertEquals("-10000000", new BigInteger(-1, bytes));

Обратите внимание, что к отрицательным значениям добавляется знак минус.

Наконец, наиболее значимое значение int должно быть ненулевым . Это означает, что BigInteger.ZERO имеет массив mag нулевой длины:

assertEquals(0, BigInteger.ZERO.bitCount()); 
assertEquals(BigInteger.ZERO, new BigInteger(0, new byte[]{}));

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

Давайте теперь перейдем к более сложным примерам и проверим, как BigInteger хранит числа в примитивных типах данных.

3. BigInteger больше, чем Long.MAX_VALUE.

Как мы уже знаем, тип данных long представляет собой 64-битное целое число с дополнением до двух . Signed long имеет минимальное значение -2 ^63 (1000 0000 … 0000) и максимальное значение 2 ^63 -1 (0111 1111 … 1111). Чтобы создать число, превышающее эти пределы, нам нужно использовать класс BigInteger .

Давайте теперь создадим значение на единицу больше, чем Long.MAX_VALUE , равное 2 ^63 . Согласно информации из предыдущей главы, он должен иметь:

• свойство signum установлено в 1,
• массив mag , всего 64 бита, где установлен только старший бит (1000 0000 … 0000).

Во-первых, давайте создадим BigInteger с помощью функции setBit(int n) :

BigInteger bi1 = BigInteger.ZERO.setBit(63);
String str = bi1.toString(2);
assertEquals(64, bi1.bitLength());
assertEquals(1, bi1.signum());
assertEquals("9223372036854775808", bi1.toString());
assertEquals(BigInteger.ONE, bi1.substract(BigInteger.valueOf(Long.MAX_VALUE)));

assertEquals(64, str.length());
assertTrue(str.matches("^10{63}$")); // 1000 0000 ... 0000

Помните, что в двоичной системе представления биты упорядочены справа налево, начиная с 0. В то время как BigInteger.ZERO имеет пустой массив величин, установка 63-го бита делает его одновременно и самым значащим — нулевым элементом массива. Массив 64 длины. Знак автоматически устанавливается равным единице .

С другой стороны, та же последовательность битов представлена Long.MIN_VALUE . Преобразуем эту константу в массив byte[] и создадим конструкцию BigInteger:

byte[] bytes = ByteBuffer.allocate(Long.BYTES).putLong(Long.MIN_VALUE).array();
BigInteger bi2 = new BigInteger(1, bytes);
assertEquals(bi1, bi2);
...

Как мы видим, оба значения равны, поэтому применяется один и тот же набор утверждений.

Наконец, мы можем проверить внутреннюю переменную int[] mag . В настоящее время Java не предоставляет API для получения этого значения, но мы можем сделать это с помощью инструмента оценки в нашем отладчике:

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

4. Вывод

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

Затем мы проверили исходный код BigInteger. Мы проверили свойства signum и mag . Мы также узнали, как BigInteger хранит данное значение, что позволяет нам предоставлять большие числа, чем доступные примитивные типы данных.

Как всегда, мы можем найти все фрагменты кода и тесты на GitHub .