C++建立大整数类头文件及源文件

总阅读量次

　　前段时间用Java的BigInteger类做了一道题，于是便萌生了自己用C++实现一个BigInteger类的想法，顺带了解并掌握其底层算法。
　　准备阶段，我查阅了一下Java的BigInteger类的源代码(毕竟是轮子)，嗯，只是看了一下，然后开工。

　　首先我们分析一下BigInteger类成员变量以及成员函数 :

成员变量

大整数数串（bigInteger）
大整数位数（length）
大整数的正负（signum）

成员函数

加法+
减法-
乘法*
除法/
取余%

下面，我们一步一步的实现…

第一步：建立头文件 BigInteger.h 声明 BigInteger类

　　这里我们用vector来存储大数，可以灵活的配置空间。

#ifndef BIGINTEGER_H_INCLUDED
#define BIGINTEGER_H_INCLUDED
#include<iostream>
#include<vector>
#include<string>
class BigInteger {
private:
    std::vector<int> bigInteger;        /* 保存大整数字串    */
    size_t length;                      /* 表示大整数长度    */
    int signum;                         /* 表示大整数正负 -1为负数 0表示数字0 1表示正数 */
public:
    // 构造函数
    BigInteger();                       /* 空无参构造函数    */
    BigInteger(const BigInteger &);     /* 拷贝构造函数      */
    BigInteger(const std::string &);    /* 字符串构造大整数  */
    // 成员函数
    friend std::ostream& operator<<(std::ostream&, BigInteger &);
    friend std::istream& operator>>(std::istream&, BigInteger &);
    void setLength(const int&);
    void setSignum(const int&);
    int getLength();
    int getSignum();
    bool operator==(const BigInteger &);
    bool operator>(const BigInteger &);
    void operator=(const BigInteger &);
    BigInteger operator+(const BigInteger &);
    BigInteger operator-(const BigInteger &);
    BigInteger operator*(const BigInteger &);
    BigInteger operator/(const BigInteger &);
    BigInteger operator%(const BigInteger &);
};
#endif // BIGINTEGER_H_INCLUDED

第二步：实现功能（这里只详解主要功能，其它略）

　　我们先来看两个常数：

const int LIMIT = 4;
const int CARRY = 1e4;

LIMIT是bigInteger (vector)每个元素存的整数的位数，因为vector每个元素都存一个范围为
-2^31 至2^31 - 1的整数，最大的数位数为9位，考虑到最大的4位数相乘,也只有8位，故不会溢出int，所以选择存储4位数。
而CARRY则是vector的每个元素的基数，到10000就进位。

1.加法

　　加法应该是最好实现的，只用从低位开始加，加完判断进位即可。
PS: 代码块可左右滑动

BigInteger BigInteger::operator+(const BigInteger &tmp)
{
    BigInteger t = *this, q = tmp;
    size_t len1, len2;
    if(t > q)  swap(t, q);                          /* 前面重载了 > 、= 和 == 运算符，选择位数多的加*/
    len1 = t.bigInteger.size();                     /* 位数少的，再更新它的属性。将其作为返回值。*/
    len2 = q.bigInteger.size();
    bool flag = false;
    for(size_t i = 0; i < len2; i++) {              /* 索引小的为低位，大的为高位        */
        if(i < len1)                                /* 防止越界            */
            q.bigInteger[i] += t.bigInteger[i];
        if(q.bigInteger[i] >= CARRY) {
            if(i == len2 - 1) {                      /* 最高位进位为q扩容并加入1 */
                q.bigInteger.push_back(1);           /* 进1                 */
                q.bigInteger[i] -= CARRY;
                flag = true;
            } else {                                /* 高位进位          */
                q.bigInteger[i + 1]++;
                q.bigInteger[i] -= CARRY;           /* 保存本位           */
            }
        }
    }
    if(flag) q.length++;                            /* 最高位有进位       */
    return q;
}

2.减法

