STL应用：大整数类

╰半夏微凉° 2022-11-27 12:19 103阅读 0赞

### 大整数类BigInteger ###

结构体BigInteger可用于存储高精度非负整数

struct BigInteger
    { 
        static const int BASE =100000000;
        static const int WIDTH =8;
        vector<int> s;
        BigInteger(long long num=0){ *this = num;} //构造函数
        BigInteger operator=(long long num)
        { 
      	s.clear();
      	do{ 
      		s.push_back(num%BASE);
       		num/=BASE;
            }while(num>0);
            return *this;
        }
        BigInteger operator=(const string& str) //赋值运算符 
        { 
      	s.clear();
     	int x,len=(str.length()-1)/WIDTH+1;
      	for(int i=0;i<len;i++)
      	{ 
                int end=str.length()-i*WIDTH;
                int start=max(0,end-WIDTH);
                sscanf(str.substr(start,end-start).c_str(),"%d",&x);
                s.push_back(x);
            } 
         return *this;
         } 
    };

s用来保存大整数的各个数位。例如，要表示1234，则s=\{4,3,2,1)。用vector而非数组保存数字。

ostream& operator << (ostream &out,const BigInteger& x)
    { 
        out<<x.s.back();
        for(int i=x.s.size()-2;i>=0;i--)
        { 
      	char buf[20];
      	sprintf(buf,"%08d",x.s[i]);
        }
        return out;
    }
    istream& operator >> (istream &in,BigInteger& x)
    { 
        string s;
        if(!(in>>s))
        { 
      	return in;
        }
        x=s;
        return in;
    }

这样，可以用cin>>x和cout<<x的方式进行输入输出。  
注：  
static const int BASE=100000000,作用是一个"属于BigInteger"的常数，不属于任何BigInteger类型的结构体变量，而属于BigInteger这个类型，因此称为静态变量成员，在声明时需加static修饰符。在其他地方使用时需要写成BigInteger::BASE。

### 四则运算 ###

高精度类非常常见（定义在结构体内部）

BigInteger operator + (const BigInteger& b) const
    { 
        BigInteger c;
        c.s.clear();
        for(int i=0,g=0;;i++)
        { 
      	if(g==0&&i>=s.size()&&i>=b.s.size())
      	{ 
                break;
      	}
      	int x=g;
      	if(i<s.size())
      	{ 
                x+=s[i];
      	}
      	if(i<b.s.size())
      	{ 
                x+=b.s[i];
      	}
      	c.s.push_back(x%BASE);
      	g=x/BASE;
        }
        return c;
    }

为了让使用更加简单，还可以重定义"+="运算符（定义在结构体内部）：

BigInteger operator +=(const BigInteger& b)
    { 
       *this = *this+b;
       return *this;
    }

### 比较运算符 ###

下面实现比较操作（定义在结构体内部）：

bool operator<(const BigInteger& b) const
    { 
        if(s.size()!=b.s.size())
        { 
      	return s.size()<b.size();
        }
        for(int i=s.size()-1;i>=0;i--)
        { 
      	if(s[i]!=b.s[i])
      	{ 
                return s[i]<b.s[i];
      	}
        }
        return false; //相等 
    }

**一开始就比较两个BigInteger的位数，不相等则直接返回，否则直接从后往前比较（因为低位在vector前面）。前提是两个数都没有前导零，否则会出错。**  
只需定义“小于”这一符号，即可用它定义其他所有比较运算符（对于BigInteger这个例子，“”可直接定义为sb.s,不过不具一般性。）：

bool operator > (const BigInteger& b) const{  return b<*this;}
    bool operator <= (const BigInteger& b) const{  return !(b<*this;}
    bool operator >= (const BigInteger& b) const{  return !(*this<b);}
    bool operator != (const BigInteger& b) const{  return b<*this||*this<b;}
    bool operator == (const BigInteger& b) const{  return !(b<*this)&&!(*this<b);}