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

Question

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

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

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

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

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

Answer 1

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

1. Создать BigInteger из вашей входной строки:

   BigInteger x = new BigInteger(s);

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

   byte[] b = x.toByteArray();

3. Преобразовать массив байтов в int [] объединение последовательных пар 8-битных значений int O 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]