高精度模板支持各种运算 c++

绪言

自从有了高精度模板，妈妈再也不用怕我不会打高精度了！

代码

代码长度与日俱增啊~~~

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<cmath>
  5 using namespace std;
  6 
  7 bool insigma(char ch){
  8     return ch=='-'||('0'<=ch&&ch<='9');
  9 }
 10 
 11 const int maxn = 1000;
 12 struct number{
 13     int num[maxn];
 14     int len;
 15     bool fu;
 16     
 17     number(){//初始化 
 18         len=fu=0;
 19         memset(num,0,sizeof(num));
 20     }
 21     
 22     int updata_len(){//更新长度 
 23         for(int i=maxn-1;i>=0;i--) if(num[i]) return len=i+1;
 24         return len=0;
 25     }
 26     
 27     //    /*
 28     number operator= (int x){//隐式转换 
 29         fu=(x<0);
 30         num[0]=abs(x);
 31         if(x>9) carry_bit();
 32         if(x<-9) back_space();
 33         return *this;
 34     }
 35 //    */
 36     /*
 37     number (int x){//有bug的构造函数 暂时用重载=替代 
 38         fu=(x<0);
 39         num[0]=abs(x);
 40         if(x>9) carry_bit();
 41         if(x<-9) back_space();
 42     }
 43     */
 44     
 45     void input(){
 46 //        /*
 47         string a;
 48         cin>>a;
 49         if(a[0]=='-'){
 50             fu=1;
 51             len=a.size()-1;
 52             for(unsigned int i=0;i<a.size()-1;i++) num[i]=a[a.size()-i-1]-'0';
 53         }
 54         else{
 55             len=a.size();
 56             for(unsigned int i=0;i<a.size();i++)    num[i]=a[a.size()-i-1]-'0';
 57         }
 58         
 59 //        */
 60         /*
 61         len=0;
 62         char ch;
 63         while(!insigma(ch=getchar()));
 64         if(ch=='-')
 65             fu=true;
 66         else 
 67             num[len++]=ch-'0';
 68         while(isdigit(ch=getchar())){
 69             num[len++]=ch-'0';
 70         }
 71         int t;
 72         for(int i=0;i<len;i++)
 73         {
 74             t=num[i];
 75             num[i]=num[len-i-1];
 76             num[len-i-1]=t; 
 77         }
 78         */
 79     }
 80     
 81     void output(){
 82         if(fu) cout<<"-";
 83         bool flag=0;
 84         for(int i=len;i>0;i--){
 85             if(num[i]) flag=1;
 86             if(num[i]>9) carry_bit(); 
 87             if(flag) putchar(num[i]+'0');//putchar加速 
 88         }
 89         putchar(num[0]+'0');
 90     }
 91     
 92     friend istream & operator>> (istream &in, number &obj);    
 93     friend ostream & operator<< (ostream &out, number &obj);
 94     
 95     int compare(number x){//2=    1> 0<
 96         if(fu^x.fu){
 97             if(fu) return 0; 
 98             else return 1;
 99         }
100         for(int i=max(len,x.len);i>=0;i--)
101         {
102             if(num[i]>x.num[i]) return !fu;//大于 (1)
103             if(num[i]<x.num[i]) return fu;//小于 (0)
104         }
105         return 2;//相等 
106     }
107     
108     //利用compare()重载比较运算符 
109      
110     bool operator> (number x){
111         return (compare(x)==1);
112     } 
113     
114     bool operator< (number x){
115         return (compare(x)==0);
116     }
117     
118     bool operator>= (number x){
119         return !(*this<x);
120     }
121     
122     bool operator<= (number x){
123         return !(*this>x);
124     }
125     
126     bool operator== (number x){
127         return compare(x)==2;
128     }
129     
130     bool operator!= (number x){
131         return compare(x)!=2;
132     }
133 
134     number operator++ (){
135         num[0]++;
136         if(num[0]>9) carry_bit();
137         return *this;
138     }
139     
140     number operator++ (int){
141         number save=*this;
142         ++*this;
143         return save;
144     }
145     
146     number operator-- (){
147         num[0]--;
148         if(num[0]<0) back_space();
149         return *this;
150     }
151     
152     number operator-- (int){
153         number save=*this;
154         num[0]--;
155         if(num[0]<0) back_space();
156         return save;
157     }
158     
159     bool judge_zero(){
160         for(int i=maxn-1;i>=0;i--)
161             if(num[i]) return 0;
162         return 1;
163     }
164     
165     bool judge_non_zero(){
166         return !judge_zero();
167     }
168     
169     bool convert_bool(){
170         return !judge_zero();
171     }
172     
173     bool even(){
174         if(num[0]%2) return 0;
175         return 1;
176     }
177     
178     bool odd(){
179         if(num[0]%2) return 1;
180         return 0;
181     }
182     
183     void carry_bit(){
184         for(int i=0;i<maxn;i++){
185             num[i+1]+=num[i]/10;
186             num[i]%=10;
187         }
188         updata_len();
189     }
190     
191     void back_space(){
192         for(int i=0;i<maxn;i++){
193             while(num[i]<0) num[i]+=10,num[i+1]--;
194         }
195     }
196     
197     number operator+ (int x){
198         number newness=*this;
199         newness.num[0]+=x;
200         if(newness.num[0]>9) newness.carry_bit();
201         return newness;
202     }
203     
204     number operator+ (number x){
205         number res=x;
206         for(int i=0;i<maxn;i++)
207         {
208             res.num[i]+=num[i];
209         }
210         res.carry_bit();
211         return res;
212     }
213     
214     number operator+= (int x){
215         *this=(*this+x);
216         return *this;
217     }
218     
219     number operator+= (number x){
220         *this=*this+x;
221         return *this;
222     }
223     
224     number operator- (number x){
225         number i,j;
226         if(compare(x)) {i=*this,j=x;}
227         else {i=x,j=*this;}
228         for(int t=0;t<maxn;t++)
229         {
230             i.num[t]-=j.num[t];
231         }
232         i.back_space();
233         return i;
234     }
235     
236     number operator-= (number x){
237         *this=*this-x;
238         return *this; 
239     }
240     
241     number operator* (number x){
242         number sum;
243         sum.fu=fu^x.fu;
244         for(int i=0;i<updata_len();i++)
245         for(int j=0;j<x.updata_len();j++)
246         {
247             if(i+j>maxn-1) continue;
248             sum.num[i+j]+=num[i]*x.num[j];
249         }
250         sum.carry_bit();
251         return sum;
252     }
253     
254     number operator*= (number x){
255         return *this=*this*x;
256     }
257     
258     number factor(){
259         number ans,t;
260         t.num[0]=1;
261         ans.num[0]=1;
262         for(;t<=*this;t.num[0]+=1,t.carry_bit())
263             ans*=t;
264         return ans;
265     }
266     
267     number division2(){
268         for(int i=maxn-1;i>=0;i--){
269             if(num[i]&1&&i!=0) num[i-1]+=10;
270             num[i]>>=1;
271         }
272         return *this;
273     }
274 };
275 
276 istream & operator>> (istream &in, number &obj)
277 {
278     string a;
279     in>>a;
280     if(a[0]=='-'){
281         obj.fu=1;
282         obj.len=a.size()-1;
283         for(unsigned int i=0;i<a.size()-1;i++) obj.num[i]=a[a.size()-i-1]-'0';
284     }
285     else{
286         obj.len=a.size();
287         for(unsigned int i=0;i<a.size();i++) obj.num[i]=a[a.size()-i-1]-'0';
288     }
289     if (!in) obj = number();
290     return in;
291 }
292 
293 ostream & operator<< (ostream &out, number &obj)
294 {
295     if(obj.fu) cout<<"-";
296         bool flag=0;
297         for(int i=obj.len;i>0;i--){
298             if(obj.num[i]) flag=1;
299             if(obj.num[i]>9) obj.carry_bit(); 
300             if(flag) out<<obj.num[i]; 
301         }
302         out<<obj.num[0];
303     return out;
304 }
305 
306 
307 number gcd_rec(number a,number b){
308     if(b.judge_zero()) return a;
309     return gcd_rec(b,a-b);
310 }
311 
312 number gcd(number a,number b){
313     if(a.judge_zero()) return a;
314     number t;
315     for(;;t=b,b=a-b,a=t)
316         if(b.judge_zero()) return a;
317     return a;
318 }
319 
320 number power(number a,number n){
321     number zero;
322     number c;c=1;
323     for(;n>zero;n.division2(),a*=a) if(n.odd()) c*=a;
324     return c;
325 }
326 
327 int main()
328 {
329     freopen("gcd.in","r",stdin);
330     freopen("gcd.out","w",stdout);
331     number a,b,c;
332     cin>>a>>b;
333     c=gcd(a,b);
334     cout<<c;
335     return 0;
336 }

