Разобрать bignum в список 16-битных целых

Question

Я должен реализовать некоторую арифметику Бигнума. Число должно быть разбито на список 16-битных целых чисел.

Это не проблема. Проблема состоит в том, чтобы разобрать строку в этой записи. Если бы это было одно целое число, я бы прошел строку назад, вытащил число из символа и добавил бы * 10 ^ строковое положение. (последний символ имеет строковую позицию 1 в этом примере)

Но у bignum не должно быть умножения, и я думаю, что должен быть более умный и быстрый способ. (Умножение int равно O (1); умножение bignum отсутствует)

Как это сделать?

(я не могу использовать полную библиотеку, такую ​​как gmp)

Answer 1

В Java вы можете решить вашу проблему, используя java.math.BigInteger класс.

1. Создайте BigInteger из вашего ввода String:

   BigInteger x = new BigInteger(s);

2. Получите байтовый массив, содержащий представление двоичного дополнения этого BigInteger:

   byte[] b = x.toByteArray();

3. Преобразование байтового массива в int [], слияние последовательных пар 8-битных значений в 16-битные значения, например:

   int[] merge(byte[] b) {
       int[] result = new int[((b.length-1)>>1) + 1];
       for (int i = 0; i < b.length; i++) {
            result[i>>1] |= b[b.length-i-1] << ((i&1)<<3);
       }
       return result;
   }
   

Answer 2

Я не думаю, что есть хороший способ сделать это, поскольку внутреннее представление на самом деле составляет 2 ^ 16 базы. Вам нужно преобразовать число на основе 10 в число на основе 2 ^ 16.

не используйте x * 10 ^ (позиция x), потому что у вас нет представления 10 ^ n в базе 2 ^ 16. Вы можете сделать что-то вроде

num = 0
for i=0 to len do
  num = num * 10 + a[i]