алгоритм преобразования Java BigInteger - PullRequest
Новая
       10

алгоритм преобразования Java BigInteger

1 голос
/ 18 апреля 2019

BigInteger из Java хранит число в виде массива "целых чисел без знака" (это массив целых чисел, но они хранят информацию в 32-битной системе, а затем приводят ее к типу long и выполняют операцию).

Как они конвертируют из десятичной системы в базовую 32-битную систему? Какой алгоритм?

Я читал источники и не понимаю этого. Я вижу, что они разделяют числа на 10-значную строку (целое число может обработать 1_000_000_000), но что дальше? Делить на 2? или 2 ^ 32 (4294967296)?

Спасибо за помощь, чтобы понять это.

1 Ответ

0 голосов
/ 18 апреля 2019

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

  1. Установите для промежуточного результата (BigInteger) значение BigInteger.ZERO.
  2. прочитать знак (если он есть) и запомнить его
  3. прочитать цифру
  4. , используя заданную числовую базу (основание, 2..36),преобразовать цифру в двоичную, например, в базу 10, '9' преобразуется в 9, в базу 16, 'A' преобразуется в 10 и т. д.
  5. Умножить промежуточный результат на базу и добавить значениецифры, поэтому, если основание равно 10, умножьте промежуточный результат на 10 и добавьте только что прочитанную цифру 9.
  6. Повторяйте с пункта 2 до тех пор, пока вся строка не будет прочитана
  7. Установите знак
  8. Очистить и при необходимости удалить начальные нули и т. Д.
  9. Вернуть промежуточный BigInteger как результат функции.

Цикл работает следующим образом: 

number: 1234 (base 10)
intermediate x = 0
read digit = 1: x = x * 10 + 1 = 0 + 1 = 1
read digit = 2: x = x * 10 + 2 = 10 + 2 = 12
read digit = 3: x = x * 10 + 3 = 120 + 3 = 123
read digit = 4: x = x * 10 + 4 = 1230 + 4 = 1234

the same number in base 16:
read digit = 1: x = x * 16 + 1 = 0 + 1 = 1
read digit = 2: x = x * 16 + 2 = 16 + 2 = 18 (= 0x12)
read digit = 3: x = x * 16 + 3 = 288 + 3 = 291 (= 0x123)
read digit = 4: x = x * 16 + 4 = 4656 + 4 = 4660 (= 0x1234)
...