我必须实现一些 bignum 算术。该数字必须拆分为 16 位整数列表。
那不是问题。问题是将字符串解析为这种表示法。如果它是一个整数,我会向后遍历字符串,从字符中取出数字并添加 <number>*10^stringposition。(在本例中,最后一个字符的字符串位置为 1)
但是 bignum 不应该有乘法,我认为应该有一个更聪明更快的方法。(一个 int 乘法是 O(1);一个 bignum 乘法不是)
怎么做?
(我不能使用像 gmp 这样的完整库)
我认为没有一个好的方法可以做到这一点,因为内部表示实际上是 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]
java.math.BigInteger
在 Java 中,您可以使用类来解决您的问题。
从您的字符串输入创建一个 BigInteger:
BigInteger x = new BigInteger(s);
获取包含此 BigInteger 的二进制补码表示的字节数组:
byte[] b = x.toByteArray();
将字节数组转换为 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; }