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;
}