BigInteger(大整数)

电玩女神 2022-05-24 12:59 166阅读 0赞

# BigInteger(大整数) #

*  BigInteger(大整数)
    
     *  实现的功能
     *  实现原理
        
         *  储存
         *  加法
         *  乘法
         *  负数
     *  完整代码

## 实现的功能 ##

*  负数
 *  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`

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

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

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

### 负数 ###

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

如`-5445843685798 + 7842365473734 = 2396521787936`

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

最后一段为负值, 其余段都是正数, 但是结果是正确的. 只需要把`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]));
        }
    }