博客

大整数在笔面试中也是常考的，所以抽时间自己实现了一个大整数类，思想是通过一个vector<int> 来存储数据，每一个元素代表万进制大整数中的一位。具体程序如下：

#include "stdafx.h"
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <vector>
using namespace std;

class BigInt
{
public:
	//利用字符串来构造一个大整数
	BigInt(string s)
	{
		int left=0;
		symbol=1; //默认为正数  
		if (s.size()>0)
		{
			if (s[0]=='-')
			{
				symbol=-1;
				left=1;
			}
			else if (s[0]=='+')
			{
				
				left=1;
			}
		}
		for (int i=s.size();i>left;i-=REDIX_LEN)
		{
			int low=max(i-REDIX_LEN,left);
			int result=0;
			for (int j=low;j<i;++j)
			{
				result=result*10+s[j]-'0';
			}
			elem.push_back(result);
		}
	}
	//将大整数转化为字符串，用于输出
	string toString()
	{
		stringstream result;
		bool flag=false; //标记是否在操作最高位
		for (int i=elem.size()-1;i>=0;--i)
		{	
			if (flag)  //跳过了最高位,每一位都需要以四位长度等宽输出，不足左边补0
			{
				result<<setfill('0')<<setw(4)<<elem[i];

			}
			else
			{
				//最高位需要特殊处理，因为可能需要输出负号，且不足4位不用补0
				if (symbol==-1)
				{
					result<<'-';
				}
				result<<elem[i];
				flag=true;
			}
				
		}
		if (!flag)  //如果elem为空，输出0
		{
			return "0";
		}
		return result.str();
	}
	//相当于两个数的绝对值相加，不考虑符号
	static BigInt add(const BigInt &x,const BigInt &y)
	{
		int maxLen=max(x.elem.size(),y.elem.size())+1;  //两个数和不会超过最大数的位数+1
		vector<int> z(maxLen,0);
		int i=0;
		for (;i<x.elem.size() && i<y.elem.size();++i)
		{
			z[i]+=x.elem[i]+y.elem[i];
			int carry=z[i]/BIGINT_REDIX;
			z[i]%=BIGINT_REDIX;
			z[i+1]+=carry;
		}
		while(i<x.elem.size())
		{
			z[i]+=x.elem[i];
			int carry=z[i]/BIGINT_REDIX;
			z[i]%=BIGINT_REDIX;
			z[i+1]+=carry;
			++i;
		}
		while(i<y.elem.size())
		{
			z[i]+=y.elem[i];
			int carry=z[i]/BIGINT_REDIX;
			z[i]%=BIGINT_REDIX;
			z[i+1]+=carry;
			++i;
		}
		//去掉高位中的0
		while(!z.empty() && z.back()==0)
		{
			z.pop_back();
		}
		return BigInt(z,1);
	}
	BigInt operator+(const BigInt &rhs)
	{
		if (this->symbol==1 && rhs.symbol==1)  //两个正数相加
		{
			return add(*this,rhs);
		}
		else if (this->symbol==-1 && rhs.symbol==-1)  //两个负数相加
		{
			BigInt tmp=add(*this,rhs);
			tmp.symbol=-1;
			return tmp;
		}
		else if (this->symbol==1)    //正数加上负数
		{
			if (*this>=rhs)
			{
				return sub(*this,rhs);
			}
			else
			{
				BigInt tmp=sub(rhs,*this);
				tmp.symbol=-1;
				return tmp;
			}
		}
		else            //负数加上正数
		{
			if (*this>=rhs)
			{
				BigInt tmp=sub(*this,rhs);
				tmp.symbol=-1;
				return tmp;
			}
			else
			{
				return sub(rhs,*this);
			}
		}
	}

