大數的c++實作，包括加減乘法

采用vector<int>實作的大整型數類，重載了 +，-，*，+=，-=，*= 操作符；通過了 poj 2389 大數乘法的測試資料；别的不多說，上代碼，供大家學習交流。

#ifndef BIG_INT_HEAD
#define BIG_INT_HEAD
#include<iostream>
#include<vector>

using namespace std;

class BigInt{
private:
	vector<unsigned int> num;
	bool isPositive; // positive number or negative number
	int length; // the length of the vector being used
	
	int compare(const BigInt & n); // compare if abs(this) is bigger than abs(n)
	void plus(const BigInt & n); // add 2 BigInt with the same sign
	void minus(const BigInt & n); // minus 2 BigInt with the same sign
	void multi(const BigInt & n);
	void shrink(){
		for(int i=length-1;i>0&&num[i]==0;i--) //shrink length
			length--; //length will be at least 1
	}
public:
	static const int CARRY = 10000; // if(num[i]>CARRY) num[i]/CARRY should be carried to num[i+1]
	static const int DIGIT = 4; // correspond to CARRY

	
	BigInt& operator+=(const BigInt & n){
		bool help = (isPositive&&!n.isPositive) || (!isPositive&&n.isPositive); // opposite sign
		if(help){
			isPositive = !isPositive;
			*this -= n;
			isPositive = !isPositive;
		}
		else
			plus(n); 
		return *this;
	}
	BigInt& operator-=(const BigInt & n){
		bool help = (isPositive&&!n.isPositive) || (!isPositive&&n.isPositive); // opposite sign
		if(help){
			isPositive = !isPositive;
			*this += n;
			isPositive = !isPositive;
		}
		else
			minus(n); 
		return *this;
	}
	BigInt& operator*=(const BigInt & n){
		multi(n); 
		return *this;
	}
	BigInt& operator+(const BigInt & n){
		BigInt * nn = new BigInt(*this);
		*nn += n;
		return *nn;
	}
	BigInt& operator-(const BigInt & n){
		BigInt * nn = new BigInt(*this);
		*nn -= n;
		return *nn;
	}
	
	BigInt& operator*(const BigInt & n){
		BigInt * nn = new BigInt(*this);
		*nn *= n; 
		return *nn;
	}

	BigInt(const char s[]);
	BigInt():length(1),isPositive(1){num.push_back(0);}
	
	void printNum(){
		if(length<=0){
			throw -1;
		}
		if(!isPositive)
			cout<<'-';
		printf("%d",num[length-1]);
		for(int i=length-2;i>=0;i--)
			printf("%0*d",DIGIT,num[i]);
		
		cout<<endl;
	}

};

BigInt::BigInt(const char s[]){ // construct BigInt by a string like "123" or "-2345"
	length = 0;
	int i = 0;
	if(s[i]=='-'){
		isPositive = 0;
		i++;
	}
	else if(s[i]=='+'){
		isPositive = 1;
		i++;
	}
	int len = strlen(s);
	int val;
	for(int k=len;k>i;k-=DIGIT){
		val = 0;
		int j = k-DIGIT;
		if(j<i)
			j = i;
		for(;j<k;j++){
			if(s[j]>'9'||s[j]<'0'){
				//length = 0;
				throw -1;
			}
			val *= 10;
			val += s[j]-'0';
		}
		num.push_back(val);
		length ++;
	}
}

void BigInt::plus(const BigInt & n){ //add BigInt n to this
	int carry = 0;
	int i,t;
	if(&n==this){ // this += this; copy a new one to help
		BigInt nn = BigInt(n);
		plus(nn);
		return ;
	}
	for(;length<n.length;length++)
		num.push_back(0);
	for(i=0;i<n.length;i++){
		t = num[i] + n.num[i] + carry;
		num[i] = t % CARRY;
		carry = t / CARRY;
	}
	if(carry>0){
		for(;i<length&&carry;i++){
			t = num[i] + carry;
			num[i] = t % CARRY;
			carry = t / CARRY;
		}
		if(carry>0){
			length++; //expand length
			num.push_back(carry);
		}
	}
}

void BigInt::minus(const BigInt &n){
	BigInt const * nn1 = this;
	BigInt const * nn2 = &n;
	int cmp = compare(n);
	if(&n==this || cmp==0){ // result is 0
		num.clear();
		num.push_back(0);
		length = 1;
		return;
	}
	if(cmp<0){
		isPositive = !isPositive;
		nn1  = &n;
		nn2 = this;
	}
	const BigInt & n1 = *nn1;
	const BigInt & n2 = *nn2;
	for(;length<n.length;length++)
		num.push_back(0);
	int carry = 0; //borrow
	int i,t;
	for(i=0;i<n2.length;i++){ // n2.length<=n2.length
		t = n1.num[i] - n2.num[i] - carry;
		if(t<0){
			t += CARRY;
			carry = 1;
		}
		num[i] = t;
	}
	if(carry>0){
		for(;i<n1.length&&carry;i++){
			t = n1.num[i] - carry;
			if(t<0){
				t += CARRY;
				carry = 1;
			}
			num[i] = t;
		}
	}
	shrink();
}

void BigInt::multi(const BigInt &n){
	if((isPositive&&!n.isPositive)||(!isPositive)&&n.isPositive)
		isPositive = 0;
	else
		isPositive = 1;
	if(&n==this){
		BigInt n2(n);
		multi(n2);
		return;
	}
	int t,c;
	BigInt nn(*this);
	*this -= *this; // set to zero
	for(int i=0;i<n.length;i++){
		for(int j=0;j<nn.length;j++){
			t = n.num[i]*nn.num[j];
			c = t/CARRY;
			BigInt tn;
			tn.length += (i+j);
			tn.num.clear();
			for(int k=0;k<i+j;k++)
				tn.num.push_back(0);
			tn.num.push_back(t%CARRY);
			if(c){
				tn.length++;
				tn.num.push_back(c);
			}
			*this+=tn;
		}
	}
}

/**
	compare the abs value of the two BigInt
**/
int BigInt::compare(const BigInt & n){ 
	if(length>n.length)
		return 1;
	if(length<n.length)
		return -1;
	for(int i=length-1;i>=0;i--){
		if(num[i]>n.num[i]) 
			return 1;
		if(num[i]<n.num[i]) 
			return -1;
	}
	return 0;
}

#endif