HDU1134，HDU1261 大数

用以前的C改了个大数类,又机制地水了几题...

#ifndef HEADER_BIGINT
#define HEADER_BIGINT

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

class BigInt{
	public:
		BigInt();
		BigInt(int smallNum);
		BigInt(const BigInt &bigNum);
		BigInt(string num);										//todo...
		~BigInt();

		BigInt& operator =(const BigInt &rhs);
		BigInt operator +(const BigInt &rhs)const;
		BigInt operator -(const BigInt &rhs)const;
		BigInt operator *(const BigInt &rhs)const;
		BigInt operator /(const BigInt &rhs)const;				//大数除大数,单纯靠减法，速度太慢...
		BigInt operator /(const int rhs)const;					//大数除整型,速度还可以，但如果除超过WEI * WEI的数会有问题
																//因为其实现需要整数除法，WEI^3大于32位范围
	friend ostream& operator <<(ostream &out,const BigInt &bigNum);
	friend istream& operator >>(istream &in,BigInt &bigNum);	//todo...

	private:
		void add(const int *a,const int *b,int *res)const;		//a中数据与b中相加放入res中
		void sub(const int *a,int *res)const;		//
		void mul(const int *a,int *res)const;		//
		void div(const int *a,int *res)const;		//
	    bool larger(const int *a,const int *b)const;			//a表示数据大于b表示数据则返回真
	    int realLen(const int *arr)const;						//返回数组arr所表示数据真正占据数组长度
		void shiftLeft(int *arr,int cnt)const;					//数组左移cnt位，空出位填0，用于除法
		void shiftRight(int *arr,int cnt)const;					//数组右移cnt位，空出位填0，用于除法
		void alloc();											//为构造函数申请digits的空间

		static const int LEN;
		static const int WEI;

		enum SIGN{POSI,NEGI} sign;								//数据符号位
		int *digits;											//真正的数据
};

//最长表示数据LEN * WEI位
const int BigInt::LEN = 105;									//缓冲区长度
const int BigInt::WEI = 10000;									//每一位权重

ostream& operator <<(ostream &out,const BigInt &bigNum){
	if(bigNum.sign == BigInt::NEGI){
		out << "-";
	}

	//计算WEI的长度用于下面的格式化输出,第一次直接用4，结果改了WEI就悲剧了
	int bitWidth = -1;										
	int wei = BigInt::WEI;
	while(wei > 0){
		bitWidth++;
		wei /= 10;
	}

	int len = bigNum.realLen(bigNum.digits);					
	out << bigNum.digits[len - 1];

	for(int i = len - 2;i >= 0;i--){
		out.width(bitWidth);
		out.fill('0');
		out << bigNum.digits[i];
	}

	return out;
}

#endif

#include "BigInt.h"
#include <string.h>

BigInt::BigInt(){
	sign = POSI;
	alloc();
}

BigInt::BigInt(int smallNum){
	alloc();

	if(smallNum < 0){
		this ->sign = NEGI;
		smallNum = -smallNum;
	}
	int num = smallNum;
	int p = 0;
	while(num > 0){
		digits[p++] = num % WEI;
		num /= WEI;
	}
}

BigInt::BigInt(const BigInt &bigNum){
	alloc();

	this ->sign = bigNum.sign;
	for(int i = 0;i < LEN;i++){
		this ->digits[i] = bigNum.digits[i];
	}
}

BigInt::~BigInt(){
	delete digits;
}

void BigInt::alloc(){
	sign = POSI;
	digits = new int[LEN];
	for(int i = 0;i < LEN;i++){
		digits[i] = 0;
	}
}

BigInt& BigInt::operator =(const BigInt &rhs){
	if(this ->digits == NULL){
		alloc();
	}

	this ->sign = rhs.sign;
	for(int i = 0;i < LEN;i++){
		this ->digits[i] = rhs.digits[i];
	}

	return *this;
}

BigInt BigInt::operator +(const BigInt &rhs)const{
	BigInt res;

	if(this ->sign == POSI && rhs.sign == NEGI){
		BigInt t(rhs);
		t.sign = POSI;
		return *this - t;
	}
	else if(this ->sign == NEGI && rhs.sign == POSI){
		BigInt t(*this);
		t.sign = POSI;
		return rhs - t;
	}
	else if(this ->sign == NEGI && rhs.sign == NEGI){	
		res.sign = NEGI;
		add(this ->digits,rhs.digits,res.digits);
	}
	else{
		res.sign = POSI;
		add(this ->digits,res.digits);
	}

	return res;
}