	//x必须大于y，且两者都非负
	static BigInt sub(const BigInt &x,const BigInt &y)
	{
		vector<int> z(x.elem.size()+1,0);  //因为x>y所以，x-y位数不会超过x的位数+1
		int i=0;
		for (;i<y.elem.size();++i)
		{
			z[i]+=x.elem[i]-y.elem[i];
			if (z[i]<0)
			{
				z[i]+=BIGINT_REDIX;
				z[i+1]-=1;
			}
		}
		while(i<x.elem.size())
		{
			z[i]+=x.elem[i];
			if (z[i]<0)
			{
				z[i]+=BIGINT_REDIX;
				z[i+1]-=1;
			}
			++i;
		}
		while(!z.empty() && z.back()==0)
		{
			z.pop_back();
		}
		return BigInt(z,1);
	}
	BigInt operator-(const BigInt &rhs)
	{
		if (this->symbol==1 && rhs.symbol==1)  //正数减正数
		{
			if (*this>=rhs)
			{
				return sub(*this,rhs);
			}
			else
			{
				BigInt tmp=sub(rhs,*this);
				tmp.symbol=-1;
				return tmp;
			}

		}
		else if (this->symbol==-1 && rhs.symbol==-1)  //负数减负数
		{
			if (*this>=rhs)
			{
				BigInt tmp=sub(*this,rhs);
				tmp.symbol=-1;
				return tmp;
			}
			else
			{
				return sub(rhs,*this);
			}
		}
		else if (this->symbol==1)   //正数减负数
		{
			return add(*this,rhs);
		}
		else                        //负数减正数
		{
			BigInt tmp=add(*this,rhs);
			tmp.symbol=-1;
			return tmp;
		}
	}
	//判断个大整数的绝对值大小
	bool operator>=(const BigInt &rhs)
	{
		if (this->elem.size()>rhs.elem.size())
		{
			return true;
		}
		else if (this->elem.size()<rhs.elem.size())
		{
			return false;
		}
		else
		{
			for (int i=this->elem.size()-1;i>=0;--i)
			{
				if (this->elem[i]<rhs.elem[i])
				{
					return false;
				}
			}
			return true;
		}
	}
	//大整数乘积，考虑了符号
	static BigInt multiply(const BigInt &x,const BigInt &y)
	{
		vector<int> z(x.elem.size()+y.elem.size(),0);
		for (int i=0;i<x.elem.size();++i)
		{
			for (int j=0;j<y.elem.size();++j)
			{
				z[i+j]+=x.elem[i]*y.elem[j];
				int carry=z[i+j]/BIGINT_REDIX;
				z[i+j]%=BIGINT_REDIX;
				z[i+j+1]+=carry;
			}
		}
		while(!z.empty() && z.back()==0)
		{
			z.pop_back();
		}
		//判断乘积的符号
		int flag=1;
		if (x.symbol*y.symbol<0)
		{
			flag=-1;
		}
		return BigInt(z,flag);
	}
	BigInt operator*(const BigInt &rhs)
	{
		return multiply(*this,rhs);
	}

	static BigInt div(const BigInt &x,const BigInt &y)
	{
		vector<int> z(x.elem.size()+1,0);
		vector<int> tmpY(x.elem.size(),0);
		BigInt tmpX(x);
		const int times=x.elem.size()-y.elem.size();
		//tmpY看成y中elem的副本左移到和x中elem位数一样多的结果
		for (int i=x.elem.size()-1;i>=0 ;--i)
		{
			if (i>=times)
			{
				tmpY[i]=y.elem[i-times];
			}
			else
			{
				tmpY[i]=0;
			}
		}
		/* 先减去若干个 y×(10000 的 times 次方)，
		不够减了，再减去若干个 y×(10000 的 times-1 次方)
		一直减到不够减为止 */
		for (int i=0;i<=times;++i)
		{
			const BigInt tmpInt(tmpY,1);
			while(tmpX>=tmpInt)
			{
				++z[times-i];
				tmpX=sub(tmpX,tmpInt);
			}
			for (int j=0;j<tmpY.size()-1;++j)
			{
				tmpY[j]=tmpY[j+1];
			}
			tmpY.pop_back();
		}
		//统一处理进位
		for (int i=0;i<z.size()-1;++i)
		{
			int carry=z[i]/BIGINT_REDIX;
			z[i]%=BIGINT_REDIX;
			z[i+1]+=carry;
		}
		//去掉高位的0
		while(!z.empty() && z.back()==0)
		{
			z.pop_back();
		}
		//判断商的符号
		int flag=1;
		if (x.symbol*y.symbol<0)
		{
			flag=-1;
		}
		return BigInt(z,flag);
	}
	BigInt operator/(const BigInt &rhs)
	{
		return div(*this,rhs);
	}
private:
	//用于运算中返回结果时，根据elem构造大整数
	BigInt(vector<int> vec,int flag):elem(vec),symbol(flag){};
	vector<int> elem;  //大整数的数据，每一个元素代表万进制中的一位
	int symbol; //1为正，-1为负
	//万进制的数,vector中的每一个元素当做大整数的万进制的一位
	static const int REDIX_LEN=4;
	static const int BIGINT_REDIX=10000;

};

int _tmain(int argc, _TCHAR* argv[])
{
	string x;
	string y;
	while(cin>>x>>y)
	{
		BigInt first(x),second(y);
		cout<<"两个数的和为： "<<(first+second).toString()<<endl;
		cout<<"两个数的差为： "<<(first-second).toString()<<endl;
		cout<<"两个数的积为： "<<(first*second).toString()<<endl;
		cout<<"两个数的商为： "<<(first/second).toString()<<endl;
	}
	return 0;
}

程序运行结果如下：