Как BigInteger хранит свои данные?

#java #biginteger

Вопрос:

Я довольно долго искал и почти ничего не нашел о том, как BigInteger на самом деле хранятся его числа. Являются ли они массивом символов? Что-то еще? И как данные преобразуются в / из BigInteger ?

Из того, что я нашел, я предполагаю, что все классы произвольной точности, такие как BigInteger и BigDecimal , содержат данные в виде массива символов. Так ли это на самом деле работает? Или это просто предположение людей?

Я спрашиваю, потому что я работал над своей собственной реализацией чего-то вроде BigInteger , но я не могу понять, как хранить числа, большие Long.MAX_VALUE (я не помню фактическое число).

Заранее спасибо.

1. Помните, что реализация вольна делать то, что ей нравится, до тех пор, пока она придерживается BigInteger контракта JDK. Вы можете просмотреть полный исходный код Sun JDK, если достаточно постараетесь — Oracle усложнила его получение, чем раньше, но это все еще возможно; начните здесь . Вы можете просмотреть версию OpenJDK здесь (она также использует int[] ).

Ответ №1:

С помощью int[]

Из исходного кода:

 /**
 * The magnitude of this BigInteger, in <i>big-endian</i> order: the
 * zeroth element of this array is the most-significant int of the
 * magnitude.  The magnitude must be "minimal" in that the most-significant
 * int ({@code mag[0]}) must be non-zero.  This is necessary to
 * ensure that there is exactly one representation for each BigInteger
 * value.  Note that this implies that the BigInteger zero has a
 * zero-length mag array.
 */
final int[] mag;

1. @glowcoder Спасибо за ответ, но есть ли в нем какие-либо другие детали? Например, как он преобразует входные данные в этот массив?

2. С точки зрения непрофессионала… (в этой конкретной реализации) побитовое числовое представление упаковано в массив значений int .

3. (Внутренне дополнение two не используется — хотя valueOf(int[]) будет принимать входные данные в дополнении two.)

4. @glowcoder: Oracle идет на некоторые меры, чтобы гарантировать, что люди принимают лицензию, прежде чем получить доступ к исходному коду. Публикация всего класса в Интернете без этих средств защиты, вероятно, является нарушением авторских прав. Вместо этого просто укажите @Jon на то, где он сам может получить копию исходного кода .

5. @T.J. Извините, я не увидел там точек. 🙂 Я бы предпочел не использовать @Crowder, так как это также фамилия моего менеджера, и я бы не хотел путать их (потому что вы мне нравитесь, и я бы предпочел, чтобы так и оставалось!) В любом случае, по теме, я взглянул на лицензию, и вы абсолютно правы. Я удалил ссылку.

Ответ №2:

Наиболее распространенным способом представления чисел является использование позиционной системы счисления. Числа записываются с использованием цифр для представления кратных степеней указанного основания. База, с которой мы наиболее знакомы и которой пользуемся каждый день, — это база 10. Когда мы записываем число 12345 в базе 10, это фактически означает: 12345 = 1*10^4 2*10^3 3*10^2 4*10^1 5*10^0

Продолжение здесь…

Ответ №3:

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