高精度算法之大整数类

思想：

由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。大数运算主要有加、减、乘三种方法。

考虑用数组存储整数，并模拟手算的方法进行加减乘除四则运算。为了能像int一样方便的使用大整数，可以定义结构体，大整数类。

结构体biginteger可用于存储高精度非负整数。这里存储的方案是每8位存在一个数组的元素里，所用base为1亿，也就是1e8这么多，从低位向高位存储

比如：123456789123456789 存储为| 23456789 |34567891 |12|在一个数组中。

大数结构体：

代码：

 1 struct biginteger
 2 {
 3     static const int base = 100000000;
 4     static const int width = 8;
 5     vector<int> s;
 6 
 7     biginteger(long long num = 0) {*this = num;}//构造函数
 8     biginteger operator=(long long num)//赋值运算符
 9     {
10         s.clear();
11         do
12         {
13             s.push_back(num%base);
14             num /= base;
15         }while(num>0);
16         return *this;
17     }
18     biginteger operator=(const string& str)//赋值运算符
19     {
20         s.clear();
21         int x,len = (str.length()-1)/width+1;
22         for(int i = 0;i<len;i++)
23         {
24             int end = str.length()-i*width;
25             int start = max(0,end-width);
26             sscanf(str.substr(start,end-start).c_str(),"%d",&x);
27             s.push_back(x);
28         }
29         return *this;
30     }
31 }

大数类的输入输出运算符重载：

还可以重载“<<”和“>>”运算符，使用方便

代码：

 1 friend ostream& operator<<(ostream &out,const biginteger& x)
 2     {
 3         out << x.s.back();
 4         for(int i = x.s.size()-2;i>=0;i--)
 5         {
 6             char buf[20];
 7             sprintf(buf,"%8d",x.s[i]);
 8             for(int j = 0;j<strlen(buf);j++)
 9             {
10                 out << buf[j];
11             }
12         }
13         return out;
14     }
15     friend istream& operator>>(istream &in,biginteger& x)
16     {
17         string s;
18         if(!(in >> s)) return in;
19         x = s;
20         return in;
21     }

由于c++的继承机制，现在istream类和ostream类都可以使用它来输出输入大整数了

上述代码中base是静态成员变量，属于这个类型而不属于静态对象，用static修饰

大数类的加法：

 1  biginteger operator+(const biginteger& b) const
 2     {
 3         biginteger c;
 4         c.s.clear();
 5         for(int i = 0,g = 0;;i++)
 6         {
 7             if(g==0&&i>=s.size()&&i>=b.s.size())//当进位为零并且加完了，退出。如果加完了进位不为零，就继续把进位补上，在退出
 8             {
 9                 break;
10             }
11             int x = g;//g为进位数，满一个base才向下进一位
12             if(i<s.size()) x+=s[i];
13             if(i<b.s.size()) x+=b.s[i];
14             c.s.push_back(x%base);//进位后本位上的数
15             g = x/base;//更新进位数
16         }
17         return c;
18     }
19     biginteger operator+=(const biginteger& b)
20     {
21         *this = *this+b;
22         return *this;
23     }

大数类的比较：

一开始就比较两个数的位数，不相等直接返回，否则从后往前比（低位在前）。注意这是在没有前导零的情况下才能这样比，有前导零最后一位还要单独处理。

代码：

bool operator<(const biginteger& b) const
    {
        if(s.size()!=b.s.size())
        {
            return s.size()<b.s.size();
        }
        for(int i = s.size()-1;i>=0;i--)
        {
            if(s[i]!=b.s[i])
            {
                return s[i]<b.s[i];
            }
        }
        return false;
    }
    bool operator>(const biginteger& b) const
    {
        return b<*this;
    }
    bool operator<=(const biginteger& b) const
    {
        return !(b<*this);
    }
    bool operator>=(const biginteger& b) const
    {
        return !(*this<b);
    }
    bool operator!=(const biginteger& b) const
    {
        return (b< *this||*this<b);
    }
    bool operator==(const biginteger& b) const
    {
        return !(b<*this)&&!(*this<b);
    }

这时依赖比较运算符的容器函数就可以支持大整数类了。

