c/c++语言开发共享C++高精度模板代码分析

0x01紫书风格

  #include <algorithm> // max  #include <cassert>   // assert  #include <cstdio>    // printf,sprintf  #include <cstring>   // strlen  #include <iostream>  // cin,cout  #include <string>    // string类  #include <vector>    // vector类  using namespace std;    struct biginteger {      typedef unsigned long long ll;        static const int base = 100000000;      static const int width = 8;      vector<int> s;        biginteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;}      biginteger(ll num = 0) {*this = num;}      biginteger(string s) {*this = s;}      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).clean();      }        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) const {          assert(b <= *this); // 减数不能大于被减数          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 = s[i] + g;              if (i < b.s.size()) x -= b.s[i];              if (x < 0) {g = -1; x += base;} else g = 0;              c.s.push_back(x);          }          return c.clean();      }      biginteger operator * (const biginteger& b) const {          int i, j; ll g;          vector<ll> v(s.size()+b.s.size(), 0);          biginteger c; c.s.clear();          for(i=0;i<s.size();i++) for(j=0;j<b.s.size();j++) v[i+j]+=ll(s[i])*b.s[j];          for (i = 0, g = 0; ; i++) {              if (g ==0 && i >= v.size()) break;              ll x = v[i] + g;              c.s.push_back(x % base);              g = x / base;          }          return c.clean();      }      biginteger operator / (const biginteger& b) const {          assert(b > 0);  // 除数必须大于0          biginteger c = *this;       // 商:主要是让c.s和(*this).s的vector一样大          biginteger m;               // 余数:初始化为0          for (int i = s.size()-1; i >= 0; i--) {              m = m*base + s[i];              c.s[i] = bsearch(b, m);              m -= b*c.s[i];          }          return c.clean();      }      biginteger operator % (const biginteger& b) const { //方法与除法相同          biginteger c = *this;          biginteger m;          for (int i = s.size()-1; i >= 0; i--) {              m = m*base + s[i];              c.s[i] = bsearch(b, m);              m -= b*c.s[i];          }          return m;      }      // 二分法找出满足bx<=m的最大的x      int bsearch(const biginteger& b, const biginteger& m) const{          int l = 0, r = base-1, x;          while (1) {              x = (l+r)>>1;              if (b*x<=m) {if (b*(x+1)>m) return x; else l = x;}              else r = x;          }      }      biginteger& operator += (const biginteger& b) {*this = *this + b; return *this;}      biginteger& operator -= (const biginteger& b) {*this = *this - b; return *this;}      biginteger& operator *= (const biginteger& b) {*this = *this * b; return *this;}      biginteger& operator /= (const biginteger& b) {*this = *this / b; return *this;}      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.s.size();          for (int i = s.size()-1; i >= 0; i--)              if (s[i] != b.s[i]) return s[i] < b.s[i];          return false;      }      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) && !(b > *this);}  };    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]);          for (int j = 0; j < strlen(buf); j++) out << buf[j];      }      return out;  }    istream& operator >> (istream& in, biginteger& x) {      string s;      if (!(in >> s)) return in;      x = s;      return in;  }