折柳的高精度模板Code

更新日志

其实我是在写了300行以后才来写这篇博客的，所以之前的时间点就不计了吧！

（2019-11-05ago）

加法

进位

构造

比较

减法

退位

递归求gcd

非递归gcd

乘法

阶乘

iostream

除以2

判断奇偶

快速幂

……

细节实现

相信这里有许多我（以前）不会的c++语言用法吧。我把它们都记录下来了呢！

构造函数

当我们定义一个number时，由于可能是局部变量，我们就要先将其赋初值

但是number不是int，不是double，要是我们要赋初值的话，还得将其所有的变量（even arraies！）赋初值！

所以我为了在使用number时方便，在网上找了个东西叫做构造函数

函数与结构体（或类，一下省略）同名，没有返回值（不是void！）

在新定义一个number时会自动调用

作用大概就是赋初值吧

（PS：还有个函数叫析构函数，用于释放结构体内存时操作（例如：删除指针等），有兴趣可以去看看）

number(){
    len=fu=0;
    memset(num,0,sizeof(num));
}

但要是我们要给一个number赋初值怎么办？

一个即将退役的老OIer告诉我，再来一个构造函数，但是它是要传参的呗！

但是，由于我不会用，只好重载的=（赋值运算符）来赋初值。

number operator= (int x){//隐式转换（？） 
    fu=(x<0);
    num[0]=abs(x);
    if(x>9) carry_bit();
    if(x<-9) back_space();
    return *this;
}

