BigInteger를 구현해보자 - 5. 시프트 연산

시프트란것은 전체 비트배열을 왼쪽으로 또는 오른쪽으로 밀어주는 것을 말한다. n비트 왼쪽으로 시프트하는 것은 2^n을 곱하는 것, 오른쪽으로 시프트하는 것은 2^n을 나누는것과 같은 효과를 나타낸다.

	a[4]	a[3]	a[2]	a[1]	a[0]
<<왼쪽으로 2만큼 시프트<<
a[3]	a[2]	a[1]	a[0]	0	0

bigint를 왼쪽,오른쪽으로 시프트하는 함수를 만든다.

1 2 3 4 5 6 7 8 9 10 11 12

void bigint_shru4(bigint *dest, u4 src) {     u4 shiftb=src>>5;     src=src&31;     dest->dats[0]=dest->dats[shiftb]>>src;     for(u4 i=1;i<dest->len-shiftb;++i)     {         dest->dats[i-1]|=dest->dats[i+shiftb]<<(32-src);         dest->dats[i]=dest->dats[i+shiftb]>>src;     }     memset(dest->dats-shiftb, 0, shiftb*sizeof(u4)); }

먼저 오른쪽으로 src비트만큼 시프트하는 함수다. 특별한 건 없고, u4가 32비트이므로, 32로 나누어서 몫만큼은 배열 전체를 밀어주고, 나머지만큼만 오른쪽으로 시프트하면 된다. 그리고 오른쪽으로 시프트 한 다음에 제일 왼쪽에 남는 공간은 memset으로 0으로 채워준다.

1 2 3 4 5 6 7 8 9 10 11 12

void bigint_shlu4(bigint *dest, u4 src) {     u4 shiftb=src>>5;     src=src&31;     dest->dats[dest->len-1]=dest->dats[dest->len-shiftb-1]<<src;     for(u4 i=dest->len-2;(long)i>=(long)shiftb;--i)     {         dest->dats[i+1]|=dest->dats[i-shiftb]>>(32-src);         dest->dats[i]=dest->dats[i-shiftb]<<src;     }     memset(dest->dats, 0, shiftb*sizeof(u4)); }

자, 이제 왼쪽으로 src비트만큼 시프트하는 함수다. 오른쪽으로 시프트하는 것과 마찬가지로 한다. 역시 왼쪽으로 시프트 한 다음에 제일 오른쪽에 남는 공간은 0으로 채워준다.

bigint의 길이가 n일때, 위 함수들은 2*n-1번의 시프트를 사용하여, bigint를 시프트한다. 따라서 시간 복잡도는 O(n).