1

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

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

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

怎么做?

(我不能使用像 gmp 这样的完整库)

4

2 回答 2

2

我认为没有一个好的方法可以做到这一点,因为内部表示实际上是 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]
于 2010-01-11T12:07:52.593 回答
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;
    }
    
于 2010-01-11T14:46:54.240 回答