C++ BigInteger类实现

发布于 2021-06-03  1909 次阅读


    这学期太忙了,一直没写什么东西(什么都没有学),等放假慢慢写点。今天刚好写到一个需要高精度的题,之前的高精度都是写了用完就扔,所以心血来潮打算直接完成一个高精度类,顺便练练运算符重载。
    此类不限数字位数大小,支持cin与cout的单实例输入输出;支持加法与乘法以及+=和*=;支持所有逻辑比较运算;可以使用string,char数组或者long long及以下的整数初始化;=赋值和初始化等效,同样可以使用string、char和整数。

class BigInteger {
    vector<int> bits;
public:
    friend istream& operator >> (istream& BigIn, BigInteger& x) {
        string num;
        BigIn >> num;
        x = num;
        return BigIn;
    }
    friend ostream& operator << (ostream& BigOut, BigInteger x) {
        for (auto it = x.bits.rbegin(); it != x.bits.rend(); ++it)
            BigOut << *it;
        return BigOut;
    }
    void operator=(const BigInteger& x)
    {
        this->bits.assign(x.bits.begin(), x.bits.end());
    }
    void operator=(string& s)
    {
        this->bits.clear();
        for (auto it = s.rbegin(); it != s.rend(); ++it)
            bits.emplace_back(*it - '0');
        while (bits.size() && bits.back() == 0)
            bits.pop_back();
    }
    void operator=(char* s)
    {
        this->bits.clear();
        for (int i = strlen(s) - 1; i >= 0; --i)
            bits.emplace_back(s[i] - '0');
        while (bits.size() && bits.back() == 0)
            bits.pop_back();
    }
    void operator=(long long x)
    {
        this->bits.clear();
        while (x)
            bits.emplace_back(x % 10), x /= 10;
        while (bits.size()&&bits.back() == 0)
            bits.pop_back();
    }
    bool operator>(const BigInteger& x)const
    {
        if (this->bits.size() != x.bits.size())
            return this->bits.size() > x.bits.size();
        else
        {
            for (int i = this->bits.size() - 1; i >= 0; --i)
                if (this->bits[i] != x.bits[i])
                    return this->bits[i] > x.bits[i];
            return 0;
        }
    }
    bool operator==(const BigInteger& x)const
    {
        if (this->bits.size() != x.bits.size())
            return 0;
        else
        {
            for (int i = 0; i < x.bits.size(); ++i)
                if (this->bits[i] != x.bits[i])
                    return 0;
            return 1;
        }
    }
    bool operator<(const BigInteger& x)const
    {
        if (this->bits.size() != x.bits.size())
            return this->bits.size() < x.bits.size();
        else
        {
            for (int i = this->bits.size() - 1; i >= 0; --i)
                if (this->bits[i] != x.bits[i])
                    return this->bits[i] < x.bits[i];
            return 0;
        }
    }
    bool operator>=(const BigInteger& x)const
    {
        return *this > x || *this == x;
    }
    bool operator<=(const BigInteger& x)const
    {
        return *this < x || *this == x;
    }
    bool operator!=(const BigInteger& x)const
    {
        return !(*this == x);
    }
    BigInteger operator+(const BigInteger& x)const
    {
        BigInteger newNum(*this);
        int minSize = min(this->bits.size(), x.bits.size());
        for (int i = 0; i < minSize; ++i)
        {
            newNum.bits[i] += x.bits[i];
            if (newNum.bits[i] >= 10 && i == newNum.bits.size() - 1)
                newNum.bits.emplace_back(newNum.bits[i] / 10), newNum.bits[i] %= 10;
            else if (newNum.bits[i] >= 10)
                newNum.bits[i + 1] += newNum.bits[i] / 10, newNum.bits[i] %= 10;
        }
        return newNum;
    }
    void operator+=(const BigInteger& x) { *this = *this + x; }

    BigInteger operator*(const BigInteger& x)const
    {
        BigInteger newNum;
        newNum.bits.resize(this->bits.size() + x.bits.size(), 0);
        for (int i = 0; i < this->bits.size(); ++i)
            for (int j = 0; j < x.bits.size(); ++j)
            {
                int k = i + j;
                if (k >= newNum.bits.size())
                    newNum.bits.emplace_back(this->bits[i] * x.bits[j]);
                else
                    newNum.bits[k] += this->bits[i] * x.bits[j];
                if (newNum.bits[k] >= 10 && k == newNum.bits.size() - 1)
                    newNum.bits.emplace_back(newNum.bits[k] / 10), newNum.bits[k] %= 10;
                else if (newNum.bits[k] >= 10)
                    newNum.bits[k + 1] += newNum.bits[k] / 10, newNum.bits[k] %= 10;
            }
        while (newNum.bits.size()&&newNum.bits.back() == 0)
            newNum.bits.pop_back();
        return newNum;
    }
    void operator*=(const BigInteger& x) { *this = *this * x; }
    int getBit(int i){return bits[i];}
    int getLen() { return bits.size(); }

    BigInteger() {}
    BigInteger(const BigInteger& x)
    {
        this->bits.assign(x.bits.begin(), x.bits.end());
    }
    BigInteger(string s)
    {
        for (auto it = s.rbegin(); it != s.rend(); ++it)
            bits.emplace_back(*it - '0');
        while (bits.size() && bits.back() == 0)
            bits.pop_back();
    }
    BigInteger(char* s)
    {
        for (int i = strlen(s) - 1; i >= 0; --i)
            bits.emplace_back(s[i] - '0');
        while (bits.size() && bits.back() == 0)
            bits.pop_back();
    }
    BigInteger(long long x)
    {
        while (x)
            bits.emplace_back(x % 10), x /= 10;
        while (bits.size() && bits.back() == 0)
            bits.pop_back();
    }
    BigInteger(BigInteger& x, int l = -1, int r = -1) {
        if (l == -1 || r == -1)
            l = 0, r = x.bits.size();
        this->bits.clear();
        for (int i = l; i < r; ++i)
            this->bits.emplace_back(x.bits[i]);
    }
};
//以下为使用示例
/*
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    BigInteger x("12345679"), y(81);
    char s[] = "0012345679";
    x = s;
    //cin >> x >> y;
    cout << x << endl << y << endl << x + y << endl 
        << x * y << endl << (x > y) << (x == y) << (x < y);
    return 0;
}
*/

例如洛谷P1018乘积最大这道题,就可以使用此类稍微魔改一下后加上dfs直接A过。AC源码链接


华科菜鸡计科学生