hugeint.cpp

将大数看作一个n进制数组

// HugeInt_try.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdlib.h"
#include "HugeInt.h"
#include <iostream>
using namespace std;


//构造函数
HugeInt::HugeInt()
{
	m_nSign = 1;
	m_nLength = 1;
	for(int i = 0;i<BI_MAXLEN;i++)
		m_ulValue[i] = 0;
}

//通过实现成员变量构造函数
HugeInt::HugeInt(int sign,int length,unsigned long value[BI_MAXLEN])
{
	m_nSign = sign;
	m_nLength = length;
	for(int i = 0;i<m_nLength;i++)
		m_ulValue[i] = value[i];
	for(i = m_nLength;i<BI_MAXLEN;i++)
		m_ulValue[i] = 0;
}
//构造函数-HugeInt
HugeInt::HugeInt(HugeInt& A)
{
	//设定符号
	m_nSign = A.m_nSign;
	//设定大数的长度
	m_nLength = A.m_nLength;
	//为大数的每一位的数值赋值
	for(int i=0; i<m_nLength; i++)
		m_ulValue[i] = A.m_ulValue[i];
	for(i = m_nLength;i<BI_MAXLEN;i++)
		m_ulValue[i] = 0;
}
//构造函数-long
HugeInt::HugeInt(long A)
{
	if(A<0)
		m_nSign = -1;//-1为负号
	else
		m_nSign = 1;//1为正号
	m_nLength = 1;
	m_ulValue[0] = (unsigned long)A;
	for(int i = m_nLength;i<BI_MAXLEN;i++)
		m_ulValue[i] = 0;
}
//构造函数-字符串
HugeInt::HugeInt(CString& A)
{
	//判断符号
	if(A.Left(1)=="-")
	{
		m_nSign = -1;
		A = A.Right(A.GetLength()-1);
	}
	else
		m_nSign = 1;	
	//X用来表示临时被除数，Y用来除数,U用来表示临时商,Z用来表示余数,W用来表示商
	HugeInt X,Y,Z,U,W;
	//x用来表示被除数
	int count;
	//HugeInt W = new HugeInt();
	count = A.GetLength();
	if((count > 10)||(_atoi64(A)>0xffffffff))
	{
		CString tempA;
		//为除数赋值
		__int64 a = 0x100000000;
		Y = a;
		//方法：先除前10位,得到的余数再加上一位继续除,最终会得到余数和商。把它们加在一起就是HugeInt
		tempA = A.Left(11);
		//为被除数赋值
		X = _atoi64(tempA);
		int i = 0;
		//不能直接转化
		while((X.Cmp(Y)>0) || (i+11 <=A.GetLength()))
		{
			//用求商+求余(除数为0xffffffff)的方法得到HugeInt
			//得到临时商
			U = X/Y;
			//得到临时余数,最后一次求余的结果为最终的余数
			Z = X%Y;
			//最终商数向右移一位
			if(W != 0)
			{
				W *= 10;
			/*	W.m_nLength += 1;
			for(int j=W.m_nLength-1; j>=1; j--)
				W.m_ulValue[j] = W.m_ulValue[j-1];
			for(j=0; j<1;j++)
				W.m_ulValue[j] =0;*/
			}
			//把临时商数写入最终商数
			W =W + U;
			i += 1;
			//重新生成tempA,继续进行计算
			if(A.GetLength() >= (11+i))
			{
				CString p1 = A.Left(11+1);
				CString p2 = p1.Right(1);
				tempA = (A.Left(11+i)).Right(1) + Z.toString();
				X = _atoi64(tempA);
			}
			else 
				X = Z;
			
		}
		//得到最后的结果
		W.m_nLength+=1;
		for(int k=W.m_nLength-1;k>=1;k--)
			W.m_ulValue[k]=W.m_ulValue[k-1];
		W.m_ulValue[0]=0;
		
		W =W + Z;
		*this = W;
		for(i = m_nLength;i<BI_MAXLEN;i++)
			m_ulValue[i] = 0;
	}
	//直接转化
	else
	{
		long lA = atol(A);
		*this = HugeInt(lA);
	}	
}

//析构函数
HugeInt::~HugeInt()
{

}

