1001.cpp

大整数运算示例代码

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
typedef string::size_type IND;

class BigNum{
private:
	string integer;
	string after;	
public:
	explicit BigNum(string& src){
		IND point;
		if((point = src.find('.')) == string::npos){
			integer = src;		
		}else{
			integer = src.substr(0, point);
			after = src.substr(point);
			after.erase(0,1);
		}	
	}
	explicit BigNum(){}	
	
	string& getInteger(){return integer;}
	string& getAfter(){return after;}
	
	void strip()
	{
		//strip the leading '0' and tailing '0'
		IND leading_not_0, tail_not_0;
		if((leading_not_0 = integer.find_first_not_of('0')) != (IND)0){		
			integer.erase(0, leading_not_0);
		}
		if((tail_not_0 = after.find_last_not_of('0')) != after.length() - 1){
			if(tail_not_0 != string::npos)			
				after.erase(tail_not_0 + 1);
			else
				after.clear();
		}
	}
	
	void Add(BigNum& adder)
	{
		string& adderInt = adder.getInteger();
		string& adderAft = adder.getAfter();		
		string newInt = integer;
		string newAft = after;
		
		//make After part length the same
		if(newAft.length() > adderAft.length()){
			adderAft.append(newAft.length() - adderAft.length() , '0');
		}else if(newAft.length() < adderAft.length()){
			newAft.append(adderAft.length() - newAft.length(), '0');
		}
		
		//make integer part length the same
		if(newInt.length() > adderInt.length()){
			adderInt.insert(0, newInt.length() - adderInt.length(), '0');
		}else if(newInt.length() < adderInt.length()){
			newInt.insert(0, adderInt.length() - newInt.length(), '0');
		}
		
		//add after part
		int i, carry = 0;
		for(i=adderAft.length() - 1; i>=0; i--){
			char res = adderAft[i] - '0' + newAft[i] - '0' + carry;			
			if(res > 9){
				carry = 1;
				res -= 10;
			}else{
				carry = 0;
			}
			newAft[i] = res + '0';
		}
		//add integer part
		for(i=adderInt.length() - 1; i>=0; i--){
			char res = adderInt[i] - '0' + newInt[i] - '0' + carry;
			if(res > 9){
				carry = 1;
				res -= 10;
			}else{
				carry = 0;
			}
			newInt[i] = res + '0';				
		}
		//take care if highest carry = 1
		if(carry == 1){
			newInt.insert(0, 1, '1');
		}
		
		//assign to the private member
		integer = newInt;			
		after = newAft;
	}
	
	void power2(){ // BigNum^2
		strip(); //strip leading and tailing '0'
		string whole = integer + after;
		BigNum newone; //0
		
		int i, j, tail_add0 = -1;
		//multiply
		for(i=whole.length() - 1; i>=0; i--){
			tail_add0 ++;
			int multier = whole[i] - '0';
			if(multier == 0)
				continue;

			int carry = 0;
			string oneres;
			
			for(j=whole.length() - 1; j>=0; j--){
				int multiee = whole[j] - '0';
				int mod = (multier * multiee + carry) % 10;
				carry = (multier * multiee + carry) / 10;
				oneres.insert(0, 1, mod + '0');
			}
			if(carry != 0)
				oneres.insert(0, 1, carry + '0');			
			
			oneres.append(tail_add0, '0'); //append 0;
			
			BigNum temp(oneres);
			newone.Add(temp); //add the temp multi
		}
		
		int aftercnt = after.length() * 2;
		if(aftercnt > newone.getInteger().length()) //if too much after period, add 0 before
			newone.getInteger().insert(0, aftercnt - newone.getInteger().length(), '0');		
		integer = newone.getInteger().substr(0, newone.getInteger().length() - aftercnt);
		after = newone.getInteger().substr(newone.getInteger().length() - aftercnt, aftercnt);				
	}

	void Multiply(BigNum& another)
	{
		strip();
		another.strip();

		string thisone = integer + after;
		string thatone = another.getInteger() + another.getAfter();
		BigNum newone;

		int i,j, tail_add0 = -1;
		//thisone * thatone
		for(i=thatone.length() - 1; i>=0; i--){
			tail_add0 ++;
			int multier = thatone[i] - '0';
			if(multier == 0)
				continue;

			int carry = 0;
			string oneres;

			for(j=thisone.length()-1; j>=0; j--){
				int multiee = thisone[j] - '0';
				int mod = (multier * multiee + carry ) % 10;
				carry = (multier * multiee + carry ) / 10;
				oneres.insert(0, 1, mod + '0');
			}
			if(carry != 0)
				oneres.insert(0, 1, carry + '0');
			
			oneres.append(tail_add0, '0');
			BigNum temp(oneres);
			newone.Add(temp); //add the temp multi
		}

		int aftercnt = after.length() + another.getAfter().length();
		if(aftercnt > newone.getInteger().length()) //if too much after period, add 0 before
			newone.getInteger().insert(0, aftercnt - newone.getInteger().length(), '0');		
		integer = newone.getInteger().substr(0, newone.getInteger().length() - aftercnt);
		after = newone.getInteger().substr(newone.getInteger().length() - aftercnt, aftercnt);
	}
	
	friend ostream& operator << (ostream& os, BigNum & bn){
		bn.strip();
		string& integer = bn.getInteger();
		string& after = bn.getAfter();
		
		if(integer.length() == 0 && after.length() == 0){
			os << 0 << endl;			
		}else if(integer.length() == 0){
			os << "." << after <<endl;			
		}else if(after.length() == 0){
			os << integer << endl;			
		}else{
			os << integer << "." << after << endl;
		}
		
		return os;		
	}		
};

int main()
{
	string src;
	string init("1");
	int e;
	
	while(cin >> src >> e){
		BigNum bn(src), res(init);
		while(e > 0){
			if(e & 1){
				res.Multiply(bn);
			}	
			e = e >> 1;
			if(e > 0)
				bn.power2();
		}
		cout << res;
	}
	return 0;
}