　　虽然减法不能交换两个数的位置，但是交换后对结果处理一下符号也可以。所以如果被减数大于减数，则直接进行减法；
如果被减数小于减数，则交换它们的位置，再相减，并为结果添上负号。减的时候如果结果小于零，此时需要向高位借位。

BigInteger BigInteger::operator-(const BigInteger &tmp)
{
    BigInteger q = *this, t = tmp;
    size_t len1, len2;
    if(q == t) {                                    /*两数相等则直接返回0*/
        BigInteger r("0");
        return r;
    }
    if(q > t) {
        len1 = q.bigInteger.size();
        len2 = t.bigInteger.size();
        for(size_t i = 0; i < len1; i++) {
            if(i < len2)                            /*防止越界          */
                q.bigInteger[i] -= t.bigInteger[i];
            if(q.bigInteger[i] < 0) {               /* 本位所减的结果小于0则向高位借位 */
                q.bigInteger[i + 1]--;
                q.bigInteger[i] += CARRY;           /*  更新本位        */
            }
        }
        // 高位去0
        for(int i = len1 - 1; i >= 0; i--) {        /* 因为q的最高位 只能大于等于t的最高位，         */
            if(q.bigInteger[i] == 0) {              /* 当它们最高位相等时,此时最高位为0，用此算法    */
                q.length -= LIMIT;                  /* 把高位的0去掉                                 */
                q.bigInteger.pop_back();
            } else break;                           /* 从最高位开始扫描，遇到第一个不为0的数则跳出   */
        }
        // 更新大数的长度
        q.length = (q.bigInteger.size() - 1) * LIMIT;   /* 重新计算最高位的位数                   */
        int k = q.bigInteger.back();
        while(k) {                                  /*  计算位数        */
            k /= 10;
            q.length++;
        }
        return q;
    } else {
        len1 = t.bigInteger.size();
        len2 = q.bigInteger.size();
        for(size_t i = 0; i < len1; i++) {
            if(i < len2)
                t.bigInteger[i] -= q.bigInteger[i];
            if(t.bigInteger[i] < 0) {
                t.bigInteger[i + 1]--;
                t.bigInteger[i] += CARRY;
            }
        }
        // 大数符号
        t.signum = -1;                              /*  反过来减，结果为负数*/
        // 高位去0
        for(int i = len1 - 1; i >= 0; i--) {
            if(t.bigInteger[i] == 0) {
                t.length -= LIMIT;
                t.bigInteger.pop_back();
            } else break;
        }
        t.length = (t.bigInteger.size() - 1) * LIMIT;
        int k = t.bigInteger.back();
        while(k) {
            k /= 10;
            t.length++;
        }
        return t;
    }
}

加减只支持无符号大整数运算,因为在算的时候可以灵活的加括号与换符号

3.乘法

　　乘法依照竖式算法，被乘数的每一位和乘数的每一位相乘并将结果保存到相应的位置，且该相应位置应加上上一位的进位与本位值。

BigInteger BigInteger::operator*(const BigInteger &tmp)
{
    BigInteger t = *this, q = tmp, r;
    int carry;
    size_t i, j;
    size_t len1 = t.bigInteger.size(), len2 = q.bigInteger.size();
    vector<int> T(len1+len2, 0);
    for(i = 0; i < len1; i++) {
        carry = 0;
        for(j = 0; j < len2; j++) {
            int temp = t.bigInteger[i] * q.bigInteger[j] + T[i + j] + carry;  /* 保存第i位与第j位的乘积，并加上本位与进位值*/
            if(temp >= CARRY) {
                carry = temp / CARRY;                                         /* 保存进位值 */
                T[i + j] = temp - temp / CARRY * CARRY;                       /* 更新本位值 */
            } else {
                carry = 0;
                T[i + j] = temp;
            }
        }
        if(carry != 0) 
        T[i + j] = carry;                                      /* 最高位进位 */
    }
    // 处理符号
    if(t.signum < 0 && q.signum < 0)
        r.signum = 1;
    else {
        if(t.signum < 0 || q.signum < 0)
            q.signum = -1;
        else if(t.signum == 0 || q.signum == 0) {
            r.signum = 0;
        } else {
            r.signum = 1;
        }
    }
    // 处理长度
    if(r.signum != 0) {                                                      /* 先判断结果的符号 */
        //  高位去0
        for(int i = T.size() - 1; i >= 0; i--) {
            if(T[i] == 0) {
                T.pop_back();
            } else {
                break;
            }
        }
        // 数字串长度
        r.length = (T.size() - 1) * LIMIT;
        int k = T.back();
        while(k) {
            k /= 10;
            r.length++;
        }
        r.bigInteger = T;
    } else {
        r.length = 1;
        T.resize(1);
        r.bigInteger = T;
    }
    return r;
}

