투 명 테 잎

이전 글에 이어서
subtract함수부터 쓰겠습니다.

void BigInteger::subtract (const BigInteger &Left, const BigInteger &Right)
{
	// Left의 크기에서 Right의 크기만큼을 빼서 this에 저장하는 함수입니다.

	// 이 함수를 호출하는 함수에서 left의 크기가 항상 크도록 설정
	// | Left | - | Right |
	// 가 성립한다는 전제하에 subtract함수는 작동합니다.
	
	// 초기에는 divideWithRemainder함수에서
	// subtract함수를 this->subtract(*this, x)와 같이 호출하여
	/*
	  if (Left.len < Right.len)
	  {
	        add(Right, Left);
	        return;
	  }
	 */
	// 이 필요하였지만, divide..함수의 알고리즘을 다른 것으로
	// 교체 하면서 subtract함수를 호출하지 않게되어 삭제하였습니다.

	// 빼는데 될 수있는 가장 긴 길이는 Left.len
	Reallocate(Left.len);

	blocktype blk_temp = 0; // 두 블럭의 차를 잠시 저장하기 위해
	// 자리내림 처리용
	// borrowIn : 이전 자리에서 자리내림 발생?
	// borrowOut : 현 자리에서 연산으로 자리내림 발생?
	bool borrowIn, borrowOut;
	index i;
	// 낮은 자리 만큼 루프를 돌며 뺄셈 연산
	for(i = 0, borrowIn = false; i < Right.len; i++){
		blk_temp = Left.blk[i] - Right.blk[i];
		// 자리 내림이 발생하면
		// blk_temp > Left.blk[i]
		// blk_temp > Right.blk[i]
		// 위 두개를 모두 만족한다.
		// 그래서 두 개중에 하나만 사용하여 비교해 주면된다.
		borrowOut = (blk_temp > Left.blk[i]);
		if (borrowIn) { // 전 자리에서 자리내림 발생했는가?
			// BorrowIn으로 인한 자리내림 발생 가능성 처리
			borrowOut |= (blk_temp==0);
			blk_temp--;
		}
		blk[i] = blk_temp;
		borrowIn = borrowOut;
	}

	// blk[Right.len - 1]에서 자리내림 발생했는가?
	// 또한, 큰 가능성은 없지만 연쇄 자리내림이 가능하다
	// ex) 1000 - 1과 같은 경우와 비슷한 맥락
	for(; borrowIn && i < Left.len; i++){
		borrowIn = (Left.blk[i] == 0);
		blk[i] = Left.blk[i] - 1;
	}

	// 나머지는 그대로 대입
	for(; i < Left.len; i++)
		blk[i] = Left.blk[i];

	// 연산 결과로 생기는 선두 0블럭들을 모두 제거
	ZapLeadingZeros();
}

add함수와 비슷한 모양이라 주석만으로 쉽게 이해가 되실겁니다.
또한, add와 subtract 함수를 완벽하게 이해하셨다면
이전 글의 + 오버로딩 함수와
아래의 - 오버로딩 함수를 충분히 이해하실 수 있으실 겁니다.

const BigInteger BigInteger::operator -(const BigInteger &x) const
{
	BigInteger temp;
	// 둘 중 하나가 0일 때 처리
	if (x.sign == Zero)
		return *this;
	if (sign == Zero)
	{
		temp = x;
		return -temp;
	}

	// 두 수의 부호가 다르다면 크기는 더해지고
	// 부호는 this를 따르면 됩니다.
	if (sign != x.sign)
	{
		temp.add(*this, x);
		temp.sign = sign;
	}
	// 두 수의 부호가 같을 때
	else
	{
		CmpResult cmp;
		// this와 x의 '크기'비교
		cmp = CompareTo(x);
		if ( cmp == Equal )
			; // 같다면 결과는 0
		else if ( cmp == Greater )
		{
			// this > x인 경우
			temp.subtract(*this, x);
			temp.sign = sign;
		}
		else
		{
			// this < x인 경우
			temp.subtract(x, *this);
			// this의 부호에 따라 결과값의 부호가 달라짐
			// Zero가 나오는 경우는 위에서 처리했으므로
			// Zero가 나올 수는 없다.
			temp.sign = (sign ==Positive) ? Negative : Positive;
		}
	}
	return temp;
}