//将大数赋值为另一个大数
HugeInt& HugeInt::operator=(HugeInt& A)
{
	//设定符号
	m_nSign = A.m_nSign;
	//设定大数的长度
	m_nLength = A.m_nLength;
	//为大数的每一位的数值赋值
	for(int i=0; i<m_nLength; i++)
		m_ulValue[i] = A.m_ulValue[i];
	for(i=m_nLength; i<BI_MAXLEN;i++)
		m_ulValue[i] = 0;
	return *this;
}
//将大数赋值为编译器能够理解的任何整形常数或变量 
HugeInt& HugeInt::operator=(unsigned __int64 A)
{
	if(A<0)
		m_nSign = -1;//-1为负号
	else
		m_nSign = 1;//1为正号
	//如果A>0xffffffff就为A进一位
	if(A>0xffffffff)
	{
		m_nLength=2;
		m_ulValue[1]=(unsigned long)(A>>32);
		m_ulValue[0]=(unsigned long)A;
	}
	else
	{
		m_nLength=1;
		m_ulValue[0]=(unsigned long)A;
	}
	for(int i=m_nLength;i<BI_MAXLEN;i++)
		m_ulValue[i]=0;
	return *this;
}


int HugeInt::Cmp(HugeInt& A)
{
	//比较两个大数的长度，长度长的数大
	if(m_nLength > A.m_nLength)
		return 1;
	if(m_nLength < A.m_nLength)
		return -1;

	//如果长度一样，说明位数一样。
	//则从位数高的数值开始比较，数值大的数大。否则继续比较位数较低的数值	
	for(int i= m_nLength -1; i>=0;i--)
	{
		if(m_ulValue[i] > A.m_ulValue[i])
			return 1;
		if(m_ulValue[i]<A.m_ulValue[i])
			return -1;
	}
	//如果两个大数一样大，则返回0
	return 0;
}

//计算两个大数的和
HugeInt HugeInt ::operator+(HugeInt& A)
{
	HugeInt X;
	//判断两个数的正负号是否相同，相同做加法
	if(X.m_nSign == A.m_nSign)
	{
		//给X赋值
		X=(*this);
		//carry记录A+X的进位
		int carry = 0;
		unsigned __int64 sum = 0;
		//如果A的长度>X的长度，X的长度赋值为A的长度,否则不变
		if(X.m_nLength < A.m_nLength)
			X.m_nLength = A.m_nLength;
		//做加法
		for(int i=0 ; i<X.m_nLength; i++)
		{
			sum = A.m_ulValue[i];
			sum = sum + X.m_ulValue[i] + carry;
			X.m_ulValue[i] = (unsigned long)sum;
			//如果sum > 0xffffffff则进一位。
			if(sum > 0xffffffff)
				carry = 1;
			else
				carry = 0;
		}
		//加完最后一位,如果进位不等于0则，X的长度+1,并把新加的最大位赋值为carry
		if(X.m_nLength < BI_MAXLEN)
		{
			X.m_ulValue[X.m_nLength] = carry;
			X.m_nLength += carry;
		}
		//如果长度超过BI_MAXLEN，只返回X
		return X;
	}
	//判断两个数的正负号是否相同，不同做减法
	else
	{
		A.m_nSign = -1 * (A.m_nSign);
		return (X-A);
	}	
}

//计算大数和long相加
HugeInt HugeInt::operator+(long A)
{
	//利用operator+(HugeInt& A)完成操作
	HugeInt X = *this;
	HugeInt hiA(A);

	return (X+ hiA);
}

//计算大数和字符串相加
HugeInt HugeInt::operator+(CString& A)
{
	//利用operator+(HugeInt& A)完成操作
	HugeInt X = *this;
	HugeInt hiA(A);

	return (X+ hiA);
}

//与另一个大数做加法,并把结果给自己
HugeInt& HugeInt::operator+=(HugeInt& A)
{
	HugeInt X = *this;
	X = X + A;
	*this= X;
	return *this;
}

//与long做加法,并把结果给自己
HugeInt&  HugeInt::operator+=(long A)
{
	HugeInt X = *this;
	X = X + A;
	*this= X;
	return *this;
}

//与字符串做加法,并把结果给自己
HugeInt&  HugeInt::operator+=(CString& A)
{
	HugeInt X = *this;
	X = X + A;
	*this= X;
	return *this;
}