4.除法

　　判定大小，如果被除数等于除数，返回1；如果被除数小于除数，返回0；如果被除数大于除数，则进入除法，最简单的就是反复的做减法，看能减多少个除数。这里只介绍最基础的
法。还有一种将这种方法优化一些的算法，完整版见我的Github 明月光。

BigInteger BigInteger::operator/(const BigInteger &tmp)     // 最基础的算法，效率上可能有不足
{
    BigInteger q = *this , t = tmp, ans, ZERO("0");
    assert(!(t == ZERO));                       /* 除数不为0                */
    if(q == ZERO) return ZERO;                  /* 被除数为0返回0           */
    if(q == t) {                                /* 两数相等则直接返回1      */
        ans.signum = 1;
        ans.length = 1;
        ans.bigInteger.push_back(1);
    } else {
        if(q > t) {                             /* 被除数大于除数，开始整除 */
            vector<int> T(100, 0);
            int index = 0, maxl = 0;
            while(true) {
                q = q - t;
                if(ZERO > q) {
                    if(!(ZERO == q)) break;     /* 直到减到q小于零，当能整除的时候要将商加1 */
                }
                T[index]++;
                if(T[index] >= CARRY) {         /*判定进位              */
                    T[index] = 0;
                    T[++index]++;
                    maxl = max(maxl, index);
                    for(int i = index; i < maxl; i++) {
                        if(T[i] >= CARRY) {
                            T[i + 1]++;
                            T[i] = 0;
                        }
                    }
                    index = 0;                  /* 重回最低位累加      */
                }
            }
            T.resize(maxl + 1);                 /* 缩放空间             */
            if(q.signum < 0 && t.signum < 0)
                q.signum = 1;
            else {
                if(q.signum < 0 || t.signum < 0) 
                    q.signum = -1;
                else {
                    q.signum = 1;
                }
            }
            ans.bigInteger = T;
        } else {
            ans = ZERO;
        }
    }
    return ans;
}

5.取余

　　最简单的方法，代码如下2333333…

BigInteger BigInteger::operator%(const BigInteger &tmp)
{
    BigInteger q = *this, t = tmp, ZERO("0"), m;
    assert(!(q==ZERO));
    assert(!(t==ZERO));
    m = q / t;
    return q - (m * t);
}

　　这里还有另一种模拟取余的方法，

long long BigInteger::operator%(const long long &tmp)
{
    BigInteger q = *this;
    long long mod = 0, len = q.bigInteger.size();
    for(int i = len - 1; i >= 0; i--) {
        mod = ((mod * CARRY)%tmp + q.bigInteger[i]) % tmp;
    }
    return mod;
}

下面是一些测试:

开始测试
p:1234567890123456789
q:123456789012345678
p - q = 1111111101111111111
p + q = 1358024679135802467
p * q = 152415787532388366390794098763907942
p / q = 10
p % q = 9
p % 1234567890 = 123456789
结束测试

参考资料：

月之燃梦

完全属于自己的安静的一隅