// big_integer.h
#include <string>
#include <vector>
#include <iostream>
using namespace std;
class NumberFormatException
{
private:
string str;
public:
NumberFormatException(string);
friend ostream& operator<<(ostream&,const NumberFormatException&);
};
class DividedByZeroException
{
private:
string str;
public:
DividedByZeroException(string);
friend ostream& operator<<(ostream&,const DividedByZeroException&);
};
class big_integer
{
private:
vector<char> digits; //
bool sign; // true for positive, false for negitive
void trim(); // remove zeros in tail, but if the value is 0, keep only one:)
public:
explicit big_integer(long); // construct with a long integer
explicit big_integer(string&)throw(NumberFormatException);
// construct with a string, which must be all integers-bits
// a sign can also be included. if the format is wrong, this will generate an Exception
big_integer(const big_integer&);
big_integer operator=(const big_integer& op2){
digits = op2.digits;
sign = op2.sign;
return (*this);
}
big_integer abs()const{
if( sign ) return *this;
else return -(*this);
}
//binary operators
friend big_integer operator+=(big_integer&,const big_integer&);
friend big_integer operator-=(big_integer&,const big_integer&);
friend big_integer operator*=(big_integer&,const big_integer&);
friend big_integer operator/=(big_integer&,const big_integer&)throw(DividedByZeroException);
friend big_integer operator%=(big_integer&,const big_integer&)throw(DividedByZeroException);
friend big_integer operator+(const big_integer&,const big_integer&);
friend big_integer operator-(const big_integer&,const big_integer&);
friend big_integer operator*(const big_integer&,const big_integer&);
friend big_integer operator/(const big_integer&,const big_integer&)throw(DividedByZeroException);
friend big_integer operator%(const big_integer&,const big_integer&)throw(DividedByZeroException);
//uniary operators
friend big_integer operator-(const big_integer&); //negative
friend big_integer operator++(big_integer&); //++v
friend big_integer operator++(big_integer&,int); //v++
friend big_integer operator--(big_integer&); //--v
friend big_integer operator--(big_integer&,int); //v--
friend bool operator>(const big_integer&,const big_integer&);
friend bool operator<(const big_integer&,const big_integer&);
friend bool operator==(const big_integer&,const big_integer&);
friend bool operator!=(const big_integer&,const big_integer&);
friend bool operator>=(const big_integer&,const big_integer&);
friend bool operator<=(const big_integer&,const big_integer&);
friend ostream& operator<<(ostream&,const big_integer&); //print the big_integer
};
const big_integer ZERO(0);
const big_integer ONE(1);
// big_integer.cpp
#include <list>
#include <deque>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include "big_integer.h"
using namespace std;
NumberFormatException::NumberFormatException(string s):str(s){}
ostream& operator<<(ostream& stream,const NumberFormatException& exception){
stream << exception.str;
return stream;
}
DividedByZeroException::DividedByZeroException(string s):str(s){}
ostream& operator<<(ostream& stream,const DividedByZeroException& exception){
stream << exception.str;
return stream;
}
big_integer::big_integer(long val){// construct with a long integer
if (val >= 0){
sign = true;
}else{
sign = false;
val *= (-1);
}
do{
digits.push_back( (char)(val%10) );
val /= 10;
}while ( val != 0 );
trim();
}
void big_integer::trim(){
vector<char>::reverse_iterator iter = digits.rbegin();
while(iter != digits.rend() && (*iter) == '\0'){
digits.pop_back();
iter++;
}
if( digits.size()==0 ){
sign = true;
digits.push_back('\0');
}
}
// construct with a string, which must be all integers-bits
// a sign can also be included. if the format is wrong, this will generate an Exception
big_integer::big_integer(string& def)throw(NumberFormatException){
for ( string::reverse_iterator iter = def.rbegin() ; iter < def.rend(); iter++){
char ch = (*iter);
if (iter == def.rend()-1){
if ( ch == '+' ){
sign = true;
continue;
}
else if(ch == '-' ){
sign = false;
continue;
}
}
if (ch <'0' || ch >'9'){
throw NumberFormatException(string("整数格式不对哦"));
}
digits.push_back( (char)((*iter) - '0' ) );
}
if( digits.empty() ){
throw NumberFormatException(string("整数格式不对哦"));
}
trim();
}
big_integer::big_integer(const big_integer& op2):digits(op2.digits){
sign = op2.sign;
}
//binary operators
big_integer operator+=(big_integer& op1,const big_integer& op2){
if( !!op1.sign == !!op2.sign ){ //只处理相同的符号的情况，异号的情况给-处理
vector<char>::iterator iter1;
vector<char>::const_iterator iter2;
iter1 = op1.digits.begin();
iter2 = op2.digits.begin();
char to_add = 0; //进位
while ( iter1 != op1.digits.end() && iter2 != op2.digits.end()){
(*iter1) = (*iter1) + (*iter2) + to_add;
to_add = (*iter1) / 10;
(*iter1) = (*iter1) % 10;
iter1++;iter2++;
}
while ( iter1 != op1.digits.end() ){
(*iter1) = (*iter1) + to_add;
to_add = (*iter1) / 10;
(*iter1) %= 10;
iter1++;
}
while ( iter2 != op2.digits.end() ){
char val = (*iter2) + to_add;
to_add = val / 10;
val %= 10;
op1.digits.push_back(val);
iter2++;
}
if( to_add != 0 ){
op1.digits.push_back(to_add);
}
return op1;
}else{
if (op1 > ZERO){
return op1 -= (-op2);
}else{
return op1 = (op2 - (-op1) );
}
}
}
big_integer operator-=(big_integer& op1,const big_integer& op2){
if (op2 < ZERO ) return op1 += (-op2);
if( op1 < op2 ) return op1 = -(op2-op1);
if( !!op1.sign == !!op2.sign ){ //只处理相同的符号的情况，异号的情况给+处理
vector<char>::iterator iter1;
vector<char>::const_iterator iter2;
iter1 = op1.digits.begin();
iter2 = op2.digits.begin();
char to_substract = 0; //借位
while ( iter1 != op1.digits.end() && iter2 != op2.digits.end()){
(*iter1) = (*iter1) - (*iter2) - to_substract;
to_substract = 0;
while( (*iter1) < 0 ){
to_substract++;
(*iter1) += 10;
}
iter1++;iter2++;
}
while ( iter1 != op1.digits.end() ){
(*iter1) = (*iter1) - to_substract;
to_substract = 0;
while( (*iter1) < 0 ){
to_substract++;
(*iter1) += 10;
}
iter1++;
}
op1.trim();
return op1;
}else{
if (op1 > ZERO){
return op1 += (-op2);
}else{
return op1 = -(op2 + (-op1));
}
}
}
big_integer operator*=(big_integer& op1,const big_integer& op2){
big_integer result(0);
if (op1 == ZERO || op2==ZERO){
result = ZERO;
}else{
vector<char>::const_iterator iter2 = op2.digits.begin();
while( iter2 != op2.digits.end() ){
if(*iter2 != 0){
deque<char> temp(op1.digits.begin() , op1.digits.end());
char to_add = 0;
deque<char>::iterator iter1 = temp.begin();
while( iter1 != temp.end() ){
(*iter1) *= (*iter2);
(*iter1) += to_add;
to_add = (*iter1) / 10;
(*iter1) %= 10;
iter1++;
}
if( to_add != 0)
temp.push_back( to_add );
int num_of_zeros = iter2 - op2.digits.begin();
while( num_of_zeros != 0 ){
temp.push_front('\0');
num_of_zeros--;
}
big_integer temp2(0);
temp2.digits.pop_back();
temp2.digits.insert( temp2.digits.end() , temp.begin() , temp.end() );
temp2.trim();
result = result + temp2;
}
iter2++;
}
result.sign = ( (op1.sign && op2.sign) || (!op1.sign && !op2.sign) );
}
op1 = result;
return op1;
}
big_integer operator/=(big_integer& op1 , const big_integer& op2 )throw(DividedByZeroException){
if( op2 == ZERO ){
throw DividedByZeroException("除数遇到0");
}
big_integer t1 = op1.abs(),t2 = op2.abs();
if ( t1 < t2 ){
op1 = ZERO;
return op1;
}
//现在 t1 > t2 > 0
//只需将 t1/t2的结果交给result就可以了
deque<char> temp;
vector<char>::reverse_iterator iter = t1.digits.rbegin();
big_integer temp2(0);
while( iter != t1.digits.rend() ){
temp2 = temp2 * big_integer( 10 ) + big_integer( (int)(*iter) );
char s = '\0';
while( temp2 >= t2 ){
temp2 = temp2 - t2;
s = s + 1;
}
temp.push_front( s );
iter++;
}
op1.digits.clear();
op1.digits.insert( op1.digits.end() , temp.begin() , temp.end() );
op1.trim();
op1.sign = ( (op1.sign && op2.sign) || (!op1.sign && !op2.sign) );
return op1;
}
big_integer operator%=(big_integer& op1,const big_integer& op2)throw(DividedByZeroException){
return op1 -= ((op1 / op2)*op2);
}
big_integer operator+(const big_integer& op1,const big_integer& op2){
big_integer temp(op1);
temp += op2;
return temp;
}
big_integer operator-(const big_integer& op1,const big_integer& op2){
big_integer temp(op1);
temp -= op2;
return temp;
}
big_integer operator*(const big_integer& op1,const big_integer& op2){
big_integer temp(op1);
temp *= op2;
return temp;
}
big_integer operator/(const big_integer& op1,const big_integer& op2)throw(DividedByZeroException){
big_integer temp(op1);
temp /= op2;
return temp;
}
big_integer operator%(const big_integer& op1,const big_integer& op2)throw(DividedByZeroException){
big_integer temp(op1);
temp %= op2;
return temp;
}
//uniary operators
big_integer operator-(const big_integer& op){ //negative
big_integer temp = big_integer(op);
temp.sign = !temp.sign;
return temp;
}
big_integer operator++(big_integer& op){ //++v
op += ONE;
return op;
}
big_integer operator++(big_integer& op,int x){ //v++
big_integer temp(op);
++op;
return temp;
}
big_integer operator--(big_integer& op){ //--v
op -= - ONE;
return op;
}
big_integer operator--(big_integer& op,int x){ //v--
big_integer temp(op);
--op;
return temp;
}
bool operator<(const big_integer& op1,const big_integer& op2){
if( !!op1.sign != !!op2.sign )
return !op1.sign && op2.sign;
else{
if(op1.digits.size() != op2.digits.size())
return (op1.sign && op1.digits.size()<op2.digits.size()) || (!op1.sign && op1.digits.size()>op2.digits.size());
//两个的长度也一样了
vector<char>::const_reverse_iterator iter1,iter2;
iter1 = op1.digits.rbegin();iter2 = op2.digits.rbegin();
while( iter1 != op1.digits.rend() ){
if( op1.sign && *iter1 < *iter2 ) return true;
if( !op1.sign && *iter1 > *iter2 ) return true;
iter1++;iter2++;
}
return false;
}
}
bool operator==(const big_integer& op1,const big_integer& op2){
if( !!op1.sign != !!op2.sign || op1.digits.size() != op2.digits.size() ){
return false;
}
vector<char>::const_iterator iter1,iter2;
iter1 = op1.digits.begin();iter2 = op2.digits.begin();
while( iter1!= op1.digits.end() ){
if( *iter1 != *iter2 ) return false;
iter1++;iter2++;
}
return true;
}
bool operator!=(const big_integer& op1,const big_integer& op2){
return !(op1==op2);
}
bool operator>=(const big_integer& op1,const big_integer& op2){
return (op1>op2) || (op1==op2);
}
bool operator<=(const big_integer& op1,const big_integer& op2){
return (op1<op2) || (op1==op2);
}
bool operator>(const big_integer& op1,const big_integer& op2){
return !(op1<=op2);
}
ostream& operator<<(ostream& stream,const big_integer& val){ //print the big_integer
if (!val.sign){
stream << "-";
}
for ( vector<char>::const_reverse_iterator iter = val.digits.rbegin(); iter != val.digits.rend() ; iter++){
stream << (char)((*iter) + '0');
}
return stream;
}
// test_big_integer.cpp
// 测试程序
#include "big_integer.cpp"
#include <fstream>
#include <iostream>
#include <time>
int main()
{
big_integer b(1);
ofstream out;
big_integer result = ONE;
for( int i = 1 ; i <= 6 ; i++){
result *= big_integer(i);
}
cout << "6 != \n" << result<<endl;
return 0;
}
