## 大整数类 原

曾劲松

http://xllib.codeplex.com/SourceControl/changeset/view/1689#1160

``````#include<iostream>
#include<vector>
#include<string>
#include<cstring>
using namespace std;

class BigInt
{
public:
BigInt();
BigInt(long int s);
BigInt(string str);
BigInt(BigInt& a);
BigInt operator=(BigInt a);

friend BigInt operator+(BigInt a,BigInt b);
friend BigInt operator-(BigInt a,BigInt b);
friend BigInt operator*(BigInt a,BigInt b);
friend BigInt operator/(BigInt a,BigInt b);//除法算法不太好

friend ostream& operator<<(ostream& out,BigInt& a);
friend istream& operator>>(istream& in,BigInt& a);

friend int SizeJudge(BigInt a,BigInt b);
private:
vector<int> vec;
int negative;//0为正，1为负
};

BigInt::BigInt()
{
vec.push_back(0);
negative = 0;
}

BigInt::BigInt(long int s)
{
if(s<0)
{
negative = 1;
s = -s;
}
else
negative = 0;
int i;
while(s>9)
{
i = s%10;
vec.push_back(i);
s /=10;
}
vec.push_back(s);
}

BigInt::BigInt(string str)
{
if(str[0] == '-')
{
negative = 1;
str = str.substr(1,str.size()-1);
}
else
negative = 0;
for(int i=str.size()-1;i>=0;i--)
{
vec.push_back(str[i]-'0');
}
}

BigInt::BigInt(BigInt& a)
{
vec = a.vec;
negative = a.negative;
}

BigInt BigInt::operator=(BigInt a)
{
vec = a.vec;
negative = a.negative;
return *this;
}

ostream& operator<<(ostream& out,BigInt& a)
{
string str="";
int judge = 0;
if((a.vec[a.vec.size()-1]+'0') == '-')
judge = 1;
if((a.negative == 1)&&judge == 0)
{
str += '-';
}
for(int i=a.vec.size()-1;i>=0;i--)
{
str += (a.vec[i]+'0');
}
out<<str;
return out;
}

istream& operator>>(istream& in,BigInt& a)
{
string str="";
in>>str;
a.vec.clear();
for(int i=str.size()-1;i>=0;i--)
{
a.vec.push_back(str[i]-'0');
}
return in;
}

BigInt operator+(BigInt a,BigInt b)
{
int negative_judge = 0;
if(a.negative == 1&&b.negative == 1)//全负
{
negative_judge = 1;
}
if(a.negative == 0&&b.negative == 0)//全正
{
negative_judge = 0;
}
if(a.negative == 0&&b.negative == 1)//a正b负
{
b.negative = 0;
return (a-b);
}
if(a.negative == 1&&b.negative == 0)//a负b正
{
a.negative = 0;
return (b-a);
}
BigInt c,tmp;
int alen,blen,min,max,i;
alen = a.vec.size();
blen = b.vec.size();
if(alen>blen)
{
c.vec = a.vec;
tmp.vec = b.vec;
min = blen;
max = alen;
}
else
{
c.vec = b.vec;
tmp.vec = a.vec;
min = alen;
max = blen;
}
for(i=0;i<min-1;i++)//min=max？
{
c.vec[i] += tmp.vec[i];
if(c.vec[i]>9)
{
c.vec[i] -= 10;
c.vec[i+1] += 1;
}
}
c.vec[i] +=tmp.vec[i];
if(c.vec[i]>9)
{
c.vec[i] -=10;
if(min == max)
c.vec.push_back(1);
else
c.vec[i+1] +=1;
}
for(i=min;i<max-1;i++)
{
if(c.vec[i]>9)
{
c.vec[i] -=10;
c.vec[i+1] +=1;
}
}
if(c.vec[max-1]>9)
{
c.vec[max-1] -=10;
c.vec.push_back(1);
}
i=c.vec.size()-1;//去掉前面的0
while(c.vec[i] == 0)
{
c.vec.pop_back();
i--;
}
if(negative_judge == 1)
{
string str = "-";
c.vec.push_back(str[0]-'0');
}
return c;
}

BigInt operator-(BigInt a,BigInt b)
{
int negative_judge = 0;
if(a.negative == 1&&b.negative == 1)//全负
{
a.negative = 0;
b.negative = 0;
return (b-a);
}
if(a.negative == 0&&b.negative == 0)//全正
{
negative_judge = 0;
}
if(a.negative == 0&&b.negative == 1)//a正b负
{
b.negative = 0;
return (a+b);
}
if(a.negative == 1&&b.negative == 0)//a负b正
{
b.negative =1;
return (a+b);
}
BigInt c,tmp;
int alen,blen,min,max,i,judge=0;
alen = a.vec.size();
blen = b.vec.size();
//大值赋给c，小值赋给tmp
if(alen>blen)
{
c.vec = a.vec;
tmp.vec = b.vec;
min = blen;
max = alen;
judge = 1;
}
else if(alen == blen)
{
for(i=alen-1;i>=0;i--)
{
if(a.vec[i]>b.vec[i])
{
c.vec = a.vec;
tmp.vec = b.vec;
min = blen;
max = alen;
judge = 1;
break;
}
else if(a.vec[i]<b.vec[i])
{
c.vec = b.vec;
tmp.vec = a.vec;
min = alen;
max = blen;
judge = 2;
break;
}
}
if(i==-1)
return (BigInt)0;
}
else
{
c.vec = b.vec;
tmp.vec = a.vec;
min = alen;
max = blen;
judge = 2;
}
for(i=0;i<min;i++)//min=max？c>tmp
{
c.vec[i] -= tmp.vec[i];
if(c.vec[i]<0)
{
c.vec[i] += 10;
c.vec[i+1] -= 1;
}
}
if(min<max)
for(i=min;i<max;i++)
{
if(c.vec[i]<0)
{
c.vec[i] +=10;
c.vec[i+1] -=1;
}
}
if(judge == 2)
{
string str="-";
c.vec.push_back(str[0]-'0');
}
i=c.vec.size()-1;//去掉前面的0
while(c.vec[i] == 0)
{
c.vec.pop_back();
i--;
}
return c;
}

