[BigInteger - 7] 비트연산

위 사진은 비트연산에 해당하는 함수들입니다.
BigInteger의 blk의 길이와 비트길이를 리턴해주는 함수와
비트연산 함수들 ( &, |, ^, ~)연산을 제공합니다. 

우선 쉬운 길이관련 함수들부터 설명하겠습니다.

const unsigned __int64 BigInteger::bitlength() const
{
	blocktype LeftMostBlock = blk[len - 1];
	unsigned __int64 LeftMostBlockLen = 0;
	while (LeftMostBlock != 0)
	{
		LeftMostBlock >>= 1;
		LeftMostBlockLen++;
	}
	return LeftMostBlockLen + unsigned __int64( (len - 1) ) * N;
}
const BigInteger::length BigInteger::blklength() const
{
	return len;
}

(N은 블럭 하나의 비트수, 32를 나타냅니다.)
음... 이 글을 쓰면서 발견한 것이 있습니다.
Allocate 함수에서 len의 길이의 최대값을 0x1A934F0A로 제한하였습니다.
만약, BigInteger의 blk가 꽉 찼다면, 그 때의 비트 길이는 0x1A934F0A * 0x20 = 0x3,5269,E140로
length 타입인 unsigned long형의 최대값을 초과합니다.
그래서 bitlength 함수의 리턴타입을
BigInteger::length에서 unsigned __int64타입으로 바꾸었습니다. 
함수 자체가 어렵지 않으므로 쉽게 이해되시리라 생각됩니다. 

다음으로 비트연산 부분입니다.
&, |, ^연산은 인수의 부호에 따라 리턴값의 부호가 정해집니다.
아래가 그것을 정리한 것입니다.

/*
*	P : Positive
*	N : Negative
*	Z : Zero
*
*
*        a     b   ||   &    |    ^
*       ------------------------------
*        P     P   ||   P    P    P
*        P     N   ||   P    N    N
*        N     P   ||   P    N    N
*        N     N   ||   N    N    P
*
*	& 연산과 ^ 연산은 Z가 나올 가능성이 있다.
*/

우선 연산별, 함수 앞쪽에서 a, b가 Z인 경우는 처리하게 만듭니다.
그 후, 위 표대로 a, b 의 부호대로 결과값의 부호가 정해지게 됩니다.
그러나, 여기서 조심해야 할것이 있습니다.
&연산과 ^연산은 결과로 Z가 나올 수 있습니다. 
예로 2 & 4 연산은
2진법으로 바꿔서 보면
10 & 100이므로 0이 나오게 됩니다.
따라서, &연산과 ^연산은, 연산 후 0이 아닌지를 검사 해야합니다. 
위의 표를 이해하셨다면 이제 &연산함수의 코드를 보겠습니다.

const BigInteger BigInteger::operator &(const BigInteger &x) const
{
	if (this == &x)
		return *this;
	BigInteger temp;
	// 둘 중 하나가 0이라면 연산값은 0입니다.
	if (sign == Zero || x.sign == Zero)
		return temp;

	// temp의 길이는 둘 중 긴것으로 재할당합니다.
	temp.Reallocate( (len < x.len) ? len : x.len );

	index i;
	for (i = 0; i < temp.len; i++)
		temp.blk[i] = blk[i] & x.blk[i];

	temp.sign = (sign == Positive || x.sign == Positive) ? Positive : Negative;
	// 선두 0 블럭을 제거 합니다.
	temp.ZapLeadingZeros();
	// this와 x의 비트의 교집합이 하나도 없으면...
	// temp는 0입니다.
	if (temp.len == 1 && temp.blk[0] == 0)
		temp.sign = Zero;
	return temp;
}

음..
일단 기본적으로 this와 x가 같은 주소일경우를 처리합니다.
그 후, 둘의 부호가 0인지를 체크합니다.
&연산은 교집합 연산이므로 둘 중 하나라도 0이면 연산 할 필요 없이 결과값도 0입니다.
이제 연산을 위한 기본전제는 다 해결하였습니다.
temp는 기본생성자에 의해 현재 0으로 초기화 되어있습니다.
이제 temp에 연산결과를 대입해야 하므로 둘 중, 길이간 긴 len으로 temp의 len과 blk를 초기화 합니다.
그리고, &연산 값을 대입하지요.
temp의 부호는 위의 표대로 대입하였습니다.
다음으로 ZapLeadingZeros함수를 호출하여 연산 결과 0이 되는 blk를 높은 자리에서부터 검사합니다.
그러다 만에하나 모든 블럭의 연산값이 0이라면 결과값은 0이 되어야 하므로 조사 후, 부호를 바꿔줍니다. |연산과 ^연산도 같은 구조로 되있기 때문에 생략하겠습니다. 연산별로 약간의 코드가 다르지만 쉽게 이해하실 수 있습니다. 

다음으로 ~연산입니다. ~연산은 정수형에서는 모든 비트를 반전시키는 연산으로 정의되있습니다. 그래서 처음에는 ~연산을 만들지 않을려고 했습니다. 왜냐하면 정의가 성립되지 않으니까요.. 그러나 ~연산을 정수형의 ~연산의 특징을 나타내는 연산으로 정의하는 식으로 해서 만들었습니다.
그 특징이란, 정수형 변수 a를 ~연산 시키면 -a -1이 나오게 됩니다. 즉, a가 1이면 ~a는 -2로, a가 0이면 -1이 나오는 것이지요.

따라서 위와같은 특징을 가지는 것으로 ~연산을 정의하였고 다음과 같이 만들었습니다.
 

const BigInteger BigInteger::operator ~() const
{
	BigInteger temp(*this);
	if (sign == Positive)
		temp.sign = Negative;
	else if (sign == Negative)
		temp.sign = Positive;
	temp -= _One;
	return temp;
}

(_One은 BigInteger형으로 정의된 1입니다.)
지역변수 temp를 this로 초기화 하였습니다.
그 후, 일단 부호를 반대로 바꿉니다.
 다음으로 1을 뺀 후에 리턴합니다.
아직 뺄셈 연산을 정의하지 않았기때문에
~연산은 만들 수 없습니다.
- 연산을 만든 후에 만드시면 됩니다.