이로써 두 BigInteger형의 + , - 연산을 만들었습니다.
+ , - 연산을 이용해 += , -= 연산도 만들었습니다. 

사칙연산을 구현할 때입니다.

사람들에게는 친숙하지만 컴퓨터에게는 친숙하지 않은가 봅니다.
제일 복잡합니다..

사칙연산 부분은 두단계를 거쳐 구현합니다.

private로 사칙연산의 알고리즘을 실행하는 함수를 만듭니다.
그리고 public으로 연산자 오버로딩을 사용하여 +,-,*,/,%,+=,-=,*=,/=,%=,++,--를 구현합니다.
private함수에서는 최대한 전제와 조건을 넣지 않으려고 하였습니다.
최대한 빠르게 하기 위해서 입니다.
private의 나누기 함수에서는 0으로 나누는지도 검사하지 않습니다.
연산을 하기 위한 모든 조건이 충족 됬다는 전제하에 private함수를 호출하는 것이기 때문입니다.
+, -, *, / 등등의 오버로딩 함수에서 모든 조건을 걸러내게 하였습니다.
(다른 멤버함수에서 호출하는 경우에 필요한 조건은 불가피하게 넣게 됬습니다.)

const BigInteger BigInteger::operator +(const BigInteger &x) const
{
	// 둘 중 하나가 0이면 다른 수를 리턴하면 됩니다.
	if (sign == Zero)
		return x;
	if (x.sign == Zero)
		return *this;

	BigInteger temp;
	CmpResult cmp;
	// CompareTo함수는 this와 x의 '크기'를 비교합니다.
	cmp = CompareTo(x);
	// 두 수의 부호가 다르다면, 뺄셈과 같습니다.
	if (sign != x.sign)
	{
		if (cmp == Equal)
			; // 연산 없이 0리턴
		else if (cmp == Greater)
		{
			// this > x인 경우
			temp.subtract(*this, x);
			temp.sign = sign;
		}
		else
		{
			// x > this인 경우
			temp.subtract(x, *this);
			temp.sign = x.sign;
		}
	}
	// 부호가 같은경우..
	else
	{
		temp.add(*this, x);
		temp.sign = sign;
	}
	return temp;
}

+ 연산자 오버로딩 부분입니다.

두 수중 0이 있는지..
두 수의 부호가 같은지 다른지..
두 수의 길이가 같은지 다른지..
에 따라 호출되는 함수가 다르며
넘어가는 인수의 순서도 다릅니다.

위 함수에서는 add 혹은 subtract 함수가 호출됩니다.
this->add(a, b)함수는 a,와 b의 크기의 함을 this에 저장합니다.
(a, b의 부호는 무시하고 크기만을 더합니다. )
this->subtract(a, b)함수는 a의 크기에서 b의 크기를 뺍니다.
(이것도 역시 부호는 무시합니다.)

여기서는 add함수에 대해서만 포스팅 하겠습니다.
subtract 함수는 다음글에서 쓰겠습니다. 