BigInt operator*(BigInt a,BigInt b)
{
BigInt c;
int alen,blen,i,j,max,tmp;
alen = a.vec.size();
blen = b.vec.size();
max = alen+blen;
c.vec.clear();
for(i=0;i<max;i++)
{
c.vec.push_back(0);
}
for(i=0;i<alen;i++)
{
for(j=0;j<blen;j++)
{
tmp = c.vec[i+j]+a.vec[i]*b.vec[j];
if(tmp>9)
{
if(i+j+1<max)
{
c.vec[i+j+1] += tmp/10;
tmp %= 10;
}
else
{
c.vec.push_back(tmp/10);
tmp %= 10;
}
}
c.vec[i+j] = tmp;
}
}
i=c.vec.size()-1;//去掉前面的0
while(c.vec[i] == 0)
{
c.vec.pop_back();
i--;
}
if((a.negative == 0&&b.negative == 1)||(a.negative ==
1&&b.negative == 0))//a正b负//a负b正
{
string str="-";
c.vec.push_back(str[0]-'0');
c.negative = 1;
}
else
{
c.negative = 0;
}
return c;
}

BigInt operator/(BigInt a,BigInt b)
{
if(SizeJudge(a,b) == -1)
{
return (BigInt)0;
}
else if(SizeJudge(a,b) == 0)
{
return (BigInt)1;
}
BigInt tmp;
int alen,blen,i;
alen = a.vec.size();
blen = b.vec.size();
if(blen == 1&&b.vec[0] == 0)
{
BigInt err("error");
return err;
}
i = alen-blen;
int j = 1;
while(i>0)
{
j *=10;
i--;
}
BigInt count(j);
tmp = count*b;
if(SizeJudge(a,tmp) == 1)
{
while(SizeJudge(a,tmp) == 1)
{
count = count+1;
tmp = b*count;
}
}
else if(SizeJudge(a,tmp) == -1)
{
while(SizeJudge(a,tmp) == -1)
{
count = count-1;
tmp = b*count;
}
}
if((a.negative == 0&&b.negative == 1)||(a.negative ==
1&&b.negative == 0))//a正b负//a负b正
{
string str="-";
count.vec.push_back(str[0]-'0');
count.negative = 1;
}
else
{
count.negative = 0;
}
return count;
}

int SizeJudge(BigInt a,BigInt b)
{//1代表大于，0代表等于，-1代表小于
int alen,blen,i;
alen = a.vec.size();
blen = b.vec.size();
if(alen>blen)
{
return 1;
}
else if(alen == blen)
{
for(i=alen-1;i>=0;i--)
{
if(a.vec[i]>b.vec[i])
{
return 1;
}
else if(a.vec[i]<b.vec[i])
{
return -1;
}
}
if(i==0)
return 0;
}
else
{
return -1;
}
}

int main()
{
////测试数据输入
//BigInt a("999999999999999999999"),b("8888"),c;
//cin>>b;
//cout<<"the input:"<<b<<endl;
//c = a+b;
//cout<<a<<"+"<<b<<"="<<c<<endl;
//cin.get();
////测试加法
//BigInt a("999999999999999999999"),b("8888"),c;
//c = a+b;
//cout<<a<<"+"<<b<<"="<<c<<endl;
//BigInt d("-1111");
//c = a+d;
//cout<<a<<"+"<<d<<"="<<c<<endl;
//c = 7777777+a;
//cout<<"7777777"<<"+"<<a<<"="<<c<<endl;
//BigInt s(a);//调用拷贝构造函数
//c = s+a;
//cout<<s<<"+"<<a<<"="<<c<<endl;
////测试减法
//BigInt a("999999999999999999999"),b("8888"),c;
//c = a-b;
//cout<<a<<"-"<<b<<"="<<c<<endl;
//BigInt d("-1111");
//c = a-d;
//cout<<a<<"-"<<d<<"="<<c<<endl;
//c = 7777777-a;
//cout<<"7777777"<<"-"<<a<<"="<<c<<endl;
////测试乘法
//BigInt a("999999999999999999999"),b("8888"),c;
//c = a*b;
//cout<<a<<"*"<<b<<"="<<c<<endl;
//BigInt d("-1111");
//c = a*d;
//cout<<a<<"*"<<d<<"="<<c<<endl;
//c = 7777777*a;
//cout<<"7777777"<<"*"<<a<<"="<<c<<endl;
///测试除法
//BigInt a("999999999999999999999"),b("888888888888888"),c;
//c = a/b;
//cout<<a<<"/"<<b<<"="<<c<<endl;
//c = b/a;
//cout<<b<<"/"<<a<<"="<<c<<endl;
//BigInt d("-111111111111111");
//c = a/d;
//cout<<a<<"/"<<d<<"="<<c<<endl;
//c = 0/a;
//cout<<"0"<<"/"<<a<<"="<<c<<endl;
//计算并显示30！
BigInt a("30"),c("1");
int i = 30;
while(i>0)
{
c = c*a;
a = a-1;
i--;
}
cout<<"30! = "<<c<<endl;
return 0;
}  ``````
``````	//简化的
template <typename T>
class big_int
{
public:
big_int();
big_int(int int_value);
big_int(unsigned char *buffer, size_t size);
big_int(const big_int &that);
big_int &operator = (const big_int &that);
~big_int();
protected:
Array<T> m_aValue;
bool m_bPositive;

public:
big_int operator +(const big_int &that) const;
big_int operator -(const big_int &that) const;
};

