BigInteger(大整数)

[TOC]

实现的功能

• 负数

• vector动态分配内存

• 普通整数long long, int, 字符串string赋值

• 加法

• 乘法

• 重载了+,+=, *, =,-,==, >, <

实现原理

储存

把一个整数每四位分解成一段保存到vector中, 如把7842365473734分解成3734 6547 8423 7保存

加法

把每一段分别相加, 然后把超过10000的部分加到vector下一个元素中

    for (int i = 0,x = 0; x != 0 || i < s.size() || i < b.s.size(); ++i) {
        if (i < s.size()) x += s[i];
        if (i < b.s.size()) x += b.s[i];
        c.s.push_back(x % BASE);
        x /= BASE;
    }

乘法

和列竖式做乘法类似, 每段分别交叉相乘

假如BASE = 100, 计算1234 * 3421, 每段保存2位, 结果不会超过8位, 所有最多需要四段保存

设A = 1234, B = 3421, C = A * B

	1	0
A	12	34
B	34	21

	3	2	1	0
			B[0] * A[1]	B[0] * A[0]
		B[1] * A[1]	B[1] * A[0]
		408	252 + 1156	714
C	4	22	15	14

类似竖式乘法, 超过BASE需要进位(多出的保存到下一个元素)

所以如果用int来保存每段数据, 要保证相乘再相加的结果依然在int范围中.

sqrt[(2 ^ 31 - 1) / 2] =32767, 所以我把BASE设为10000不会超过范围

负数

一个正整数加一个负整数可能会出现有分段为负数有分段为正数的情况

如-5445843685798 + 7842365473734 = 2396521787936

按照加法函数的运算结果为

3	2	1	0
2	3965	2179	-2064

最后一段为负值, 其余段都是正数, 但是结果是正确的. 只需要把1位置上退一位给0即可, 也就是1位置上的值变为2178, 0位置上的值变为10000 - 2064 = 7936

按照上述思路我们可以写个maintain函数来维护各段的值符号相同

只需要在输出的时候调用, 因为即使符合不同, 保存的值本质上还是相同的

    void maintain() {
        if (s[s.size() - 1] > 0)
            for (int i = 0; i < s.size() - 1; ++i)
                if (s[i] >= 0) continue;
                else {
                    s[i + 1]--;
                    s[i] += BASE;
                }
        else
            for (int i = 0; i < s.size() - 1; ++i)
                if (s[i] <= 0) continue;
                else {
                    s[i + 1]++;
                    s[i] -= BASE;
                }
    }

完整代码

struct BigInteger {
    static const int BASE = 10000;
    static const int WIDTH = 4;
    vector<int> s;

    BigInteger(int num) { *this = num; }

    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(string str) {
        *this = str;
    }

    BigInteger(const char s[]) {
        string str(s);
        *this = str;
    }

    BigInteger operator=(const string &str) {
        s.clear();
        int sign = 1;
        int length = str.length();
        int left = 0;//记录数字的开始结束位置
        int right = length;
        if (str.at(0) == '-') {
            sign = -1;
            length--;
            left++;
        }
        int n = (length - 1) / WIDTH + 1;//vector数目
        for (int i = 0; i < n; ++i) {
            int end = right - i * WIDTH;
            int start = max(left, end - WIDTH);
            int x;
            sscanf(str.substr(start, end - start).c_str(), "%d", &x);
            s.push_back(x * sign);
        }
        return *this;
    }

    BigInteger operator+(const BigInteger &b) const {
        BigInteger c;
        c.s.clear();
        for (int i = 0, x = 0; x != 0 || i < s.size() || i < b.s.size(); ++i) {
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x += b.s[i];
            c.s.push_back(x % BASE);
            x /= BASE;//需要进位的部分
        }
        return c;
    }

    BigInteger operator-(const BigInteger &b) const {
        BigInteger c;
        c.s.clear();
        for (int i = 0, x = 0; x != 0 || i < s.size() || i < b.s.size(); ++i) {
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x -= b.s[i];
            c.s.push_back(x % BASE);
            x /= BASE;//需要进位的部分
        }
        c.clean();
        return c;
    }


    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) {
        if (b.s.size() != s.size()) return false;
        for (int i = s.size() - 1; i >= 0; i--)
            if (s[i] != b.s[i]) return false;
        return true;
    }

    bool operator>(const BigInteger &b) {
        if (s.front() > 0 && b.s.front() <= 0) return true;
        else if (s.front() < 0 && b.s.front() >= 0) return false;
        return (*this - b).s.front() > 0;
    }

    bool operator<(const BigInteger &b) {
        if (s.front() > 0 && b.s.front() <= 0) return false;
        else if (s.front() < 0 && b.s.front() >= 0) return true;
        return (*this - b).s.front() < 0;
    }

    BigInteger operator*(const BigInteger &b) const {
        BigInteger res;
        res.s.resize(s.size() + b.s.size());
        for (int i = 0; i < b.s.size(); ++i)
            for (int j = 0; j < s.size(); ++j)
                res.s[i + j] += b.s[i] * s[j];
        //进位
        for (int i = 0; i < res.s.size() - 1; ++i) {
            res.s[i + 1] += res.s[i] / BASE;
            res.s[i] %= BASE;
        }
        //最后的一段上可能没有值, 所以需要pop
//        if (res.s[res.s.size() - 1] == 0)
//            res.s.pop_back();
        res.clean();
        return res;
    }

    void clean() {
        int i = s.size();
        while (s[--i] == 0)
            s.pop_back();
    }

    void maintain() {
        //一个数的符号仅由它的最前面一段决定, 也就是vector中最后的元素
        if (s[s.size() - 1] > 0)
            for (int i = 0; i < s.size() - 1; ++i)
                if (s[i] >= 0) continue;
                else {
                    s[i + 1]--;//后面位置小于0, 需要前面位置退位
                    s[i] += BASE;
                }
        else
            for (int i = 0; i < s.size() - 1; ++i)
                if (s[i] <= 0) continue;
                else {
                    s[i + 1]++;
                    s[i] -= BASE;
                }
    }

    void print() {
        maintain();
        printf("%d", s[s.size() - 1]);
        for (int i = s.size() - 2; i >= 0; i--)
            //负数只需要输出第一段的符号即可, 后面没有满4位的应该用0补到4位
            printf("%04d", abs(s[i]));
    }
}