hugeinteger.cpp

一些C++的课件和实验源代码

		int length = m_nLength;
		if(right.m_nLength > m_nLength){
			length = right.m_nLength;
		}
		
		result.m_nLength = length;
		result.m_nSign = m_nSign;

		for(int i = 0; i < length; i++){
			unsigned __int64 sum = m_ulValue[i];
			sum = sum + right.m_ulValue[i] + carry;
			result.m_ulValue[i] = (unsigned int)sum;
			if(sum > 0xFFFFFFFF){
				carry = 1;
			}
			else{
				carry = 0;
			}
		}

		if(result.m_nLength < HI_MAXLEN){
			result.m_ulValue[result.m_nLength] = carry;
		    result.m_nLength += carry;
		}

		return result;
	}
	else{
		CHugeInteger negative = right;
		negative.m_nSign = 0 - negative.m_nSign;
		return *this - negative;
	}
}

CHugeInteger CHugeInteger::operator + (int right)
{
	return *this + CHugeInteger(right);
}

/*******************************************************\
 * 函数：operator += ()                                *
 * 功能：计算两个数相加的和                            *
 * 输入：right --- 加数                                *
 * 输出：无                                            *
 * 返回：*this,和                                      *
\*******************************************************/
CHugeInteger& CHugeInteger::operator += (CHugeInteger& right)
{
	*this = *this + right;
	return *this;
}

CHugeInteger& CHugeInteger::operator += (int right)
{
	*this = *this + right;
	return *this;
}

/*******************************************************\
 * 函数：operator ++ ()                                *
 * 功能：整数自加1                                     *
 * 输入：无                                            *
 * 输出：无                                            *
 * 返回：*this,加1后的整数                             *
\*******************************************************/
CHugeInteger& CHugeInteger::operator ++ ()
{
	*this = *this + 1;
	return *this;
}
	
/*******************************************************\
 * 函数：operator - ()                                 *
 * 功能：计算两个数相减后的差                          *
 * 输入：right --- 减数                                *
 * 输出：无                                            *
 * 返回：差                                            *
\*******************************************************/
CHugeInteger CHugeInteger::operator - (CHugeInteger& right)
{
	CHugeInteger result;
	
	if(m_nSign == 0){
		result = right;
		result.m_nSign *= -1;
		return result;
	}
	if(right.m_nSign == 0){
		result = *this;
		return result;
	}


	if(m_nSign == right.m_nSign)
	{
		if(m_nSign == 0){
			result = 0;
			return result;
		}

		int len = 0;
		int carry = 0;
		unsigned __int64 num = 0;
		unsigned int *s = NULL;
		unsigned int *d = NULL;

		CHugeInteger abs_left = *this;
		CHugeInteger abs_right = right;
		abs_left.m_nSign = 1;
		abs_right.m_nSign = 1;
		
		int cmp = abs_left.Compare(abs_right); 
		if(cmp == 0){
			result = 0;
			return result;
		}
	    else if(cmp > 0){
			s = abs_left.m_ulValue;
			d = abs_right.m_ulValue;
			len = abs_left.m_nLength;
		}
		else{	// < 0
			s = abs_right.m_ulValue;
			d = abs_left.m_ulValue;
			len = abs_right.m_nLength;
		}

	    for(int i = 0; i < len; i++){
			__int64 val1 = s[i];
			__int64 val2 = carry;
			__int64 val3 = d[i];
			if( (val1 - carry) >= val3 ){
		//	if( (s[i] - carry) >= d[i] ){
				result.m_ulValue[i] = s[i]- carry - d[i];
				carry = 0;
			}
			else{
				num = 0x100000000 + s[i];
				result.m_ulValue[i] = (unsigned int)(num - carry - d[i]);
				carry = 1;
			}
		}

		for(i = len; i > 0; i--){
			if(result.m_ulValue[i - 1] != 0){
				result.m_nLength = i;
				break;
			}
		}
		
		cmp = Compare(right);
		if( cmp > 0 ){
			result.m_nSign = 1;
		}
		else if( cmp < 0 ){
			result.m_nSign = -1;
		}
		else{
			result.m_nSign = 0;
		}

		return result;
	}
	else{
		CHugeInteger negative = right;
		negative.m_nSign = 0 - negative.m_nSign;
		return *this + negative;
	}
}

CHugeInteger CHugeInteger::operator - (int right)
{
	return *this - CHugeInteger(right);
}

/*******************************************************\
 * 函数：operator -= ()                                *
 * 功能：计算两个数相减后的差                          *
 * 输入：right --- 减数                                *
 * 输出：无                                            *
 * 返回：*this,差                                      *
\*******************************************************/
CHugeInteger& CHugeInteger::operator -= (CHugeInteger& right)
{
	*this = *this - right;
	return *this;
}

CHugeInteger& CHugeInteger::operator -= (int right)
{
	*this = *this - right;
	return *this;
}