void BigInteger::add(const BigInteger &Left, const BigInteger &Right)
{
	// Left와 Right의 크기를 더하여 this에 저장하는 함수입니다.

	// StringToBiginteger 함수에서
	// this->add(*this, x)와 같이 호출하기 때문에
	if (this == &Left)
	{
		BigInteger Left_temp(Left);
		add(Left_temp, Right);
		return;
	}
	// 호출 함수부분을 간략하게 하기 위해서
	if (Left.len < Right.len)
	{
		add(Right, Left);
		return;
	}
	// 이제, Left와 Right의 길이간에는
	// Left.len >= Right.len 이 성립
	Reallocate(Left.len + 1);

	blocktype blk_temp = 0; // 두 블럭의 합을 잠시 저장하기 위해
	// 자리수 올림 처리용
	// carryIn : 이전 자리에서 자리올림 발생?
	// carryOut : 현 자리에서 연산으로 자리올림 발생?
	bool carryIn, carryOut;
	index i;
	// 낮은 자리 만큼 루프를 돌며 덧셈 연산
	for(i = 0, carryIn = false; i < Right.len; i++){
		blk_temp = Left.blk[i] + Right.blk[i];
		// 자리 올림이 발생하면
		// blk_temp < Left.blk[i]
		// blk_temp < Right.blk[i]
		// 위 두개를 모두 만족한다.
		// 그래서 두 개중에 하나만 사용하여 비교해 주면된다.
		carryOut = (blk_temp < Left.blk[i]);
		if (carryIn) { // 전 자리에서 자리올림 발생했는가?
			++blk_temp;
			// CarryIn으로 인한 자리올림 발생 가능성 처리
			carryOut |= (blk_temp==0);
		}
		blk[i] = blk_temp;
		carryIn = carryOut;
	}

	// blk[Right.len - 1]에서 자리올림 발생했는가?
	// 또한, 큰 가능성은 없지만 연쇄 자리올림이 가능하다
	// ex) 799 + 1과 같은 경우와 비슷한 맥락
	for(; carryIn && i < Left.len; i++){
		blk[i] = Left.blk[i] + 1;
		carryIn = (blk[i] == 0);
	}

	// 나머지는 그대로 대입
	for(; i < Left.len; i++){
		blk[i] = Left.blk[i];
	}

	// 연쇄 자리올림이 끝까지 일어난 경우이다.
	// 위에서 799 + 1이 아닌 999 + 1과 같은 경우다.
	// 연산값이 자릿수가 1 증가하며 증가한 자리의 숫자는 1이다.
	// 아니라면 len 1 감소
	if(carryIn) blk[i]=1;
	else len--;
}

정성스럽게 주석을 달았습니다.. ^^
주석만 잘보시면 이해되실겁니다. ^^ 

오른쪽 쉬프트에서
헷갈리는 부분이 있습니다..
(앗.. 혹시 저만.. 그런가요..)

const BigInteger BigInteger::operator >>(const int rightmove) const
{
	BigInteger temp;
	if (sign == Zero)
		return temp;
	if (rightmove == 0)
		return *this;
	else if (rightmove < 0)
		return *this << (-rightmove);
	// 결과값이 0이 나오는 경우
	if (unsigned __int64(rightmove)  >= bitlength())
		return temp;

	length rightShiftBlocks = (rightmove + N - 1) / N;
	length leftShiftBits = N * rightShiftBlocks - rightmove;
	// 이제 (N * rightShiftBlocks - leftShiftBits) == rightmove
	// 그리고 0 <= leftShiftBits < N 가 성립합니다.
	
	// + 1: 최상위 블럭 때문입니다.
	temp.Reallocate(len + 1 - rightShiftBlocks);

	index i, j;
	for (j = rightShiftBlocks, i = 0; j <= len; j++, i++)
		temp.blk[i] = Get_LShiftedBlock(j, leftShiftBits);
	if (temp.blk[temp.len - 1] == 0 && temp.len != 1)
		temp.len--;
	// 위에서 결과값이 0이 나오는 것을 제거 하였기 때문에
	// 그대로 부호를 넣는다.
	temp.sign = sign;
	return temp;
}

함수 중에
rightShiftBlocks와 leftShiftBits를 구하는 부분이 헷갈릴 수 있습니다.
오른쪽으로 쉬프트 하는 경우는 두가지 경우로 구 할수 있습니다.

n비트를 쉬프트 하는 경우..

a = n/32 b = n%32 x블럭에 Get_LShiftedBlock(x+a+1, 32-b)대입 x는 0부터 len-1-a까지

c = (n + 32 - 1)/32 d = (32*c - n) x블럭에 Get_LShiftedBlock(x+c, d)대입 x는 0부터 len-1-c까지

두가지 경우를 생각 해볼 수 있습니다.
그 중, 오른쪽 방법을 사용하여 >> 쉬프트 함수를 구현한 것입니다.

둘을 방법론적으로 보면 똑같은 원리입니다.
하지만 초기에 a,b와 c,d를 구하는 식이 다르기 때문에
아래 함수에 들어가는 인수가 달라져 보이는 것뿐입니다.

곰곰히 생각해보세요.
정 오른쪽이 이해가 안가시겠다면 왼쪽방법으로 구현하세요. ^^