代码汇总：

 

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <vector>
  4 #include <cstring>
  5 #include<set>
  6 #include<map>
  7 using namespace std;
  8 struct biginteger
  9 {
 10     static const int base = 100000000;
 11     static const int width = 8;
 12     vector<int> s;
 13 
 14     biginteger(long long num = 0) {*this = num;}//构造函数
 15     biginteger operator=(long long num)//赋值运算符
 16     {
 17         s.clear();
 18         do
 19         {
 20             s.push_back(num%base);
 21             num /= base;
 22         }while(num>0);
 23         return *this;
 24     }
 25     biginteger operator=(const string& str)//赋值运算符
 26     {
 27         s.clear();
 28         int x,len = (str.length()-1)/width+1;
 29         for(int i = 0;i<len;i++)
 30         {
 31             int end = str.length()-i*width;
 32             int start = max(0,end-width);
 33             sscanf(str.substr(start,end-start).c_str(),"%d",&x);
 34             s.push_back(x);
 35         }
 36         return *this;
 37     }
 38     friend ostream& operator<<(ostream &out,const biginteger& x)
 39     {
 40         out << x.s.back();
 41         for(int i = x.s.size()-2;i>=0;i--)
 42         {
 43             char buf[20];
 44             sprintf(buf,"%8d",x.s[i]);
 45             for(int j = 0;j<strlen(buf);j++)
 46             {
 47                 out << buf[j];
 48             }
 49         }
 50         return out;
 51     }
 52     friend istream& operator>>(istream &in,biginteger& x)
 53     {
 54         string s;
 55         if(!(in >> s)) return in;
 56         x = s;
 57         return in;
 58     }
 59 
 60     bool operator<(const biginteger& b) const
 61     {
 62         if(s.size()!=b.s.size())
 63         {
 64             return s.size()<b.s.size();
 65         }
 66         for(int i = s.size()-1;i>=0;i--)
 67         {
 68             if(s[i]!=b.s[i])
 69             {
 70                 return s[i]<b.s[i];
 71             }
 72         }
 73         return false;
 74     }
 75     bool operator>(const biginteger& b) const
 76     {
 77         return b<*this;
 78     }
 79     bool operator<=(const biginteger& b) const
 80     {
 81         return !(b<*this);
 82     }
 83     bool operator>=(const biginteger& b) const
 84     {
 85         return !(*this<b);
 86     }
 87     bool operator!=(const biginteger& b) const
 88     {
 89         return (b< *this||*this<b);
 90     }
 91     bool operator==(const biginteger& b) const
 92     {
 93         return !(b<*this)&&!(*this<b);
 94     }
 95     biginteger operator+(const biginteger& b) const
 96     {
 97         biginteger c;
 98         c.s.clear();
 99         for(int i = 0,g = 0;;i++)
100         {
101             if(g==0&&i>=s.size()&&i>=b.s.size())//当进位为零并且加完了，退出。如果加完了进位不为零，就继续把进位补上，在退出
102             {
103                 break;
104             }
105             int x = g;//g为进位数，满一个base才向下进一位
106             if(i<s.size()) x+=s[i];
107             if(i<b.s.size()) x+=b.s[i];
108             c.s.push_back(x%base);//进位后本位上的数
109             g = x/base;//更新进位数
110         }
111         return c;
112     }
113     biginteger operator+=(const biginteger& b)
114     {
115         *this = *this+b;
116         return *this;
117     }
118 };
119 set<biginteger> s;
120 map<biginteger, int> m;
121 int main()
122 {
123     biginteger y;
124     biginteger x = y;
125     biginteger z = 123;
126 
127     biginteger a, b;
128     cin >> a >> b;
129     cout << a + b << "\n";
130     cout << biginteger::base << "\n";
131     return 0;
132 }

 

参考代码：https://github.com/aoapc-book/aoapc-bac2nd/blob/master/ch5/biginteger.cpp

参考文章：

关于sscanf，sprintf的使用：

https://www.runoob.com/cprogramming/c-function-sscanf.html

https://www.runoob.com/cprogramming/c-function-sprintf.html