探寻C/C++中更快的大数(自然数集)模板 - c++编程基础

本文系fcbruce个人原创整理，转载请注明出处http://blog.csdn.net/u012965890/article/details/40432511，谢谢！

我们知道在C/C++中int型可处理-2^31~2^31-1(32位及以上编译器)，long long型可处理-2^63~2^63-1的数据,这实际上是非常有限的，在很多情况下，我们往往会处理范围更大的数据。Java中有BigInteger类，python中想要多大就有多大（取决于内存），但是C/C++就显得有些乏力，这时候我们会手写大数类，用一个数组记录一个数，来模拟竖式计算。通常我们会一位一位地储存数据，这样易于实现，逻辑清晰，方便理解，但是一定程度上牺牲了效率，浪费了资源，那么能否多位存储数据并操作呢，显然是可以的。

我们知道int类型能表示的最大数量级为10^9左右，为了避免乘法溢出，我们不妨用一个int存储4位数字(10^4)，可以轻易写下如下代码（仅含加、减、乘和比较操作）：

/*
 *
 * Author : fcbruce 
  
   
 *
 * Time : Fri 24 Oct 2014 02:43:41 PM CST
 *
 */
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                
                  #include 
                  #include 
                  
                    #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #ifdef _WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define maxm #define maxn using namespace std; const int maxl = 233; struct bign { static int width; static int mod; int len,s[maxl]; bign() { memset(s,0,sizeof s); len=1; } bign(int num) { *this=num; } bign(long long num) { *this=num; } bign(const char *s) { *this=s; } bign operator = (int num) { char s[maxl]; sprintf(s,"%d",num); *this=s; return *this; } bign operator = (long long num) { char s[maxl]; sprintf(s,lld,num); *this=s; return *this; } bign operator = (const char *s) { int l=strlen(s); len=0; for (int i=l-1;i>=0;i-=width,len++) { (*this).s[len]=0; for (int j=max(0,i-width+1);j<=i;j++) (*this).s[len]=(*this).s[len]*10+s[j]-'0'; } return *this; } void str(char *s) { char format[5]; sprintf(format,"%%0%dd",width); for (int i=len-1,j=0;i>=0;i--,j++) sprintf(s+j*width,format,(*this).s[i]); int j=0; while (s[j]=='0' && s[j+1]!='\0') j++; strcpy(s,s+j); } bign operator + (const bign &b)const { bign c; c.len=0; for (int i=0,g=0;g || i
                   
                    1 && s[len-1]==0) len--; } bign operator * (const bign &b) { bign c;c.len=len+b.len; for (int i=0;i
                    
                     =0) g=0; else { g=1; x+=mod; } c.s[c.len++]=x; } c.clean(); return c; } bool operator < (const bign &b)const { if (len!=b.len) return len
                     
                       (const bign &b)const { return b<*this; } bool operator <= (const bign &b)const { return !(b>*this); } bool operator >= (const bign &b)const { return !(b<*this); } bool operator == (const bign &b)const { if (len!=b.len) return false; for (int i=0;i
                      
                       
 其中void str(char *)函数为将该大数转换成字符串。 
                       





 
                       
  
                       随机生成100000组10^82数量级以下的数据并进行对拍，没有发现错误。 
                       
  
                       long long能表示的数据范围更大，能压更多的位数，会不会更快呢？不妨一次压8位，对以上代码稍加改动即可 
                        
                       /*
 *
 * Author : fcbruce 
                        
                         
 *
 * Time : Fri 24 Oct 2014 02:43:41 PM CST
 *
 */
#include 
                         
                           #include 
                          
                            #include 
                           
                             #include 
                            
                              #include 
                             
                               #include 
                              
                                #include 
                               
                                 #include 
                                
                                  #include 
                                 
                                   #include 
                                  
                                    #include 
                                   
                                     #include 
                                    
                                      #include 
                                     
                                       #include 
                                      
                                        #include 
                                        #include 
                                        
                                          #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #ifdef _WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define maxm #define maxn using namespace std; const int maxl = 233; struct bign { static int width; static long long mod; int len; long long s[maxl]; bign() { memset(s,0,sizeof s); len=1; } bign(int num) { *this=num; } bign(long long num) { *this=num; } bign(const char *s) { *this=s; } bign operator = (int num) { char s[maxl]; sprintf(s,"%d",num); *this=s; return *this; } bign operator = (long long num) { char s[maxl]; sprintf(s,lld,num); *this=s; return *this; } bign operator = (const char *s) { int l=strlen(s); len=0; for (int i=l-1;i>=0;i-=width,len++) { (*this).s[len]=0; for (int j=max(0,i-width+1);j<=i;j++) (*this).s[len]=(*this).s[len]*10+s[j]-'0'; } return *this; } void str(char *s) { char format[10]; sprintf(format,"%%0%d%s",width,lld+1); for (int i=len-1,j=0;i>=0;i--,j++) sprintf(s+j*width,format,(*this).s[i]); int j=0; while (s[j]=='0' && s[j+1]!='\0') j++; strcpy(s,s+j); } bign operator + (const bign &b)const { bign c; c.len=0; long long g=0ll; for (int i=0;g!=0ll || i
                                         
                                          1 && s[len-1]==0) len--; } bi

探寻C/C++中更快的大数(自然数集)模板(一)