也许以后我就会用了吧！

重载前缀自增自减运算符

本来我想到了自增自减有前缀和后缀之分，但是不知道该怎么打……

所以就先打了个不知道是哪种的operator+

number operator++ (){
    num[0]++;
    if(num[0]>9) carry_bit();
    return *this;
}

结果发现只有前缀才能用。

那么后缀的该怎么打呢？

重载后缀自增自减运算符

几番查找后，终于在《C++ Primer Plus》里面找到了

只要在（）里加一个int即可

（原理不知）

number operator++ (int){
    number save=*this;
    ++*this;
    return save;
}

这里我甚至还偷懒地在后缀里用了前缀……本来就没错嘛！

重载赋值运算符(int转num高精度)

见构造函数末尾部分

number operator= (int x){//隐式转换 
    fu=(x<0);
    num[0]=abs(x);
    if(x>9) carry_bit();
    if(x<-9) back_space();
    return *this;
}

重载输入输出流运算符(友元)

首先我为了输入输出各自写了一个成员函数

void input(){
    string a;
    cin>>a;
    if(a[0]=='-'){
        fu=1;
        len=a.size()-1;
        for(unsigned int i=0;i<a.size()-1;i++) num[i]=a[a.size()-i-1]-'0';
    }
    else{
        len=a.size();
        for(unsigned int i=0;i<a.size();i++)    num[i]=a[a.size()-i-1]-'0';
    }
}

void output(){
    if(fu) cout<<"-";
    bool flag=0;
    for(int i=len;i>0;i--){
        if(num[i]) flag=1;
        if(num[i]>9) carry_bit(); 
        if(flag) putchar(num[i]+'0');//putchar加速 
    }
    putchar(num[0]+'0');
}

后来，我想：看看人家STL-string，都可以直接拿cin cout输入输出了，你怎么就不可以做到呢？

我又去网上，书中找了找怎么重载流运算符……

不想讲了，就是套模板，把之前写的那个input和output套进去就可以了嘛！

But，由于stream是一个已经封装好了的类，你也不能修改头文件中的内容，怎么办呢？

answer：用友元！它可以“打入敌人内部”进行一些操作！

友元函数声明（要放在结构体中！）

friend istream & operator>> (istream &in, number &obj);    
friend ostream & operator<< (ostream &out, number &obj);

即在正常的函数前加上friend即可

友元函数定义（要放在全局中！）

istream & operator>> (istream &in, number &obj)
{
    string a;
    in>>a;
    if(a[0]=='-'){
        obj.fu=1;
        obj.len=a.size()-1;
        for(unsigned int i=0;i<a.size()-1;i++) obj.num[i]=a[a.size()-i-1]-'0';
    }
    else{
        obj.len=a.size();
        for(unsigned int i=0;i<a.size();i++) obj.num[i]=a[a.size()-i-1]-'0';
    }
    if (!in) obj = number();
    return in;
}

ostream & operator<< (ostream &out, number &obj)
{
    if(obj.fu) cout<<"-";
        bool flag=0;
        for(int i=obj.len;i>0;i--){
            if(obj.num[i]) flag=1;
            if(obj.num[i]>9) obj.carry_bit(); 
            if(flag) out<<obj.num[i]; 
        }
        out<<obj.num[0];
    return out;
}

重载判断符运算符

那么多比较函数，我一下子那写的过来呢？

本来我都是没有operator这些比较运算符的，只用了一个int compare(number)就好了

PS：为什么返回值不是bool而是int呢？因为返回的信息可能不只有大于，小于，还会有等于呀！

int compare(number x){//2=    1> 0<
    if(fu^x.fu){
        if(fu) return 0; 
        else return 1;
    }
    for(int i=max(len,x.len);i>=0;i--)
    {
        if(num[i]>x.num[i]) return !fu;//大于 (1)
        if(num[i]<x.num[i]) return fu;//小于 (0)
    }
    return 2;//相等 
}

后来，我觉得这样十分的不直观，而且有时容易错，还是个成员函数，调用时是a.compare(b)这样的形式的……

所以我就把"<",">","<=",">=","==","!="都重载了！

Impression

现在的长度是有限的而且在枚举时也可能会有大量时间浪费

尽管已经引进了len和updata_len()，但是这两个玩意的作用还是较小，用法比较麻烦

希望能像STL的某些容器那样可自动改变大小，已经O(1)就可以知道number的位数

不知道为什么，一个number表达式不可以用cout<<输出？

就像

a,b为number时，cout<<(a+b);不可以；

但是

a,b为int时，cout<<(a+b);可以！

是因为operator<< 里的参数obj为引用吗？

除法（二分）

这个玩意还有存在许多许多可以更新&改进的地方，欢迎提建议！