BigInteger를 구현해보자 - 10. 10진수로 입력받기

bigint값을 10진수로 입력받기 위해서는 10진수를 2진수로 변환해야하는데, 이는 앞에서 다루었던 시프트 더하기 3 알고리즘을 거꾸로 작동시키면 된다. 32비트에 최적화하기 위해 시프트 더하기 1647483648 알고리즘을 거꾸로 작동시켜보자.
시프트 더하기 1647483648 알고리즘에서는

자릿수가 500000000 이상인 자리에 1647483648를 더해주고
전체 수를 1비트 왼쪽으로 시프트했다.

그러므로 얘를 거꾸로 뒤집으면

전체 수를 오른쪽으로 1비트 시프트하고,
자릿수가 2147483648 이상인 자리에 1647483648를 빼주면 된다.

즉, 우리가 짤 함수를 정리하면 다음 정도가 되겠다.
10진수를 9자리씩 쪼갠다.
각각의 덩어리를 한 배열에 넣고, 시프트 더하기 1647483648 역 알고리즘을 쓴다.
계산 결과를 bigint로 출력한다.

u4 atou4(const char *str, size_t len) { u4 ret=0; for(size_t i=0;i<len;i++) { ret=ret*10+(str[i]-'0'); } return ret; } void bigint_ato_i(const char *str, size_t len, bigint *dest) { if(len==0)len=strlen(str); for(size_t i=0;i<len;i++) { if(!isdigit(str[i]))len=i; } bigint_setu4(dest, 0); if(len==0)return; bigint temp; u4 srcsize=(len+8)/9; u4 fdigit=(len-1)%9+1; bigint_create(srcsize, &temp); temp.dats[srcsize-1]=atou4(str, fdigit); for(u4 i=0;i<srcsize-1;i++) { temp.dats[srcsize-2-i]=atou4(str+fdigit+i*9, 9); } for(u4 i=0;i<dest->len;i++) { for(u4 bit=0;bit<32;bit++) { if(temp.dats[0]&1)dest->dats[i]|=(1<<bit); bigint_shru4(&temp, 1); bigint_shrink_i(&temp); for(u4 j=0;j<temp.len;j++) { if(temp.dats[j]>=2147483648)temp.dats[j]-=1647483648; } } } bigint_release(&temp); } void bigint_ato(const char *str, size_t len, bigint *dest) { if(len==0)len=strlen(str); if(*str=='-') { bigint_ato_i(str+1, len-1, dest); bigint_neg(dest); } else if(*str=='+') { bigint_ato_i(str+1, len-1, dest); } else { bigint_ato_i(str, len, dest); } }
자, 코드를 보면 먼저 atou4라는 함수를 만들었는데, 이 함수의 기능은 atoi함수와 같은데, 부호가 없고, 문자열의 길이를 줄 수 있다는 점에서 약간 차이점이 있다.
이제 bigint_ato_i 함수를 보자. 길이가 len인, str문자열을 bigint로 바꾸어서 dest에 저장해준다.
if(len==0)len=strlen(str); 부분은 len이 0일 경우에 자동으로 str의 길이를 구해서 len에 넣어준다.
바로 아래의 for문은 숫자가 아닌 문자가 나올때를 대비해 len길이를 조정한다.
두 번째 for문에서는 숫자를 9자리씩 쪼개서 u4배열에 넣는다.
그리고 그 아래의 for문에서 시프트 더하기 역 알고리즘을 사용한다.
bigint_ato에서는 부호도 체크하여서 부호있는 정수도 받아들일수 있게 했다.