高精度算法之大整数类

2019-08-16 07:55:29来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

高精度算法之大整数类

思想:

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

考虑用数组存储整数,并模拟手算的方法进行加减乘除四则运算。为了能像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 }
View Code

 

参考代码: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


原文链接:https://www.cnblogs.com/zhanhonhao/p/11255454.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:从“约瑟夫问题”谈起

下一篇:P3121 [USACO15FEB]审查(AC自动机)