/*******************************************************\
 * 函数：operator -- ()                                *
 * 功能：整数自减1                                     *
 * 输入：无                                            *
 * 输出：无                                            *
 * 返回：*this,减1后的整数                             *
\*******************************************************/
CHugeInteger& CHugeInteger::operator -- ()
{
	*this = *this - 1;
	return *this;
}

/*******************************************************\
 * 函数：operator * ()                                 *
 * 功能：计算两个数的相乘的乘积                        *
 * 输入：right --- 乘数                                *
 * 输出：无                                            *
 * 返回：乘积                                          *
\*******************************************************/
CHugeInteger CHugeInteger::operator * (CHugeInteger& right)
{
	CHugeInteger result;

	if(m_nSign == 0 || right.m_nSign == 0){
		result = 0;
		return result;
	}

	unsigned __int64 mul = 0;
    unsigned int carry = 0;
    for(int i = 0; i < right.m_nLength; i++){
		CHugeInteger temp = *this * right.m_ulValue[i];
		for(int k = temp.m_nLength + i - 1; k >= i; k--){
			temp.m_ulValue[k] = temp.m_ulValue[k - i];
		}
		for(k = 0; k < i; k++){
			temp.m_ulValue[k] = 0;
		}

		// add by wangtao,2004-08-12
		for(k = temp.m_nLength + i; k > 1; k--){
			if( temp.m_ulValue[k - 1] > 0){
				temp.m_nLength = k;
				break;
			}
		}
		//add end.

		result += temp;
	}

	if(m_nSign == right.m_nSign){
		result.m_nSign = 1;
	}
	else{
		result.m_nSign = -1;
	}

	for(i = HI_MAXLEN; i > 0; i--){
		if(result.m_ulValue[i - 1] != 0){
			result.m_nLength = i;
			break;
		}
	}

	return result;
}

/*******************************************************\
 * 函数：operator * ()                                 *
 * 功能：计算两个数的相乘的乘积                        *
 * 输入：right --- 乘数                                *
 * 输出：无                                            *
 * 返回：乘积                                          *
\*******************************************************/
CHugeInteger CHugeInteger::operator * (unsigned int right)
{
	CHugeInteger result;
	unsigned __int64 mul = 0;
	unsigned int carry = 0;
	
	if(right == 0 || m_nSign == 0){
		result = 0;
		return result;
	}

	for(int i = 0; i < m_nLength; i++){
		mul = m_ulValue[i];
		mul = mul * right + carry;
		result.m_ulValue[i] = (unsigned int)mul;
		carry = (unsigned int)(mul >> BITNUM_UINT );
	}

	result.m_nSign = m_nSign;
	if(right < 0){
		result.m_nSign *= -1;
	}

	result.m_nLength = m_nLength;
	if(carry && (result.m_nLength < HI_MAXLEN)){
		result.m_nLength++;
		result.m_ulValue[result.m_nLength - 1] = carry;
	}

	return result;
}

/*******************************************************\
 * 函数：operator *= ()                                *
 * 功能：计算两个数的相乘的乘积                        *
 * 输入：right --- 乘数                                *
 * 输出：无                                            *
 * 返回：*this,乘积                                    *
\*******************************************************/
CHugeInteger& CHugeInteger::operator *= (CHugeInteger& right)
{
	*this = *this * right;
	return *this;
}

CHugeInteger& CHugeInteger::operator *= (unsigned int right)
{
	*this = *this * right;
	return *this;
}

/*******************************************************\
 * 函数：operator / ()                                 *
 * 功能：计算两个数的相除的商                          *
 * 输入：right --- 除数                                *
 * 输出：无                                            *
 * 返回：商                                            *
\*******************************************************/
CHugeInteger CHugeInteger::operator / (unsigned int right)
{
	CHugeInteger result;
	
	if( right == 0 ){
		result =  0;
		return result;
	}

	if(m_nLength == 1){
		result.m_ulValue[0] = m_ulValue[0] / right;
		result.m_nLength = 1;
	}
	else{
		unsigned __int64 div = 0;
		unsigned int carry = 0;
		for(int i = m_nLength - 1; i >= 0; i--)
		{
			div = carry;
			div = (div << BITNUM_UINT ) + m_ulValue[i];
			
			result.m_ulValue[i] = (unsigned int)(div / right);
			carry = (unsigned int)(div % right);
		}

		result.m_nLength = m_nLength;
		if( result.m_ulValue[m_nLength - 1] == 0 ){
			result.m_nLength--;
		}
	}
	
	if( right < 0 ){
		result.m_nSign = m_nSign * (-1);
	}
	else{
		result.m_nSign = m_nSign;
	}
	
	if( result.m_nLength == 1 && result.m_ulValue[0] == 0 ){
		result.m_nSign = 0;
	}

	return result;
}

/*******************************************************\
 * 函数：operator / ()                                 *
 * 功能：计算两个数的相除的商                          *
 * 输入：right --- 除数                                *
 * 输出：无                                            *
 * 返回：商                                            *
\*******************************************************/
CHugeInteger CHugeInteger::operator / (CHugeInteger& right)
{
	CHugeInteger result = 0;
	CHugeInteger& left = *this;