bignum을 16 비트 정수 목록으로 구문 분석

Question

일부 bignum 산술을 구현해야합니다. 숫자는 16 비트 정수의 목록으로 분할되어야합니다.

그건 문제가되지 않습니다. 문제는이 표기법으로 문자열을 구문 분석하는 것입니다. 그것은 하나의 정수가 될 경우, 내가 문자열을 거꾸로 가서 char 밖으로 숫자를 얻을 것이고 숫자 > * 10^stringposition을 추가 할 것입니다. (마지막 문자는이 예에서 stringposition 1을 가짐)

그러나 bignum은 곱셈을해서는 안되며 더 똑똑한 방법이 있어야합니다. (int 곱셈은 O (1)이고, bignum 곱셈은 아닙니다)

어떻게 할 것인가?

내가 내부 표현 실제로 2^16 기지로이 작업을 수행 할 수있는 좋은 방법이 생각하지 않습니다

Answer 1

java.math.BigInteger 클래스를 사용하여 문제를 해결할 수 있습니다.

1. 당신의 문자열 입력에서의 BigInteger를 만들기 :

   byte[] b = x.toByteArray();

2. 변환 :

   BigInteger x = new BigInteger(s);

3. 이 BigInteger의 2의 보수 표현을 포함한 바이트 배열을 가져옵니다 바이트 배열을 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

(I는 GMP와 같은 전체 라이브러리를 사용할 수 없습니다). 10 개의 숫자를 2^16의 숫자로 변환해야합니다.

2^16 기준으로 10^n의 표현이 없기 때문에 x * 10^(위치 x)를 사용하지 마십시오.

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