투 명 테 잎

본격적으로 쉬프트 연산을 만들어 보겠습니다.
숫자들은 blk라는 unsigned long형 배열에 저장되있습니다.

하.. 배열의 시작번지를 인수로 주면 배열 전체를 n비트 쉬프트 시켜주는 함수가

blocktype *blk;
blk = blk << n;

있었으면 아주 편했을텐데 말인데.. 그런건 없더라구요.. 
결국, blk의 블럭 하나하나를 쉬프트 해야만 했습니다.
(..
memmove함수를 생각해봤지만 이동단위가 byte여서
bit를 쉬프트 해야 하는 이번 경우에는 적용시킬 수 없었습니다.)

우선 몇 블럭, 몇 비트를 쉬프트 해야 하는지 구합니다.
만약 blk를 40비트 왼쪽으로 쉬프트 한다면
(blocktype은 32비트이므로, 한 블록은 32비트입니다.)
32 + 8이므로
1블럭 + 8비트 쉬프트입니다.

이제, Get_LShiftedBlock함수를 호출하여
젤 낮은 자리부터 8비트 쉬프트 한것을 1블럭 옆에 대입합니다.

일반화 시킨다면
x크기의 blk를
(blk[0],blk[1], blk[2]...blk[x-2]...blk[x-1])
n비트 쉬프트시
blk[i]블럭을
n%32만큼 쉬프트 시켜서
blk[n/32 + i]블럭에 대입합니다.
이것을 i가 0부터 x-1까지, x번 반복하는 것이지요. 

이해가 되셨나요?
그럼 이제 코드를 보겠습니다.
 

const BigInteger BigInteger::operator <<(const int leftmove) const
{
	// (*this) * 2^(leftmove)를 연산
	BigInteger temp; // 결과값 리턴용
	/*
	 * 특수 경우를 제외합니다.
	 * 1. *this가 0이면, 0 리턴
	 * 2. leftmove가 0이면, *this 리턴
	 * 3. leftmove가 음수면, >> 쉬프트로 연산
	 */
	if (sign == Zero)
		return temp;
	if (leftmove == 0)
		return *this;
	else if (leftmove < 0)
		return *this >> (-leftmove);
	length shiftblocks = leftmove / N;
	length shiftbits = leftmove % N;

	// +1은 shitfbits때문에 생기는 추가되는 블록 저장용
	temp.Reallocate(len + shiftblocks + 1);

	// 한블럭씩 shiftbits만큼 쉬프트 시켜 대입해줍니다.
	index i, j;
	for (i = 0, j = shiftblocks; i <= len; i++, j++)
		temp.blk[j] = Get_LShiftedBlock(i, shiftbits);

	// Get_LShiftedBlock(len - 1, shiftbits)가 0일 경우...
	if (temp.blk[temp.len - 1] == 0)
		temp.len--;
	temp.sign = sign;
	return temp;
}

위에서 설명하여서 비교적 이해가 되시리라 생각됩니다.
그런데
temp를 재할당 하는 함수에서 +1을 하였습니다.
왜 그랬을까요?
shiftbits가 0이면 그냥 shiftblocks만큼 배열의 원소들을 옮겨주면 됩니다.
하지만 shiftbits가 0이 아니라면 배열의 최고차항도 shiftbits만큼 쉬프트 해주어 합니다.

그런데 만약 배열의 최고차항 배열의 원소가
다음을 만족한다면..

(  blk[len - 1] >> ( 32 - shiftbits)  ) != 0

배열의 길이가 len + shiftblocks보다 1칸 더 많아져야 합니다.
(  blk[len - 1] >> ( 32 - shiftbits)  ) 이것을 저장한 1블럭이 필요하기 때문입니다.
무슨 소린야?? 라고 하실지도 모르겠습니다.
근데.. 곰곰히 생각해보시면.. 아 그렇구나 하실겁니다.

블럭을 쉬프트 대입 후,
temp.blk[temp.len - 1] 가 0인지 비교합니다.
이건 다음과 뜻이 같습니다.
==  this->Get_LShiftedBlock(len - 1, shiftbits)가 0인가?
==  (  *this.blk[len - 1] >> ( 32 - shiftbits)  )가 0인가?
0이라면 temp.len을 한칸 줄입니다.
그 후, 부호를 대입하면 끝입니다..!!

글이 많이 길어졌네요..
다음글에서 >>연산에 대해 쓰겠습니다. 

"C++로 구현핱 자료구조"
제 1장 서론 연습문제 30번...

"n진법 표현에서 n이 꼭 양수일 필요는 없다..."

