文档章节

大整数类

曾劲松
 曾劲松
发布于 2016/08/02 20:46
字数 4137
阅读 17
收藏 0

参考来源:

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__

 

© 著作权归作者所有

曾劲松
粉丝 5
博文 200
码字总数 141434
作品 0
武汉
私信 提问
自定义40位长整数类及测试类(通过字符串解析构造、静态方法求和等)(Huge Integer Class)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/hpdlzu80100/article/details/85627856 功能: 1. 使用字符串解析构建一个40位的整数 2. 实现加减运算及其他一...

预见未来to50
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
有趣的Integer.Java 类缓存

如果你运行下面的代码 你会得到:false true 基本知识:我们知道,如果两个引用指向同一个对象,用==表示它们是相等的。如果两个引用指向不同的对象,用==表示它们是不相等的,即使它们的内容...

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

我是javaer. java里面的OutputStream和DataOutputStream,我测试了一下,看了他们输出了整数的文件,用16进制查看后,发现是big endian,如short类型的122,输出为00 7a,又查了资料说,java里面默认...

李嘉图
2015/08/24
2.1K
14

没有更多内容

加载失败,请刷新页面

加载更多

前嗅教程:如何获取精准客源,提高销量

经常有人问嗅嗅,我是XX行业的,大数据能帮我做什么? • 可以给我带来客源吗? • 可以提高我的销量吗? • 可以增加我的利润吗? 今天嗅嗅就以生鲜供货为例,为大家讲一讲外卖平台那些事~...

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 master 共享 JENKINS_HOME 目录的实验

本文首发于:Jenkins 中文社区 作者:翟志军 审校:王冬辉,linuxsuren Jenkins master 的高可用是个老大难的问题。和很多人一样,笔者也想过两个 Jenkins master 共享同一个 JENKINS_HOME 的...

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

背景 重构-改善既有代码的设计,重构的目的是是软件更容易被理解和修改。 书接上回Spring Security OAuth 微服务内部Token传递的源码解析,本篇主要无token 调用过程中,代码的不断完善及其重...

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

苹果在发布 Apple Watch 4 系列时也发布了 ECG(心电图)功能,但这项功能仅适用于在美版 Apple Watch。对于其他地区的用户来说,访问该功能的唯一途径是在美国购买该设备。不过当 watchOS ...

linuxCool
54分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部