高精度算法之大整数类
思想：
由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。大数运算主要有加、减、乘三种方法。
考虑用数组存储整数，并模拟手算的方法进行加减乘除四则运算。为了能像int一样方便的使用大整数，可以定义结构体，大整数类。
结构体BigInteger可用于存储高精度非负整数。这里存储的方案是每8位存在一个数组的元素里，所用base为1亿，也就是1e8这么多，从低位向高位存储
比如：123456789123456789存储为|23456789|34567891|12|在一个数组中。
大数结构体：
代码：
1structBigInteger
2{
3staticconstintBASE=100000000;
4staticconstintWIDTH=8;
5vector<int>s;
6
7BigInteger(longlongnum=0){*this=num;}//构造函数
8BigIntegeroperator=(longlongnum)//赋值运算符
9{
10s.clear();
11do
12{
13s.push_back(num%BASE);
14num/=BASE;
15}while(num>0);
16return*this;
17}
18BigIntegeroperator=(conststring&str)//赋值运算符
19{
20s.clear();
21intx,len=(str.length()-1)/WIDTH+1;
22for(inti=0;i<len;i++)
23{
24intend=str.length()-i*WIDTH;
25intstart=max(0,end-WIDTH);
26sscanf(str.substr(start,end-start).c_str(),"%d",&x);
27s.push_back(x);
28}
29return*this;
30}
31}
大数类的输入输出运算符重载：
还可以重载“<<”和“>>”运算符，使用方便
代码：
1friendostream&operator<<(ostream&out,constBigInteger&x)
2{
3out<<x.s.back();
4for(inti=x.s.size()-2;i>=0;i--)
5{
6charbuf[20];
7sprintf(buf,"%8d",x.s[i]);
8for(intj=0;j<strlen(buf);j++)
9{
10out<<buf[j];
11}
12}
13returnout;
14}
15friendistream&operator>>(istream&in,BigInteger&x)
16{
17strings;
18if(!(in>>s))returnin;
19x=s;
20returnin;
21}
由于c++的继承机制，现在istream类和ostream类都可以使用它来输出输入大整数了
上述代码中BASE是静态成员变量，属于这个类型而不属于静态对象，用static修饰
大数类的加法：
1BigIntegeroperator+(constBigInteger&b)const
2{
3BigIntegerc;
4c.s.clear();
5for(inti=0,g=0;;i++)
6{
7if(g==0&&i>=s.size()&&i>=b.s.size())//当进位为零并且加完了，退出。如果加完了进位不为零，就继续把进位补上，在退出
8{
9break;
10}
11intx=g;//g为进位数，满一个BASE才向下进一位
12if(i<s.size())x+=s[i];
13if(i<b.s.size())x+=b.s[i];
14c.s.push_back(x%BASE);//进位后本位上的数
15g=x/BASE;//更新进位数
16}
17returnc;
18}
19BigIntegeroperator+=(constBigInteger&b)
20{
21*this=*this+b;
22return*this;
23}
大数类的比较：
一开始就比较两个数的位数，不相等直接返回，否则从后往前比（低位在前）。注意这是在没有前导零的情况下才能这样比，有前导零最后一位还要单独处理。
代码：
booloperator<(constBigInteger&b)const
{
if(s.size()!=b.s.size())
{
returns.size()<b.s.size();
}
for(inti=s.size()-1;i>=0;i--)
{
if(s[i]!=b.s[i])
{
returns[i]<b.s[i];
}
}
returnfalse;
}
booloperator>(constBigInteger&b)const
{
returnb<*this;
}
booloperator<=(constBigInteger&b)const
{
return!(b<*this);
}
booloperator>=(constBigInteger&b)const
{
return!(*this<b);
}
booloperator!=(constBigInteger&b)const
{
return(b<*this||*this<b);
}
booloperator==(constBigInteger&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>
7usingnamespacestd;
8structBigInteger
9{
10staticconstintBASE=100000000;
11staticconstintWIDTH=8;
12vector<int>s;
13
14BigInteger(longlongnum=0){*this=num;}//构造函数
15BigIntegeroperator=(longlongnum)//赋值运算符
16{
17s.clear();
18do
19{
20s.push_back(num%BASE);
21num/=BASE;
22}while(num>0);
23return*this;
24}
25BigIntegeroperator=(conststring&str)//赋值运算符
26{
27s.clear();
28intx,len=(str.length()-1)/WIDTH+1;
29for(inti=0;i<len;i++)
30{
31intend=str.length()-i*WIDTH;
32intstart=max(0,end-WIDTH);
33sscanf(str.substr(start,end-start).c_str(),"%d",&x);
34s.push_back(x);
35}
36return*this;
37}
38friendostream&operator<<(ostream&out,constBigInteger&x)
39{
40out<<x.s.back();
41for(inti=x.s.size()-2;i>=0;i--)
42{
43charbuf[20];
44sprintf(buf,"%8d",x.s[i]);
45for(intj=0;j<strlen(buf);j++)
46{
47out<<buf[j];
48}
49}
50returnout;
51}
52friendistream&operator>>(istream&in,BigInteger&x)
53{
54strings;
55if(!(in>>s))returnin;
56x=s;
57returnin;
58}
59
60booloperator<(constBigInteger&b)const
61{
62if(s.size()!=b.s.size())
63{
64returns.size()<b.s.size();
65}
66for(inti=s.size()-1;i>=0;i--)
67{
68if(s[i]!=b.s[i])
69{
70returns[i]<b.s[i];
71}
72}
73returnfalse;
74}
75booloperator>(constBigInteger&b)const
76{
77returnb<*this;
78}
79booloperator<=(constBigInteger&b)const
80{
81return!(b<*this);
82}
83booloperator>=(constBigInteger&b)const
84{
85return!(*this<b);
86}
87booloperator!=(constBigInteger&b)const
88{
89return(b<*this||*this<b);
90}
91booloperator==(constBigInteger&b)const
92{
93return!(b<*this)&&!(*this<b);
94}
95BigIntegeroperator+(constBigInteger&b)const
96{
97BigIntegerc;
98c.s.clear();
99for(inti=0,g=0;;i++)
100{
101if(g==0&&i>=s.size()&&i>=b.s.size())//当进位为零并且加完了，退出。如果加完了进位不为零，就继续把进位补上，在退出
102{
103break;
104}
105intx=g;//g为进位数，满一个BASE才向下进一位
106if(i<s.size())x+=s[i];
107if(i<b.s.size())x+=b.s[i];
108c.s.push_back(x%BASE);//进位后本位上的数
109g=x/BASE;//更新进位数
110}
111returnc;
112}
113BigIntegeroperator+=(constBigInteger&b)
114{
115*this=*this+b;
116return*this;
117}
118};
119set<BigInteger>s;
120map<BigInteger,int>m;
121intmain()
122{
123BigIntegery;
124BigIntegerx=y;
125BigIntegerz=123;
126
127BigIntegera,b;
128cin>>a>>b;
129cout<<a+b<<"\n";
130cout<<BigInteger::BASE<<"\n";
131return0;
132}
ViewCode
如需转载，请注明文章出处和来源网址：http://www.divcss5.com/html/h56811.shtml