생각해 보니 그렇다.
예로 -2진법을 보였는데
흥미로웠다.
음의 진법으로는 부호의 표기가 필요없다고 한다.
또한, e.번에 "이 표기법으로 덧셈을 하는 너무 깜찍한 방법이 한 가지 있다.", 라고 한다.


음의 진법을 생각해보자!

다음으로 쉬프트 연산입니다.
하.. ^^
쉬프트 연산도 만들 때 고생 많이 했습니다.
배열을 쉬프트하는 연산을 기본적으로 제공하지 않으므로
배열 쉬프트 연산을 만들어 직접 blk 배열을 쉬프트 하는 수밖에 없습니다.
그러기 위해 보조 함수를 만들었습니다.

다음이 그 보조 함수입니다.

const BigInteger::blocktype BigInteger::Get_LShiftedBlock(const index x, const length n) const
{
	// x는 0~len까지의 범위를 가집니다.
	// n은 0~31까지의 범위를 가집니다.

	// x의 전 블록 상위 n비트를 추출 합니다.
	blocktype lowblk = (x == 0 || n == 0) ? 0 : ( blk[x - 1] >> (N - n) );
	// x 블록을 왼쪽으로 n번 쉬프트한 것을 추출 합니다.
	blocktype highblk = (x == len) ? 0 :( blk[x] << n );
	// 위 두 블럭의 합집합을 리턴합니다.
	return lowblk | highblk;
}

blk배열을 블록단위로 쉬프트 하는 함수입니다.
x는 blk의 몇 번째를 쉬프트 할지 결정하고,
n은 몇 비트를 쉬프트 할지 결정합니다.
즉, 다음과 같이 사용하면
Get_LShiftedBlock(3,4);
blk[3] << 4 한 것과 blk[2]의 상위 4비트와의 합집합을 구한다는 것입니다.

blk[x]를 왼쪽으로 2 쉬프트 한다면
blk[x]의 하위 2비트는 0으로 채워지게 됩니다.
하지만 BigInteger형에서는 0으로 채워져서는 안되며
아래 배열요소의 상위 2비트값으로 채워져야하합니다.
그래야 배열에서 연속적으로 저장한 숫자들의 쉬프트를 구현했다고
말할 수 있습니다.

자, 그럼 문제입니다.. !!!
왜 오른쪽으로 쉬프트 하는 함수는 없을까요?
위 함수를 쓰면 되기 때문입니다.
blk3]을 오른쪽으로 4비트 쉬프트 시키려면 어떻게 함수를 호출해야 할까요??




Get_LShiftedBlock(4,28);
을 호출하면 됩니다.
즉, x블록을 오른쪽으로 n비트 쉬프트 시키려면
Get_LShiftedBlock(x + 1, 32 - n);
을 호출해주면 됩니다.
엥?? 무슨 소리냐구요??
곰곰히 생각해보세요.. ^^
안되는 머리로 생각 하려니 전 오래 걸렸습니다.. ㅠㅠ 


이제 저 보조함수를 이용해서
왼쪽, 오른쪽으로 쉬프트 하는 쉬프트연산자를 오버로딩 해보겠습니다.
그 전에!!
또, 정의를 새롭게 해야합니다.
정수형에서 쉬프트 연산자는
왼쪽 혹은 오른쪽으로 모든 n비트를 옮긴 후, 범위 밖은 버리고, 공백은 0으로 채우는 것으로 정의되있습니다.
그러나, BigInteger형은 비트수가 정해진게 아니라서 위의 정의가 성립하지 않습니다.

그래서 이것도 연산의 특징을 정의로 간주하고 만들었습니다.
즉, << 쉬프트 연산은 모든 비트를 왼쪽으로 옮기데, 블록이 부족하면 새롭게 할당합니다.
그러므로, a << b를 호출하면 무조건 a * 2^b 가 성립하게 됩니다.
>> 쉬프트는 정수형과 비슷합니다.
모든 비트를 오른쪽으로 옮기데, 블록이 남으면 없앱니다.
따라서, a >> b를 호출하면 무조건 a * 2^(-b)가 성립합니다.

또한, 기본 쉬프트 연산과는 다른점이 있습니다.
기본 쉬프트는
b가      0 <= b < sizeof(a) 안에서만 정상적으로 작동합니다.
하지만, BigInteger형이 쉬프트 연산은 모든 int범위 내에서 성립하게 만들었습니다.
1. b가 0이면 a리턴
2. b가 양수이면 정상적으로 실행    ->     a * 2^b
3. b가 음수라면 반대쉬프트 실행    ->     a * 2^b, (b<0)
예로 1 << - 1은  1 >> 1과 같다는 말입니다. 

휴... 기네요.. ㅋ
다음 글에서 계속 이어 가겠습니다. ^^