template <typename T>
big_int<T>::big_int(): m_bPositive(true)
{

}

template <typename T>
big_int<T>::big_int(unsigned char *buffer, size_t size)
: m_bPositive(true)
{
for (size_t i = 0; i < size / sizeof(T); ++i, buffer += sizeof(T))
{
m_aValue.PushBack(*(T *)buffer);
}

size_t rest = size % sizeof(T);

if (rest > 0)
{
T val = 0;
unsigned char *p = (unsigned char *)&val;

for (size_t i = 0; i < rest; ++i)
{
p[i] = buffer[i];
}

m_aValue.PushBack(val);
}
}

template <typename T>
big_int<T>::big_int(int int_value)
: m_bPositive(true)
{
unsigned long long val = (unsigned long long)int_value;

if (int_value < 0)
{
val = (unsigned long long)-int_value;
m_bPositive = false;
}

while (val > 0)
{
m_aValue.PushBack((T)val);
val >>= sizeof(T) * 8;
}
}

template <typename T>
big_int<T>::big_int(const big_int &that)
: m_bPositive(true)
{
this->m_bPositive = that.m_bPositive;
this->m_aValue = that.m_aValue;
}

template <typename T>
big_int<T> &big_int<T>::operator = (const big_int<T> &that)
{
if (this != &that)
{
this->m_aValue = that.m_aValue;
this->m_bPositive = that.m_bPositive;
}

return *this;
}

template <typename T>
big_int<T>::~big_int()
{

}

template <typename T>
big_int<T> big_int<T>::operator +(const big_int<T> &addend)
{
if (this->m_bPositive != addend.m_bPositive)
{
big_int<T> subtrahend = addend;
subtrahend.Neg();
Sub(subtrahend);
return *this;
}

const Array<T> &rhs = addend.m_aValue;
Array<T> &res = this->m_aValue;

for (size_t i = 0; i < rhs.Size(); ++ i)
{
T overflow = 0;

while (res.Size() <= i)
{
res.PushBack((T)0);
}

res[i] += rhs[i];

if (res[i] < rhs[i])
{
++overflow;
}

for (size_t j = i + 1; overflow > 0; ++j)
{
if (res.Size() <= j)
{
res.PushBack((T)0);
}

res[j] += overflow;

if (res[j] < overflow)
{
overflow = 1;
}
else
{
overflow = 0;
}
}
}

big_int<T> ret(*this);
return ret;
}

template <typename T>
big_int<T> big_int<T>::operator -(const big_int<T> &subtrahend)
{
if (this->m_bPositive != subtrahend.m_bPositive)
{
big_int<T> addend = subtrahend;
addend.Neg();
Add(subtrahend);
big_int<T> ret(*this);
return  ret.Sub(that);
}

if (*this == subtrahend)
{
m_bPositive = true;
m_aValue.Clear();
big_int<T> ret(*this);
return  ret.Sub(that);
}

if (*this < subtrahend)
{
big_int<T> minuend = subtrahend;
minuend.Sub(*this);
minuend.Neg();
*this = minuend;
big_int<T> ret(*this);
return  ret.Sub(that);
}

const Array<T> &rhs = subtrahend.m_aValue;
Array<T> &res = this->m_aValue;

for (size_t i = 0; i < rhs.Size(); ++ i)
{
T overflow = 0;
T original = res[i];

res[i] -= rhs[i];

if (res[i] > original)
{
++overflow;
}

for (size_t j = i + 1; overflow > 0; ++j)
{
original = res[j];
res[j] -= overflow;

if (res[j] > original)
{
overflow = 1;
}
else
{
overflow = 0;
}
}
}

while (!res.Empty() && *res.ReverseBegin() == 0)
{
res.Delete(res.ReverseBegin());
}

big_int<T> ret(*this);
return  ret.Sub(that);
}
``````
``````#ifndef __XLBigIntT_H_4ED560E8_F226_4D72_9016_828D1AA8696E_INCLUDED__
#define __XLBigIntT_H_4ED560E8_F226_4D72_9016_828D1AA8696E_INCLUDED__

