algorithm - 将 bignum 解析为 16 位整数列表

Question

我必须实现一些 bignum 算术。该数字必须拆分为 16 位整数列表。

那不是问题。问题是将字符串解析为这种表示法。如果它是一个整数，我会向后遍历字符串，从字符中取出数字并添加 <number>*10^stringposition。（在本例中，最后一个字符的字符串位置为 1）

但是 bignum 不应该有乘法，我认为应该有一个更聪明更快的方法。（一个 int 乘法是 O(1)；一个 bignum 乘法不是）

怎么做？

（我不能使用像 gmp 这样的完整库）

Answer 1

我认为没有一个好的方法可以做到这一点，因为内部表示实际上是 2^16 基数。您需要将基于 10 的数字转换为基于 2^16 的数字。

不要使用 x*10^(position x)，因为在 2^16 基数中没有 10^n 的表示。你可以做类似的事情

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

Answer 2

java.math.BigInteger在 Java 中，您可以使用类来解决您的问题。

1. 从您的字符串输入创建一个 BigInteger：

   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;
   }