Parse bignum into list of 16-bit integers
I have to implement some bignum arithmetics. The number has to be split into a list of 16 bit integers.
That is not t开发者_JAVA技巧he problem. The problem is to parse a string into this notation. If it would be a single integer, i would go through the string backwards, get the number out of the char and would add <number>*10^stringposition. (last char has stringposition 1 in this example)
But the bignum should not have multiplication and I thing there should be a smarter faster way. (A int multiplication is O(1); a bignum multiplication not)
How to do it?
(I can not use a complete library like gmp)
In Java you can solve your problem using java.math.BigInteger
class.
Create a BigInteger from your String input:
BigInteger x = new BigInteger(s);
Get a byte array containing the two's-complement representation of this BigInteger:
byte[] b = x.toByteArray();
Convert the byte array to int[] merging consecutive pairs of 8-bit values into 16-bit values like this:
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; }
I don't think there's a good way to do this as the internal representation actually 2^16 base. You need to convert a 10 based number into a 2^16 based number.
don't use x*10^(position x), because you don't have the representation of 10^n in 2^16 base. You can do something like
num = 0
for i=0 to len do
num = num * 10 + a[i]
精彩评论