#include <xl/Containers/xlArray.h>
#include <xl/Containers/xlMap.h>
#include <xl/Objects/xlString.h>

namespace xl
{
template <typename T>
class BigIntT
{
public:
BigIntT();
BigIntT(char char_value);
BigIntT(unsigned char uchar_value);
BigIntT(short short_value);
BigIntT(unsigned short ushort_value);
BigIntT(int int_value);
BigIntT(unsigned int uint_value);
BigIntT(long long_value);
BigIntT(unsigned long ulong_value);
BigIntT(long long int64_value);
BigIntT(unsigned long long uint64_value);
BigIntT(unsigned char *buffer, size_t size);
BigIntT(const wchar_t *string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF");
BigIntT(const String &string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF");
BigIntT(const BigIntT &that);
BigIntT &operator = (const BigIntT &that);
~BigIntT();

protected:
Array<T> m_aValue;
bool m_bPositive;

public:
bool IsPositive() const;
Array<T> GetData() const;

public:
bool operator ==(const BigIntT &that) const;
bool operator !=(const BigIntT &that) const;
bool operator <(const BigIntT &that) const;
bool operator >(const BigIntT &that) const;
bool operator <=(const BigIntT &that) const;
bool operator >=(const BigIntT &that) const;

public:
BigIntT &Neg();
BigIntT &Inc();
BigIntT &Dec();
BigIntT &Add(const BigIntT &addend);
BigIntT &Sub(const BigIntT &subtrahend);
BigIntT Mul(const BigIntT &multiplicator) const;
BigIntT Div(const BigIntT &divisor, BigIntT &remainder) const;
BigIntT Exp(const BigIntT &exponent) const;
BigIntT ExpMod(const BigIntT &exponent, const BigIntT &divisor) const;

public:
BigIntT operator -() const;
BigIntT &operator ++();
BigIntT operator ++(int);
BigIntT &operator --();
BigIntT operator --(int);
BigIntT operator +(const BigIntT &that) const;
BigIntT operator -(const BigIntT &that) const;
BigIntT operator *(const BigIntT &that) const;
BigIntT operator /(const BigIntT &that) const;
BigIntT operator %(const BigIntT &that) const;
BigIntT &operator +=(const BigIntT &that);
BigIntT &operator -=(const BigIntT &that);
BigIntT &operator *=(const BigIntT &that);
BigIntT &operator /=(const BigIntT &that);
BigIntT &operator %=(const BigIntT &that);

public:
char ToChar() const;
short ToShort() const;
int ToInt() const;
long ToLong() const;
long long ToLongLong() const;

public:
BigIntT &FromString(const wchar_t *string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF");
BigIntT &FromString(const String &string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF");
String ToString(unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF") const;
};

typedef BigIntT<unsigned int> BigInt;

template <typename T>
BigIntT<T>::BigIntT()
: m_bPositive(true)
{

}

template <typename T>
BigIntT<T>::BigIntT(char char_value)
: m_bPositive(true)
{
unsigned long long val = (unsigned long long)char_value;

if (char_value < 0)
{
val = (unsigned long long)-char_value;
m_bPositive = false;
}

while (val > 0)
{
m_aValue.PushBack((T)val);
val >>= sizeof(T) * 8;
}
}

template <typename T>
BigIntT<T>::BigIntT(unsigned char uchar_value)
: m_bPositive(true)
{
unsigned long long val = (unsigned long long)uchar_value;

while (val > 0)
{
m_aValue.PushBack((T)val);
val >>= sizeof(T) * 8;
}
}

template <typename T>
BigIntT<T>::BigIntT(short short_value)
: m_bPositive(true)
{
unsigned long long val = (unsigned long long)short_value;

if (short_value < 0)
{
val = (unsigned long long)-short_value;
m_bPositive = false;
}

while (val > 0)
{
m_aValue.PushBack((T)val);
val >>= sizeof(T) * 8;
}
}

template <typename T>
BigIntT<T>::BigIntT(unsigned short ushort_value)
: m_bPositive(true)
{
unsigned long long val = (unsigned long long)ushort_value;

while (val > 0)
{
m_aValue.PushBack((T)val);
val >>= sizeof(T) * 8;
}
}

template <typename T>
BigIntT<T>::BigIntT(int int_value)
: m_bPositive(true)
{
unsigned long long val = (unsigned long long)int_value;

if (int_value < 0)
{
val = (unsigned long long)-int_value;
m_bPositive = false;
}

while (val > 0)
{
m_aValue.PushBack((T)val);
val >>= sizeof(T) * 8;
}
}

template <typename T>
BigIntT<T>::BigIntT(unsigned int uint_value)
: m_bPositive(true)
{
unsigned long long val = (unsigned long long)uint_value;

while (val > 0)
{
m_aValue.PushBack((T)val);
val >>= sizeof(T) * 8;
}
}

template <typename T>
BigIntT<T>::BigIntT(long long_value)
: m_bPositive(true)
{
unsigned long long val = (unsigned long long)long_value;

if (long_value < 0)
{
val = (unsigned long long)-long_value;
m_bPositive = false;
}

while (val > 0)
{
m_aValue.PushBack((T)val);
val >>= sizeof(T) * 8;
}
}

template <typename T>
BigIntT<T>::BigIntT(unsigned long ulong_value)
: m_bPositive(true)
{
unsigned long long val = (unsigned long long)ulong_value;

while (val > 0)
{
m_aValue.PushBack((T)val);
val >>= sizeof(T) * 8;
}
}

template <typename T>
BigIntT<T>::BigIntT(long long int64_value)
: m_bPositive(true)
{
unsigned long long val = (unsigned long long)int64_value;

if (int64_value < 0)
{
val = (unsigned long long)-int64_value;
m_bPositive = false;
}

while (val > 0)
{
m_aValue.PushBack((T)val);
val >>= sizeof(T) * 8;
}
}

template <typename T>
BigIntT<T>::BigIntT(unsigned long long uint64_value)
: m_bPositive(true)
{
unsigned long long val = (unsigned long long)uint64_value;

while (val > 0)
{
m_aValue.PushBack((T)val);
val >>= sizeof(T) * 8;
}
}

template <typename T>
BigIntT<T>::BigIntT(unsigned char *buffer, size_t size)
: m_bPositive(true)
{
for (size_t i = 0; i < size / sizeof(T); ++i, buffer += sizeof(T))
{
m_aValue.PushBack(*(T *)buffer);
}

size_t rest = size % sizeof(T);

if (rest > 0)
{
T val = 0;
unsigned char *p = (unsigned char *)&val;

for (size_t i = 0; i < rest; ++i)
{
p[i] = buffer[i];
}

m_aValue.PushBack(val);
}
}

template <typename T>
BigIntT<T>::BigIntT(const wchar_t *string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF")
{
FromString(string_value, base, alphabet);
}

template <typename T>
BigIntT<T>::BigIntT(const String &string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF")
{
FromString(string_value, base, alphabet);
}

template <typename T>
BigIntT<T>::BigIntT(const BigIntT &that)
: m_bPositive(true)
{
this->m_bPositive = that.m_bPositive;
this->m_aValue = that.m_aValue;
}

template <typename T>
BigIntT<T> &BigIntT<T>::operator = (const BigIntT<T> &that)
{
if (this != &that)
{
this->m_aValue = that.m_aValue;
this->m_bPositive = that.m_bPositive;
}

return *this;
}

template <typename T>
BigIntT<T>::~BigIntT()
{

}

template <typename T>
bool BigIntT<T>::IsPositive() const
{
return m_bPositive;
}

template <typename T>
Array<T> BigIntT<T>::GetData() const
{
return m_aValue;
}

template <typename T>
bool BigIntT<T>::operator ==(const BigIntT<T> &that) const
{
return (this->m_bPositive == that.m_bPositive) && (this->m_aValue == that.m_aValue);
}

template <typename T>
bool BigIntT<T>::operator !=(const BigIntT<T> &that) const
{
return !(*this == that);
}

template <typename T>
bool BigIntT<T>::operator <(const BigIntT<T> &that) const
{
if (this->m_bPositive != that.m_bPositive)
{
return !this->m_bPositive;
}

if (this->m_aValue.Size() != that.m_aValue.Size())
{
return this->m_aValue.Size() < that.m_aValue.Size();
}

if (!this->m_aValue.Empty())
{
for (size_t i = this->m_aValue.Size() - 1; true; --i)
{
if (this->m_aValue[i] != that.m_aValue[i])
{
return this->m_aValue[i] < that.m_aValue[i];
}

if (i == 0)
{
break;
}
}
}

return false;
}

template <typename T>
bool BigIntT<T>::operator >(const BigIntT<T> &that) const
{
if (this->m_bPositive != that.m_bPositive)
{
return this->m_bPositive;
}

if (this->m_aValue.Size() != that.m_aValue.Size())
{
return this->m_aValue.Size() > that.m_aValue.Size();
}

if (!this->m_aValue.Empty())
{
for (size_t i = this->m_aValue.Size() - 1; true; --i)
{
if (this->m_aValue[i] != that.m_aValue[i])
{
return this->m_aValue[i] > that.m_aValue[i];
}

if (i == 0)
{
break;
}
}
}

return false;
}

template <typename T>
bool BigIntT<T>::operator <=(const BigIntT<T> &that) const
{
if (this->m_bPositive != that.m_bPositive)
{
return !this->m_bPositive;
}

if (this->m_aValue.Size() != that.m_aValue.Size())
{
return this->m_aValue.Size() < that.m_aValue.Size();
}

if (!this->m_aValue.Empty())
{
for (size_t i = this->m_aValue.Size() - 1; true; --i)
{
if (this->m_aValue[i] != that.m_aValue[i])
{
return this->m_aValue[i] < that.m_aValue[i];
}

if (i == 0)
{
break;
}
}
}

return true;
}

template <typename T>
bool BigIntT<T>::operator >=(const BigIntT<T> &that) const
{
if (this->m_bPositive != that.m_bPositive)
{
return this->m_bPositive;
}

if (this->m_aValue.Size() != that.m_aValue.Size())
{
return this->m_aValue.Size() > that.m_aValue.Size();
}

if (!this->m_aValue.Empty())
{
for (size_t i = this->m_aValue.Size() - 1; true; --i)
{
if (this->m_aValue[i] != that.m_aValue[i])
{
return this->m_aValue[i] > that.m_aValue[i];
}

if (i == 0)
{
break;
}
}
}

return true;
}

template <typename T>
BigIntT<T> &BigIntT<T>::Neg()
{
m_bPositive = !m_bPositive;
return *this;
}

template <typename T>
BigIntT<T> &BigIntT<T>::Inc()
{
Add(1u);
return *this;
}

template <typename T>
BigIntT<T> &BigIntT<T>::Dec()
{
Sub(1u);
return *this;
}

template <typename T>
BigIntT<T> &BigIntT<T>::Add(const BigIntT<T> &addend)
{
if (this->m_bPositive != addend.m_bPositive)
{
BigIntT<T> subtrahend = addend;
subtrahend.Neg();
Sub(subtrahend);
return *this;
}

const Array<T> &rhs = addend.m_aValue;
Array<T> &res = this->m_aValue;

for (size_t i = 0; i < rhs.Size(); ++ i)
{
T overflow = 0;

while (res.Size() <= i)
{
res.PushBack((T)0);
}

res[i] += rhs[i];

if (res[i] < rhs[i])
{
++overflow;
}

for (size_t j = i + 1; overflow > 0; ++j)
{
if (res.Size() <= j)
{
res.PushBack((T)0);
}

res[j] += overflow;

if (res[j] < overflow)
{
overflow = 1;
}
else
{
overflow = 0;
}
}
}

return *this;
}

template <typename T>
BigIntT<T> &BigIntT<T>::Sub(const BigIntT<T> &subtrahend)
{
if (this->m_bPositive != subtrahend.m_bPositive)
{
BigIntT<T> addend = subtrahend;
addend.Neg();
Add(subtrahend);
return *this;
}

if (*this == subtrahend)
{
m_bPositive = true;
m_aValue.Clear();
return *this;
}

if (*this < subtrahend)
{
BigIntT<T> minuend = subtrahend;
minuend.Sub(*this);
minuend.Neg();
*this = minuend;
return *this;
}

const Array<T> &rhs = subtrahend.m_aValue;
Array<T> &res = this->m_aValue;

for (size_t i = 0; i < rhs.Size(); ++ i)
{
T overflow = 0;
T original = res[i];

res[i] -= rhs[i];

if (res[i] > original)
{
++overflow;
}

for (size_t j = i + 1; overflow > 0; ++j)
{
original = res[j];
res[j] -= overflow;

if (res[j] > original)
{
overflow = 1;
}
else
{
overflow = 0;
}
}
}

while (!res.Empty() && *res.ReverseBegin() == 0)
{
res.Delete(res.ReverseBegin());
}

return *this;
}

template <typename T>
BigIntT<T> BigIntT<T>::Mul(const BigIntT<T> &multiplicator) const
{
BigIntT<T> product;

const Array<T> &lhs = this->m_aValue, &rhs = multiplicator.m_aValue;
Array<T> &res = product.m_aValue;

if (lhs.Empty() || rhs.Empty())
{
return product;
}

for (size_t i = 0; i < lhs.Size(); ++i)
{
for (size_t j = 0; j < rhs.Size(); ++j)
{
unsigned long long temp = lhs[i];
temp *= rhs[j];

for (size_t k = 0; temp > 0; ++k)
{
while (res.Size() <= i + j + k)
{
res.PushBack((T)0);
}

res[i + j + k] += (T)temp;

if (res[i + j + k] < (T)temp)
{
temp >>= sizeof(T) * 8;
++temp;
}
else
{
temp >>= sizeof(T) * 8;
}
}
}
}

if ((this->m_bPositive != multiplicator.m_bPositive) && !res.Empty())
{
product.m_bPositive = !product.m_bPositive;
}

return product;
}

template <typename T>
BigIntT<T> BigIntT<T>::Div(const BigIntT<T> &divisor, BigIntT<T> &remainder) const
{
if (divisor.m_aValue.Empty())
{
return 0;
}

BigIntT<T> dividend(*this), div(divisor);

dividend.m_bPositive = true;
div.m_bPositive = true;

BigIntT<T> quotient;

while (dividend >= div)
{
size_t zeros = dividend.m_aValue.Size() - div.m_aValue.Size();

BigIntT<T> temp;
temp.m_aValue.Insert(temp.m_aValue.Begin(), dividend.m_aValue.Begin() + zeros, dividend.m_aValue.End());

unsigned long long a = temp.m_aValue[temp.m_aValue.Size() - 1];
unsigned long long b = div.m_aValue[div.m_aValue.Size() - 1];

if (temp < div)
{
--zeros;
temp.m_aValue.Insert(temp.m_aValue.Begin(), dividend.m_aValue.Begin() + zeros, dividend.m_aValue.Begin() + zeros + 1);
a <<= sizeof(T) * 8;
a += temp.m_aValue[temp.m_aValue.Size() - 2];
}

unsigned long long test = a / b;

if (div.m_aValue.Size() >= 2)
{
while (b * test + ((div.m_aValue[div.m_aValue.Size() - 2] * test) >> sizeof(T) * 8) > a)
{
--test;
}
}

BigIntT<T> product = div.Mul(test);

while (product > temp)
{
--test;
product = div.Mul(test);
}

BigIntT<T> res(test);

for (size_t i = 0; i < zeros; ++i)
{
res.m_aValue.PushFront((T)0);
product.m_aValue.PushFront((T)0);
}

quotient.Add(res);
dividend.Sub(product);
}

remainder = dividend;

remainder.m_bPositive = this->m_bPositive;
quotient.m_bPositive = (this->m_bPositive == divisor.m_bPositive);

return quotient;
}

template <typename T>
BigIntT<T> BigIntT<T>::Exp(const BigIntT<T> &exponent) const
{
if (!exponent.m_bPositive)
{
return 0u;
}

if (exponent.m_aValue.Empty())
{
return 1u;
}

BigIntT<T> power(1u);

for (size_t i = exponent.m_aValue.Size() - 1; true; --i)
{
T n = exponent.m_aValue[i];

for (T mask = (1u << (sizeof(T) * 8 - 1)); mask > 0; mask >>= 1)
{
power = power.Mul(power);

if ((n & mask) != 0)
{
power = power.Mul(*this);
}
}

if (i == 0)
{
break;
}
}

return power;
}

template <typename T>
BigIntT<T> BigIntT<T>::ExpMod(const BigIntT<T> &exponent, const BigIntT<T> &divisor) const
{
if (!exponent.m_bPositive)
{
return 0u;
}

if (exponent.m_aValue.Empty())
{
return 1u;
}

BigIntT<T> power(1u);

for (size_t i = exponent.m_aValue.Size() - 1; true; --i)
{
T n = exponent.m_aValue[i];

for (T mask = (1u << (sizeof(T) * 8 - 1)); mask > 0; mask >>= 1)
{
power = power.Mul(power);
power.Div(divisor, power);

if ((n & mask) != 0)
{
power = power.Mul(*this);
power.Div(divisor, power);
}
}

if (i == 0)
{
break;
}
}

return power;
}

template <typename T>
BigIntT<T> BigIntT<T>::operator -() const
{
BigIntT<T> ret(*this);
return ret.Neg();
}

template <typename T>
BigIntT<T> &BigIntT<T>::operator ++()
{
return Inc();
}

template <typename T>
BigIntT<T> BigIntT<T>::operator ++(int)
{
BigIntT<T> ret(*this);
Inc();
return ret;
}

template <typename T>
BigIntT<T> &BigIntT<T>::operator --()
{
return Dec();
}

template <typename T>
BigIntT<T> BigIntT<T>::operator --(int)
{
BigIntT<T> ret(*this);
Dec();
return ret;
}

template <typename T>
BigIntT<T> BigIntT<T>::operator +(const BigIntT<T> &that) const
{
BigIntT<T> ret(*this);
return ret.Add(that);
}

template <typename T>
BigIntT<T> BigIntT<T>::operator -(const BigIntT<T> &that) const
{
BigIntT<T> ret(*this);
return  ret.Sub(that);
}

template <typename T>
BigIntT<T> BigIntT<T>::operator *(const BigIntT<T> &that) const
{
return Mul(that);
}

template <typename T>
BigIntT<T> BigIntT<T>::operator /(const BigIntT<T> &that) const
{
BigIntT<T> reminder;
return Div(that, reminder);
}

template <typename T>
BigIntT<T> BigIntT<T>::operator %(const BigIntT<T> &that) const
{
BigIntT<T> reminder;
Div(that, reminder);
return reminder;
}

template <typename T>
BigIntT<T> &BigIntT<T>::operator +=(const BigIntT<T> &that)
{
return Add(that);
}

template <typename T>
BigIntT<T> &BigIntT<T>::operator -=(const BigIntT<T> &that)
{
return Sub(that);
}

template <typename T>
BigIntT<T> &BigIntT<T>::operator *=(const BigIntT<T> &that)
{
return *this = Mul(that);
}

template <typename T>
BigIntT<T> &BigIntT<T>::operator /=(const BigIntT<T> &that)
{
BigIntT<T> reminder;
return *this = Div(that, reminder);
}

template <typename T>
BigIntT<T> &BigIntT<T>::operator %=(const BigIntT<T> &that)
{
BigIntT<T> reminder;
Div(that, reminder);
return *this = reminder;
}

template <typename T>
char BigIntT<T>::ToChar() const
{
long long ret = 0, temp = 0;
size_t i = 0;

while (i * sizeof(T) < sizeof(char) && m_aValue.Size() > i)
{
temp = m_aValue[i];
temp <<= i * sizeof(T) * 8;
ret |= temp;
++i;
}

if (!m_bPositive)
{
ret = - ret;
}

return (char)ret;
}

template <typename T>
short BigIntT<T>::ToShort() const
{
long long ret = 0, temp = 0;
size_t i = 0;

while (i * sizeof(T) < sizeof(short) && m_aValue.Size() > i)
{
temp = m_aValue[i];
temp <<= i * sizeof(T) * 8;
ret |= temp;
++i;
}

if (!m_bPositive)
{
ret = - ret;
}

return (short)ret;
}

template <typename T>
int BigIntT<T>::ToInt() const
{
long long ret = 0, temp = 0;
size_t i = 0;

while (i * sizeof(T) < sizeof(int) && m_aValue.Size() > i)
{
temp = m_aValue[i];
temp <<= i * sizeof(T) * 8;
ret |= temp;
++i;
}

if (!m_bPositive)
{
ret = - ret;
}

return (int)ret;
}

template <typename T>
long BigIntT<T>::ToLong() const
{
long long ret = 0, temp = 0;
size_t i = 0;

while (i * sizeof(T) < sizeof(long) && m_aValue.Size() > i)
{
temp = m_aValue[i];
temp <<= i * sizeof(T) * 8;
ret |= temp;
++i;
}

if (!m_bPositive)
{
ret = - ret;
}

return (long)ret;
}

template <typename T>
long long BigIntT<T>::ToLongLong() const
{
long long ret = 0, temp = 0;
size_t i = 0;

while (i * sizeof(T) < sizeof(long long) && m_aValue.Size() > i)
{
temp = m_aValue[i];
temp <<= i * sizeof(T) * 8;
ret |= temp;
++i;
}

if (!m_bPositive)
{
ret = - ret;
}

return (long long)ret;
}

template <typename T>
BigIntT<T> &BigIntT<T>::FromString(const wchar_t *string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF")
{
m_aValue.Clear();
m_bPositive = true;

if (base < 2 || base > (unsigned int)alphabet.Length())
{
return *this;
}

size_t begin = 0;
bool positive = true;

if (string_value[begin] == L'-')
{
positive = false;
++begin;
}

Map<wchar_t, unsigned char> alphabet_reverse;

for (unsigned char i = 0; i < alphabet.Length(); ++i)
{
alphabet_reverse.Insert(alphabet[i], i);
}

for (size_t i = begin; string_value[i] != '\0'; ++i)
{
wchar_t ch = string_value[i];

Map<wchar_t, unsigned char>::Iterator it = alphabet_reverse.Find(ch);

if (it == alphabet_reverse.End())
{
break;
}

*this = (*this) * base + it->Value;
}

this->m_bPositive = positive;

return *this;
}

template <typename T>
BigIntT<T> &BigIntT<T>::FromString(const String &string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF")
{
return FromString(string_value, base, alphabet);
}

template <typename T>
String BigIntT<T>::ToString(unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF") const
{
if (base < 2 || base > (unsigned int)alphabet.Length())
{
return L"";
}

BigIntT<T> temp(*this);
temp.m_bPositive = true;

String ret;

const unsigned int EXP[] = { 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4 };
unsigned int exp = 0;

if (base <= 16 && ((exp = EXP[base]) != 0))
{
for (size_t i = m_aValue.Size() - 1; true; --i)
{
T val = m_aValue[i];
T mask = base - 1;
unsigned int bits = 0;

while ((mask & (1 << (sizeof(T) * 8 - 1))) == 0)
{
mask *= base;
bits += exp;
}

if (i == m_aValue.Size() - 1)
{
while ((mask & val) == 0)
{
mask /= base;
bits -= exp;
}
}

while (mask != 0)
{
ret.AppendBack(alphabet[(val & mask) >> bits]);
mask /= base;
bits -= exp;
}

if (i == 0)
{
break;
}
}
}
else
{
do
{
BigIntT<T> reminder;
temp = temp.Div(base, reminder);

ret.AppendFront(alphabet[reminder.ToChar()]);

} while (temp > 0u);
}

if (!this->m_bPositive)
{
ret.AppendFront(L'-');
}

return ret;
}

} // namespace xl

#endif // #ifndef __XLBigIntT_H_4ED560E8_F226_4D72_9016_828D1AA8696E_INCLUDED__
``````

© 著作权归作者所有

### 曾劲松

01/02
0
0
java.math.BigDecimal cannot be cast to java.lang.String

BigDecimal表示一个大整数，一般情况下很多整型都有个最大值的，但是有时候我们需要处理一些超过这个最大值的值，这个时候就出现了BigDecimal这样的类用于表达大数值，这个错误应该是类型转换...

ty2538402559
2017/11/02
0
0
JAVA数学包

Java.lang.Math类 提供了基本数学函数运算 Math.PI：圆周率 Math.E：自然常量 常见方法 abs() ceil()：最近整数 floor()：小于等于最近整数 max()：取大 min()：取小 random()：0.0-1.0的dou...

2009/03/26
1K
0

whatwhowhy
2016/10/21
0
0
java 里面的流输出的时候是big endian还是little endian?

2015/08/24
2.1K
14

forespider
27分钟前
1
0

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>移动窗口</title> <style> body { margin: 0; padding: 0; width: 100%; height: 1000px; background: #eee; } /*示......

31分钟前
2
0

Jenkins中文社区
39分钟前
3
0
【重构】Spring Cloud OAuth 无Token调用源码封装

45分钟前
26
0
watchOS更新后 Apple Watch 4心电图功能已开始支持欧洲用户

linuxCool
54分钟前
3
0