void BigInt::add(const int *a,int *res)const{
	int carry = 0;
	int len = realLen(a) > realLen(b) ? realLen(a) : realLen(b);

	for(int i = 0;i <= len;i++){
		res[i] = (a[i] + b[i] + carry) % WEI;
		carry = (a[i] + b[i] + carry) / WEI;
	}
}

BigInt BigInt::operator -(const BigInt &rhs)const{
	BigInt res;

	if(this ->sign == POSI && rhs.sign == NEGI){
		res.sign = POSI;
		add(this ->digits,res.digits);
	}
	else if(this ->sign == NEGI && rhs.sign == NEGI){
		BigInt t(rhs);
		t.sign = POSI;
		return *this + t;
	}
	else if(this ->sign == NEGI && rhs.sign == POSI){
		res.sign = NEGI;
		add(this ->digits,res.digits);
	}
	else{
		if(larger(this ->digits,rhs.digits)){
			res.sign = POSI;
			sub(this ->digits,res.digits);
		}
		else{
			res.sign = NEGI;
			sub(rhs.digits,this ->digits,res.digits);
		}
	}

	return res;
}

void BigInt::sub(const int *a,int *res)const{
	int carry = 0;
	for(int i = 0;i < realLen(a);i++){
		int t = a[i] - b[i] - carry;
		res[i] = (t + WEI) % WEI;
		carry = 1 - (t + WEI) / WEI;
	}
}


BigInt BigInt::operator *(const BigInt &rhs)const{
	BigInt res;

	if(this ->sign  ^ rhs.sign){
		res.sign = NEGI;
	}
	else{
		res.sign = POSI;
	}
	
	mul(this ->digits,res.digits);

	return res;
}

void BigInt::mul(const int *a,int *res)const{
	for(int i = 0;i <= realLen(a);i++){
		int carry = 0;

		for(int j = 0;j <= realLen(b) && i + j < LEN;j++){
			int s = res[i + j] + a[i] * b[j] + carry;
			res[i + j] = s % WEI;
			carry = s / WEI;
		}
	}
}
BigInt BigInt::operator /(const int rhs)const{
	BigInt res;
	if(this ->sign ^ (rhs < 0)){
		res.sign = NEGI;
	}
	else{
		res.sign = POSI;
	}

	int carry = 0;
	for(int i = realLen(this ->digits) - 1;i >= 0;i--){
		res.digits[i] = (this ->digits[i] + carry * WEI) / rhs;
		carry = (this ->digits[i] + carry * WEI) % rhs;
	}

	return res;
}

BigInt BigInt::operator /(const BigInt &rhs)const{
	BigInt res;
	
	if(this ->sign ^ rhs.sign){
		res.sign = NEGI;
	}
	else{
		res.sign = POSI;
	}

	int *ta = new int[LEN];
	memcpy(ta,sizeof(int) * LEN);
	int *tb = new int[LEN];
	memcpy(tb,sizeof(int) * LEN);

	div(ta,tb,res.digits);

	delete tb;
	delete ta;

	return res;
}

void BigInt::div(const int *a,int *res)const{
	int la = realLen(a);
	int lb = realLen(b);

	if(la < lb){
		return;
	}

	int *ta = new int[LEN];
	memcpy(ta,a,b,sizeof(int) * LEN);

	shiftLeft(tb,la -lb);

	for(int i = la - lb;i >= 0;i--){
		while(!larger(tb,ta)){
			res[i]++;
			sub(ta,ta);
		}
		shiftRight(tb,1);
	}

	delete ta;
	delete tb;
}

void BigInt::shiftLeft(int *arr,int cnt)const{
	for(int i = LEN - 1;i >= cnt;i--){
		arr[i] = arr[i - cnt];
	}
	for(int i = cnt - 1;i >= 0;i--){
		arr[i] = 0;
	}
}
void BigInt::shiftRight(int *arr,int cnt)const{
	for(int i = LEN - 1;i > LEN - 1 - cnt;i--){
		arr[i] = 0;
	}
	for(int i = 0;i < LEN - cnt;i++){
		arr[i] = arr[i + cnt];
	}
}

bool BigInt::larger(const int *a,const int *b)const{
	for(int i = LEN - 1;i >= 0;i--){
		if(a[i] > b[i]){
			return true;
		}
		else if(a[i] < b[i]){
			return false;
		}
	}
	return false;
}

int BigInt::realLen(const int *arr)const{
	int len = LEN - 1;
	while(arr[len] == 0 && len > 0){
		len--;
	}
	return len + 1;
}