1 #include<iostream>
2 #include<string>
3 #include<cstring>
4 using namespace std;
5 const int M=400;
6 const int BASE=10;
7 //****************************************
8 class BigInt
9 {
10 friend BigInt operator+(const BigInt &a,const BigInt &b);
11 friend BigInt operator*(const BigInt &a,const BigInt &b);
12 friend BigInt operator-(const BigInt &a,const BigInt &b);
13 friend BigInt operator/(const BigInt &a,const BigInt &b);
14 friend ostream& operator<<( ostream &os,BigInt &a);
15 //friend power(BigInt &BASE,BigInt &n);
16 private:
17 static int pos;
18 //小数点的位置 pos存放小数点后第一位。比如：3456.123 pos存放6
19 int sign; //数的正负 1为正数，-1为负数，
20 int before; // 小数点前的位数
21 int after; //小数点后的位数
22 int data[M];
23 // BigInt NormalAdd(const BigInt &a,const BigInt &b);
24 BigInt NormalAdd(const BigInt &a);// 不考虑符号加法运算 return this+a
25 BigInt NormalSubtract( const BigInt & a); //要求this>a进行减法 ,且不考虑符号
26 public:
27 BigInt();
28 BigInt( string str);
29 static void SetPos(int m){pos=m;}
30 int AbsCompare(const BigInt &a);
31 int Compare(const BigInt &a); // this>a return 1 ;this<a return -1;this ==a reuturn 0;
32 BigInt Add( BigInt &a);
33 BigInt Subtract(BigInt &a);
34 BigInt Mul(const BigInt &a);
35 };
36 //****************************************
37 BigInt::BigInt()
38 {
39 memset(data,0,sizeof(data));
40 after=0;
41 sign=1;
42 before=0;
43 }
44 //***********************************************************
45 BigInt::BigInt( string str)
46 {
47 memset(data,0,sizeof(data));
48 if(str[0]!='-')
49 sign=1;
50 else sign=-1;
51 if(str[0]=='-' || str[0]=='+')
52 str.erase(0,1);
53 unsigned int loc=str.find('.',0);
54 int len=str.length();
55 if(loc==string::npos)
56 {
57 after=0;
58 before=len;
59 for(int i=len-1,j=pos;i>=0;--i,++j)
60 {
61 data[j]=str[i]-'0';
62 }
63 }
64 else
65 {
66 for(int i=loc-1,j=pos;i>=0;--i,++j)
67 {
68 data[j]=str[i]-'0';
69 }
70 before=loc;
71 for(int i=loc+1,j=pos-1;i<len;++i,--j)
72 {
73 data[j]=str[i]-'0';
74 }
75 after=len-loc-1;
76 }
77 while(after>0 && data[pos-after]==0)
78 --after;
79
80 while(before>0 && data[pos+before-1]==0)
81 --before;
82 }
83 //***********************************************************
84 //*********************************************************************
85 BigInt BigInt::NormalAdd(const BigInt & a)
86 {
87 BigInt res;
88 res.sign=sign;
89 res.after=a.after>after ? a.after:after;
90 int bef=a.before>before ? a.before: before;
91 for(int i=pos-res.after; i<pos+bef; ++i)
92 {
93 res.data[i]+=data[i]+a.data[i];
94 if(res.data[i]>=BASE)
95 {
96 res.data[i+1]+=res.data[i]/BASE;
97 res.data[i]%=BASE;
98 }
99 }
100 while(res.data[pos+bef])
101 {
102 res.data[pos+bef+1]+=res.data[pos+bef]/BASE;
103 res.data[pos+bef]%=BASE;
104 ++bef;
105 }
106 res.before=bef;
107 while(res.after>0 && res.data[pos-res.after]==0)
108 {
109 --res.after;
110 }
111 return res;
112 }
113 //********************************************************
114 int BigInt::AbsCompare(const BigInt &a)
115 {
116 if(before>a.before) return 1;
117 else if(before<a.before) return -1;
118 else
119 {
120 int t=after>a.after ? after: a.after;
121 t=pos-t;
122 for(int i=pos+before-1; i>=t; --i)
123 {
124 if(data[i]>a.data[i])
125 return 1;
126 else if(data[i]<a.data[i])
127 return -1;
128 }
129 }
130 return 0;
131 }
132 //*********************************************************
133 int BigInt::Compare(const BigInt &a)
134 {
135 if(sign>a.sign) return 1;
136 else if(sign<a.sign) return -1;
137 else return sign*AbsCompare(a);
138 }
139 //**********************************************************
140 BigInt BigInt::NormalSubtract( const BigInt &a)
141 {
142 BigInt res;
143 res.after=after>a.after ? after: a.after;
144 for(int i=pos-res.after; i<pos+before; ++i)
145 {
146 res.data[i]=data[i]-a.data[i];
147 }
148 for(int i=pos-res.after; i<pos+before; ++i)
149 {
150 if(res.data[i]<0)
151 {
152 res.data[i]+=BASE;
153 res.data[i+1]-=1;
154 }
155 }
156 int bef=before;
157 while(bef)
158 {
159 if(res.data[pos+bef-1])
160 break;
161 --bef;
162 }
163 res.before=bef;
164 while(res.after>0 && res.data[pos-res.after]==0)
165 {
166 --res.after;
167 }
168 return res;
169 }
170 //*********************************************************
171 BigInt BigInt::Add( BigInt &a)
172 {
173 if(sign==a.sign)
174 return NormalAdd(a);
175 BigInt res;
176 if(sign>a.sign)
177 {
178 if(AbsCompare(a)>=0)
179 {
180 res=NormalSubtract(a);
181 res.sign=1;
182 }
183 else
184 {
185 res=a.NormalSubtract(*this);
186 res.sign=-1;
187 }
188 }
189 else if(sign<a.sign)
190 {
191 if(AbsCompare(a)>0)
192 {
193 res=NormalSubtract(a);
194 res.sign=-1;
195 }
196 else
197 {
198 res=a.NormalSubtract(*this);
199 res.sign=1;
200 }
201 }
202 return res;
203 }
204 //********************************************************
205 BigInt BigInt::Subtract(BigInt &a)
206 {
207 if(sign!=a.sign)
208 {
209 return NormalAdd(a);
210 }
211 BigInt res;
212 if(sign==1)
213 {
214 if(AbsCompare(a)>=0)
215 {
216 res=NormalSubtract(a);
217 res.sign=1;
218 }
219 else
220 {
221 res=a.NormalSubtract(*this);
222 res.sign=-1;
223 }
224 }
225 else if(sign==-1)
226 {
227 if(AbsCompare(a)>0)
228 {
229 res=NormalSubtract(a);
230 res.sign=-1;
231 }
232 else
233 {
234 res=a.NormalSubtract(*this);
235 res.sign=1;
236 }
237 }
238 return res;
239 }
240 //********************************************************
241 BigInt BigInt::Mul(const BigInt &a)
242 {
243 BigInt res;
244 if(sign!=a.sign) res.sign=-1;
245 else res.sign=1;
246 int len=before+after;
247 int alen=a.before+a.after;
248 for(int i=0,j=pos-after; i<len; ++i,++j) //计算
249 {
250 for(int k=0,t=a.pos-a.after; k<alen; ++k,++t)
251 {
252 res.data[i+k]+=data[j]*a.data[t];
253 }
254 }
255 for(int i=0;i<len+alen;++i) //进位
256 {
257 if(res.data[i]>=BASE)
258 {
259 res.data[i+1]+=res.data[i]/BASE;
260 res.data[i]%=BASE;
261 }
262 }
263 int shift=pos-after-a.after; //计算应该移动的位数
264 for(int i=len+alen; i>=0; --i)
265 {
266 res.data[i+shift]=res.data[i];
267 res.data[i]=0;
268 }
269 int i=0;
270 while(i<pos)
271 {
272 if(res.data[i]>0) break;
273 ++i;
274 }
275 res.after=pos-i;
276 int bef=alen+len+shift;
277 if(res.data[bef]>0)
278 {
279 while(res.data[bef])
280 {
281 res.data[bef+1]=res.data[bef]/BASE;
282 res.data[bef]%=BASE;
283 ++bef;
284 }
285 res.before=bef-pos;
286 }
287 else
288 {
289 while(bef>=pos)
290 {
291 if(res.data[bef]>0) break;
292 --bef;
293 }
294 res.before=bef-pos+1;
295 }
296 return res;
297 }
298 //********************************************************
299 ostream & operator<<(ostream &os,BigInt &a)
300 {
301 if(a.sign==-1)
302 os<<'-';
303 for(int i=a.before+a.pos-1; i>=a.pos; --i)
304 os<<a.data[i];
305 if(a.after>0)
306 {
307 os<<'.';
308 for(int i=a.pos-1; i>=a.pos-a.after; --i)
309 os<<a.data[i];
310 }
311 if(a.after==0 && a.before==0)
312 os<<'0';
313 return os;
314 }
315 //********************************************************
316 int BigInt::pos=200;
317
高精度应该不是什么陌生的东西了，以前觉得这个东西挺高深的，其实明白了也就没什么了。我们知道对于int只能保存32位的数，long long也不过能保存64位的，若是要更大的数就只能自己动手写了，大概就是模拟笔算而已。 对于一个大数怎么来表示我们先约定一个格式。用一个int类型的sign来表示符号位，正数为1，负数为-1。用一个int数组data[]来存储数据，用一个int类型的数字pos来表示小数点所在的地方，这个数字对于所有的BigInt应该是相同的所以用静态变量。before表示小数点前面有几位数字，after表示小数点后面有几位数字。比如说：-356.5672 sign为-1，before为3，after为4。当然可以用其他方法表示，只是我觉得用着这样的表示方法有很多有点。 AbsCompare()为其绝对值的比较。 NormalSubtract( const BigInt &a)为不考虑符号的减法运算要求|this|>|a|,返回值为|this|-|a|,比如：-100-（-50）返回值为50。 对于加法Add运算可分为，正数+正数，负数+正数，正数+负数，负数+负数，不考虑符号位的加法称为NormalAdd()，对于正数+正数，负数+负数，可以用NormalAdd()，然后考虑符号为就行了。比如说：(-123）+(-456) 可以认为是123+456然后再为其加符号位-1，即-（123+456）。而对于正数+负数，负数+正数，其实是普通的减法。比如说：567+（-123），其实是567-123； -567 +123 亦是如此。 对于减法Subtract运算亦可分为：正数-正数，正数-负数，负数-正数，负数-负数。正数-负数其实是加法运算，例如： 100-（-200）==100+200；负数-正数也可看成加法运算，然后再考虑符号问题，例如：-100 - 200==-（100+200）；正数-正数要分开考虑：减数的绝对值大于被减数的绝对值，被减数的绝对值大于减数的绝对值，然后在进行Norsubtract运算，之后考虑符号为就可以了。例如：500-200==+（300），200-500==-（500-200）。负数-负数同正数-正数相同。 乘法Mul则相对简单一些，同号得正，异号得负。然后考虑正数的乘法运算，模仿笔算乘法就行了。 除法其实是减法，逐次相减就可以了，代码里没有写。