【原创】高精度(压位储存)模板

  1 /*
  2 高精度(压位储存) 
  3 */
  4 #include <cstdlib>
  5 #include <iostream>
  6 #include <cstdio>
  7 #include <cstring>
  8 #include <cmath>
  9 const int MAX=10005;//最长长度 
 10 using namespace std;
 11 //高精度结构体,先声明后实现 
 12 struct hp
 13 {
 14        //注意，这里用num[0]来保存位数
 15        int num[MAX]; 
 16        
 17        //-------赋值与初始化-------//
 18        hp() {}
 19        hp & operator =(const char*);//从字符串赋值 
 20        hp & operator =(int);//从整型赋值 
 21        hp (int);
 22        
 23        //-------普通运算符-------//
 24        hp operator + (const hp &) const;
 25        hp operator - (const hp &) const;
 26        hp operator * (const hp &) const;
 27        hp operator / (const hp &) const;//注意后面两个的实现 
 28        hp operator % (const hp &) const;
 29        
 30        //-------比较运算符-------//
 31        bool operator > (const hp &) const;
 32        bool operator < (const hp &) const;
 33        bool operator == (const hp &) const;
 34        bool operator >= (const hp &) const;
 35        bool operator <= (const hp &) const;
 36        
 37 }shu;
 38 //-------实现-------//
 39 hp & hp::operator =(const char* str)
 40 {
 41      memset(num,0,sizeof(num));
 42      int len=strlen(str),j=1,k=1;
 43      for (int i=1;i<=len;i++)//注意从1开始循环 
 44      {
 45          if (k==10000) j++,k=1;            
 46          num[j]+=k*(str[len-i]-‘0‘);
 47          k*=10;
 48      }
 49      num[0]=j;
 50      return *this;
 51 }
 52 hp & hp::operator =(int a) 
 53 {
 54      char s[MAX];
 55      sprintf(s,"%d",a);
 56      return *this=s;
 57 }
 58 hp::hp(int n){*this=n;}
 59 hp hp::operator +(const hp & t)const
 60 {
 61      hp c;
 62      memset(c.num,0,sizeof(c.num));
 63      c.num[0]=max(num[0],t.num[0]);
 64      for (int i=1;i<=c.num[0];i++)
 65      {
 66          c.num[i]=num[i]+t.num[i]; 
 67          if (c.num[i]>=10000){
 68              c.num[i+1]++;
 69              c.num[i]-=10000;
 70          }
 71      }
 72      while (c.num[c.num[0]+1]>0) c.num[0]++;
 73      return c; 
 74 }
 75 hp hp::operator -(const hp & t)const
 76 {
 77      hp c;
 78      memset(c.num,0,sizeof(c.num));
 79      c.num[0]=num[0];
 80      for (int i=1;i<=c.num[0];i++)
 81      {
 82          c.num[i]+=num[i]-t.num[i];
 83          if (c.num[i]<0){
 84              c.num[i+1]--;
 85              c.num[i]+=10000;
 86          }
 87      }
 88      while (c.num[c.num[0]]==0 && c.num[0]>1) c.num[0]--;
 89      return c; 
 90 }
 91 hp hp::operator *(const hp & t)const
 92 {
 93      hp c;
 94      memset(c.num,0,sizeof(c.num));
 95      c.num[0]=num[0]+t.num[0]+1;//位数 
 96      for (int i=1;i<=num[0];i++)
 97      for (int j=1;j<=t.num[0];j++)
 98      {
 99          c.num[i+j-1]=num[i]*t.num[j];
100          c.num[i+j]+=c.num[i+j-1]/10000;
101          c.num[i+j]%=10000;
102      }
103      while (c.num[c.num[0]]==0 && c.num[0]>1) c.num[0]--;
104      return c;
105 } 
106 bool hp::operator > (const hp &b) const
107 {
108     if (num[0]!=b.num[0]) return num[0]>b.num[0];
109     for (int i=num[0];i>=1;i--)
110         if (num[i]!=b.num[i])
111             return (num[i]>b.num[i]);
112     return false;
113 }
114 bool hp::operator < (const hp &b) const {return b>*this;}
115 bool hp::operator <= (const hp &b) const {return !(*this>b);}
116 bool hp::operator >= (const hp &b) const {return !(b>*this);}
117 bool hp::operator == (const hp &b) const {return !(b>*this)&&!(*this>b);}
118 hp hp::operator /(const hp & b)const//二分除法 
119 {
120     hp c, d;
121     c.num[0]=num[0]+b.num[0]+1;
122     d.num[0]=0;//d用来存储余数 
123     for (int i=num[0];i>=1;i--)
124     {
125         memmove(d.num+2,d.num+1,sizeof(d.num)-sizeof(int)*2);
126         d.num[0]++;
127         d.num[1]=num[i];
128 
129         int left=0,right=9999,mid;
130         while (left<right)
131         {
132             mid =(left+right)/2;
133             if (b*hp(mid)<=d) left=mid+1;
134             else right=mid;
135         }
136         c.num[i]=right-1;
137         d=d-b*hp(right-1);
138     }
139     while (c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--;
140     return c;            
141 }