博客

需要注意的是，BASE一定要用LL,在vc中是__int64

下面是代码：

代码里面会有详细的注释：

#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef __int64 LL;
//不可以对结构体和结构体的赋值再定义=号
struct BigInteger
{
    vector<LL>S;

    //定义了构造函数之后，需要再去重载构造函数中的=号
    BigInteger(LL num = 0){*this = num;}//构造函数不可以返回一个值，非常重要，需要缺省定义num = 0的情况
    BigInteger(string num){*this = num;}//字符串的构造函数，有了这个函数就可以直接A(string)或者A = string,上面的LL类型也是一样的



    //结构体之间的赋值绝对不可以再次定义
    BigInteger operator = (LL num)
    {
        S.clear();
        while(num)
        {
            S.push_back(num % 100000000);//对后面有8个零的数取余数，最后结果一定小于8位
            num = num / 100000000;
        }
        return *this;//这里返回这个结构体本身，所以是*this
    }

    //string的运算符重载，需要从后往前
    BigInteger operator = (string num)
    {
        int end = num.size();
        int start ;
        do
        {
            start = end - 8;
            if(start < 0)//有可能遇到开头
            {
                start = 0;        
            }
            LL sum = 0;
            for(int i = start;i < end;i++)//计算这个8位的值，当然可能是0，如果是0，那么这个vector中就加入0就可以了
            {
                sum = sum * 10 + num[i] - '0';
            }
            S.push_back(sum);
            end = start;
        }while(start);
        return *this;
    }

    //输出，要特别注意vector中不够8位的情况，比如说500000000000001，第一个vector中的值是1，所以要先放到一个buffer中
    void output()
    {
        printf("%ld",S[S.size() - 1]);//最后一个不用输出前导0
        for(int i = S.size() - 2;i >= 0;i--)
        {
            char s[20];
            sprintf(s,"%08d",S[i]);//最多输出8位，不够8位的加前导0
            for(int j = 0 ; j < 8;j++)
            {
                printf("%c",s[j]);
            }
        }
        cout<<endl;
    }

    //加法
    BigInteger operator + (BigInteger B)
    {
        BigInteger C;
        C.S.clear();//这个地方必须加这一句，因为不加这一句，可能会直接加入到一个已经有数据的vector中
        LL g = 0;

        //g必须是longlong类型的，不然会溢出，还有就是g代表这次相加的结果
        for(int i = 0,j = 0;i < B.S.size() || j < S.size() || g;i++,j++)
        {
            if(i < B.S.size())
            {
                g = g + B.S[i];
            }
            if(j < S.size())
            {
                g = g + S[i];
            }
            C.S.push_back(g % 100000000);
            g = g / 100000000;
        }
        return C;
    }

    //和整数的乘法
    BigInteger operator * (int num)
    {
        BigInteger C;
        C.S.clear();
        LL g = 0;
        //和整数的乘法思想很简单，就是直接用这个整数从第一个vector乘到最后一个vector，成绩不会超过10^16，也就是不会超过longlong
        //g代表此次乘的结果，结果可能大于10^8,所以需要取模运算
        for(int i = 0;i < S.size() || g;i++)
        {
            if(i < S.size())
            {
                g = g + S[i] * num;
            }
            C.S.push_back(g % 100000000);
            g = g / 100000000;
        }
        return C;
    }

    //大整数和大整数之间的乘法
    //思想就是利用乘法分配律，让一个大整数的一个vector和另一个大整数整体进行相乘
    //但要注意在后面乘100000000
    BigInteger operator * (BigInteger B)
    {
        BigInteger C;
        C.S.clear();
        LL g = 0;
        for(int i = 0;i < S.size();i++)
        {
            BigInteger D;
            D = B * S[i];//最好选用*前面的那个数的每一个vector作为整数，因为直接乘*this感觉很奇怪
            int j = i;
            while(j)
            {
                D = D * 100000000;
                j--;
            }
//            D.output();
            C = C + D;
        }
        return C;
    }
    //必须是大数减小数
    BigInteger operator - (BigInteger B)
    {
        BigInteger C;
        C.S.clear();
        int flag = 0;//有没有借位;
        for(int i = 0,j = 0;i < S.size();i++,j++)
        {
            LL g = 0;
            if(j < B.S.size())//小数还没有减完
            {
                g = S[i] - B.S[j] + flag;//大数减小数，但是必须考虑进位
                if(g < 0)//如果小于0，那么这次的进位还是要设置成-1
                {
                    g = g + 100000000;
                    flag = -1;
                }
                else//如果不小于0，那么需要设置成0
                {
                    flag = 0;
                }
            }
            else //小数的计算完了，有可能只剩下大数了，也可能什么都没有
            {
                g = g + S[i] + flag;//这个时候任然需要考虑进位，以及此时是不是负数
                if(g < 0)
                {
                    g = g + 100000000;
                    flag = -1;
                }
                else
                {
                    flag = 0;
                }
            }
            C.S.push_back(g);
        }
        return C;
    }

    //最主要要定义<号
    bool operator < (BigInteger B)
    {
        //相等的时候放在最后判断
        if(S.size() < B.S.size())//相等的情况最后判断
        {
            return true;
        }
        else if(S.size() > B.S.size())
        {
            return false;//非常重要
        }
        for(int i = B.S.size();i >= 0;i--)
        {
            if(S[i] < B.S[i])
            {
                return true;
            }
            else if(S[i] > B.S[i])
            {
                return false;//非常重要，因为小的数的低位可能会大于大的数
            }
        }
        return false;
    }

    //依据小于号来判断大于号就可以
    bool operator > (BigInteger B)
    {
        if(B < *this)
        {
            return true;
        }
        return false;
    }
};
int main()
{

    //如果是一个负数，那么需要把它变成正数和符号的结合体
    //然后再进行计算
    BigInteger A("555555000000000000000000001");
    A.output();
    BigInteger B("11234");
    B.output();
    BigInteger C = A - B;
    C.output();
    if(A < B)
    {
        printf("YES\n");
    }
    return 0;
}