//计算两个大数的差
HugeInt HugeInt::operator-(HugeInt& A)
{
	HugeInt X;
	//做减法
	if(m_nSign == A.m_nSign)
	{
		//为X赋值
		X=(*this);
		//比较X与A,X>A返回cmp=1,X<A返回cmp=-1,X=A返回0
		int cmp = X.Cmp(A);
		//X=A
		if(cmp == 0)
		{
			X= 0;
			return   X;
		}
		//len为在做减法时记录X的长度;carry为做减法时的借位数
		int len,carry = 0;
		unsigned __int64 num;
		unsigned long *s,*d;
		//X>A
		if(cmp > 0)
		{
			s= X.m_ulValue;
			d= A.m_ulValue;
			len = X.m_nLength;
		}
		//X<A
		if(cmp < 0)
		{
			s= X.m_ulValue;
			d= A.m_ulValue;
			len = A.m_nLength;
			//符号改变
			X.m_nSign = -1 * X.m_nSign;
		}
		for(int i=0; i<len;i++)
		{
			//不需要借位　carry = 0;
			if((s[i] - carry)>= d[i])
			{
				X.m_ulValue[i] = s[i] - carry - d[i];
				carry = 0;
			}
			//需要借位　carry = 1;
			else
			{
				//借一位为：0x100000000
				num = 0x100000000 + s[i];
				X.m_ulValue[i] = (unsigned long)(num-carry-d[i]);
				carry = 1;
			}
		}
		//如果最大一位数的数值等于0那么，大数的长度减1
		while(X.m_ulValue[len -1] ==0)
			len--;
		X.m_nLength = len;
		return  X;
	}
	//做加法
	else
	{
		A.m_nSign = -1 * A.m_nSign;
		return (X+ A);
	}
}

//计算大数和long相减
HugeInt HugeInt::operator-(long A)
{
	//利用operator-(HugeInt& A)完成操作
	HugeInt X = *this;
	HugeInt hiA(A);

	return (X- hiA);
}

//计算大数和字符串相减
HugeInt HugeInt::operator-(CString& A)
{
	//利用operator-(HugeInt& A)完成操作
	HugeInt X = *this;
	HugeInt hiA(A);

	return (X- hiA);
}

//与另一个大数做减法,并把结果给自己
HugeInt& HugeInt::operator-=(HugeInt& A)
{
	HugeInt X = *this;
	X = X - A;

	*this= X;
	return *this;
}

//与long做减法,并把结果给自己
HugeInt& HugeInt::operator-=(long A)
{
	HugeInt X = *this;
	X = X -A;
	*this= X;
	return *this;
}

//与字符串做减法,并把结果给自己
HugeInt& HugeInt::operator-=(CString& A)
{
	HugeInt X = *this;
	X = X - A;
	
	*this= X;
	return *this;
}

//计算两个大数的积
HugeInt HugeInt::operator*(HugeInt& A)
{
	//X用来存放结果,Y用来表示this
	HugeInt X,Y;
	unsigned __int64 mul;
	//carry用来表示进位
	unsigned long carry;
	//A的每位进行计算
	for(int i=0;i<A.m_nLength;i++)
	{
		Y.m_nLength = m_nLength;
		carry = 0;
		//this的每位进行计算
		for(int j=0;j<m_nLength;j++)
		{
			mul = m_ulValue[j];
			mul = mul * A.m_ulValue[i] + carry;
			Y.m_ulValue[j] = (unsigned long)mul;
			carry = (unsigned long)(mul>>32);
		}
		//如果carry>0,并且Y.m_nLength没有超出范围,就给Y进一位并把carry赋值给Y的最大位
		if(carry&&(Y.m_nLength<BI_MAXLEN))
		{
			Y.m_nLength++;
			Y.m_ulValue[Y.m_nLength-1] = carry;
		}
		//乘法规则，移位相加
		if(Y.m_nLength<BI_MAXLEN - i)
		{
			Y.m_nLength += i;
			for(int k=Y.m_nLength -1; k>=i;k--)
			{
				Y.m_ulValue[k] = Y.m_ulValue[k-i];
			}
			for(k = 0;k<i;k++)
			{
				Y.m_ulValue[k] = 0;
			}
		}
		X=X+Y;
	}
	//正负号号
	if(m_nSign*A.m_nSign == -1)
		X.m_nSign = -1;
	else
		X.m_nSign = 1;
	
	return X;
}

//计算大数和long相乘
HugeInt HugeInt::operator*(long A)
{
	//利用operator*(HugeInt& A)完成操作
	HugeInt X = *this;
	HugeInt hiA(A);

	
	return (X*hiA);
}

//计算大数和字符串相乘
HugeInt HugeInt::operator*(CString& A)
{
	//利用operator*(HugeInt& A)完成操作
	HugeInt X = *this;
	HugeInt hiA(A);

	return (X*hiA);
}