利用数组实现500位C++大整数类

前言

C++中一直没有实现big integer类，而long long类型也仅仅占了8个字节，取值范围在-9223372036854775808～+9223372036854775807之间。所以，要实现比long long更大的整数类型，就必须自己造轮子。

一般来说，对于数据的保存有两种做法，一个是用字符串进行保存，一个是用一个数值数组进行保存。这里我用数值型数组进行保存。

（Q：为什么不用字符串存储呢？ A：因为这是我在C++课上遇到的一个附加思考题，我就完全按照题目要求来实现了，实际上我个人也觉得用数组更方便实现一点）

功能描述

利用int数组编写高精度运算类bign，完成大整数的运算。

类的数据成员有两个：一个是int型变量length，用来存储大数数据的有效长度；另一个是整型数组data，用来存储大整数（数组长度最大500）。（实际上，读者完全可以利用short数组或者unsigned char 数组保存值）

支持字符串赋值和整数赋值，了重载+ - * / += -= *= 、= >> << > < >= <= == !=运算符。

类的定义

class bign
{
private:
    //length存大整数的长度
    int length;
    //data存大整数的各个位置的值
    int data[500];  //下标0存个位数字，下标1存十位数字，以此类推

public:
    bign();
    void operator=(const string &); //利用字符串赋值
    void operator=(const int &); //利用int赋值
    bign &operator+=(const bign &);
    bign &operator-=(const bign &);
    bign &operator*=(const bign &);
    bign &operator/=(const bign &);
    bign operator+(const bign &);
    bign operator-(const bign &);
    bign operator*(const bign &);
    bign operator/(const bign &);
    bool operator>(const bign &);
    bool operator>=(const bign &);
    bool operator<(const bign &);
    bool operator<=(const bign &);
    friend bool operator==(const bign &, const bign &);
    friend bool operator!=(const bign &, const bign &);
    friend ostream &operator<<(ostream &, const bign &);
    friend istream &operator>>(istream &, bign &);
};

类的实现

无参构造函数

长度默认为0，data的值全部置0。

bign::bign()
{
    length = 0;
    for (int i = 0; i < 500; i++)
        data[i] = 0;
}

重载 = ，实现赋值

字符串为参数：

void bign::operator=(const string &str)
{
    length = str.length();
    int j = 0;
    for (int i = str.length() - 1; i >= 0; i--, j++)
        //字符在ASCII中以数值储存，'0'-'9',对应十进制数字48-57
        data[j] = str[i] - '0'; //-'0'的本质是-48，比如'9'-'0'本质是57-48，就转化为了数值9
    for (int i = str.length(); i < 500; i++)
        data[i] = 0;
}

int变量为参数：

void bign::operator=(const int &num)
{
    string str = to_string(num);
    operator=(str);
}

这里偷了个懒。

重载 << >> ，实现输入输出

istream &operator>>(istream &in, bign &bignum)
{
    string str;
    in >> str;
    bignum = str;
    return in;
}

ostream &operator<<(ostream &out, const bign &bignum)
{
    string s = "";
    for (int i = bignum.length - 1; i >= 0; i--)
        s += to_string(bignum.data[i]);
    out << s;
    return out;
}

重载 == 等，实现关系比较

bool operator==(const bign &n1, const bign &n2)
{
    if (n1.length != n2.length)
        return false;
    for (int i = 0; i < n1.length; i++)
        if (n1.data[i] != n2.data[i])
            return false;
    return true;
}

bool operator!=(const bign &n1, const bign &n2)
{
    return !(n1 == n2); //利用operator==()函数取反
}

bool bign::operator>(const bign &bignum)
{
    if (this->length > bignum.length)
        return true;
    else if (this->length < bignum.length)
        return false;
    for (int i = length; i > 0; i--)
        if (data[i] != bignum.data[i])
            return data[i] > bignum.data[i];
    return false;
}

bool bign::operator>=(const bign &bignum)
{
    if (this->length > bignum.length)
        return true;
    else if (this->length < bignum.length)
        return false;
    for (int i = length; i > 0; i--)
        if (data[i] != bignum.data[i])
            return data[i] > bignum.data[i];
    return true;
}

bool bign::operator<(const bign &bignum)
{
    return !(*this >= bignum); //利用operator>=()函数取反
}

bool bign::operator<=(const bign &bignum)
{
    return !(*this > bignum); //利用operator<()函数取反
}

重载 + ，实现大整数加法

大整数加法比较简单，利用carried变量记录进位，然后每一位相加即可。

bign bign::operator+(const bign &bignum)
{
    int longer_len = max(this->length, bignum.length);
    int carried = 0;
    bign temp;
    for (int i = 0; i < longer_len; i++)
    {
        temp.data[i] = (this->data[i] + bignum.data[i] + carried) % 10;
        carried = (this->data[i] + bignum.data[i] + carried) / 10;
    }
    if (carried > 0)
    {
        temp.data[longer_len] = carried;
        longer_len += 1;
    }
    temp.length = longer_len;
    return temp;
}

//利用operator+()实现operator+=()
bign &bign::operator+=(const bign &bignum)
{
    *this = *this + bignum;
    return *this;
}

重载 - ，实现大整数减法

减法只考虑了大数减小数。

减法和加法类似，利用borrowed变量记录借位，按位置相减，最后算出长度（最高位）即可。

bign bign::operator-(const bign &bignum)
{
    int longer_len = max(this->length, bignum.length);
    int borrowed = 0;
    bign temp;
    for (int i = 0; i < longer_len; i++)
    {
        if (this->data[i] < bignum.data[i] + borrowed)
        {
            temp.data[i] = 10 + this->data[i] - bignum.data[i] - borrowed;
            borrowed = 1;
        }
        else
        {
            temp.data[i] = this->data[i] - bignum.data[i] - borrowed;
            borrowed = 0;
        }
    }
    //计算长度
    for (int i = 500; i >= 0; i--)
    {
        if (temp.data[i] > 0)
        {
            temp.length = i + 1;
            break;
        }
    }
    return temp;
}

//利用operator-()实现operator-=()
bign &bign::operator-=(const bign &bignum)
{
    *this = *this - bignum;
    return *this;
}

重载 * ，实现大整数乘法

这里我使用的算法原理是模拟乘法竖式计算。为了简化步骤，计算时先不进位，全部运算完之后再进行进位。

bign bign::operator*(const bign &bignum)
{
    bign temp;
    for (int i = 0; i < length; i++) //this->data作为竖式上面的数
        for (int j = 0; j < bignum.length; j++) //bignum.data作为竖式下面的数
            temp.data[i + j] += this->data[i] * bignum.data[j]; 
            //相乘后的结果加到对应位置，但并不进位

    //统一进位
    for (int i = 0; i < 500; i++)
    {
        if (temp.data[i] >= 10)
        {
            temp.data[i + 1] += (temp.data[i] / 10);
            temp.data[i] %= 10;
        }
    }

    //计算长度
    for (int i = 500; i >= 0; i--)
    {
        if (temp.data[i] > 0)
        {
            temp.length = i + 1;
            break;
        }
    }
    return temp;
}

//利用operator*()实现operator*=()
bign &bign::operator*=(const bign &bignum)
{
    *this = *this * bignum;
    return *this;
}

重载 / ，实现大整数除法 (难点)

设计大整数除法的算法是实现大整数类最大的难点。

基本思想是：反复做减法，看从被除数里面最多能减去多少个除数，商就是多少。

但是，逐个减显然效率过低，尤其是对于大整数。所以我们要判断：一次最多能减几个“除数的10的n次方”。

以7546除以23为例：

• 7546长度为4，23长度为2，长度差值是2，所以从23的10^2倍开始考虑
• 先用7546减去23的100倍，即减去2300，可以减3次，余下646，此时商就是300 (300 = 100 * 3)，百位是3
• 然后646减去23的10倍，即减去230，可以减2次，余下186，此时商就是320 (320 = 300 + 10 * 2)，十位是2
• 然后186减去23的1倍，可以减8次，余下2，此时商就是328 (328 = 320 + 1 * 8)，个位是1

bign bign::operator/(const bign &bignum)
{
    //如果除数大于被除数，返回大整数0
    bign ans; //最终的答案
    ans = 0;
    if (*this < bignum)
        return ans; //返回的是bign，而不是int数值

    //如果除数等于被除数，返回大整数1
    ans = 1;
    if (*this == bignum)
        return ans;

    //如果除数小于被除数，开始计算
    int d_len = length - bignum.length; 
    bign this_copy = *this; //this的拷贝
    bign temp10; //大整数10
    temp10 = 10;
    bign temp1; //大整数1
    temp1 = 1;

    bign tempn; 
    ans = 0;
    for (int i = d_len; i >= 0; i--)
    {
        //把被除数的10^n次倍数赋值给tempn
        tempn = bignum;
        for (int j = 0; j < i; j++)
            tempn *= temp10;

        //看看能减几次tempn，存到temp_ans里
        bign temp_ans;
        temp_ans = 1;
        while ((temp_ans * tempn) <= this_copy)
            temp_ans += temp1;
        temp_ans -= temp1;

        this_copy -= (temp_ans * tempn); //this_copy去掉已经减掉的值，以进行下一次计算
        ans.data[i] = temp_ans.data[0]; //把商的对应位数存起来
    }

    //计算长度
    for (int i = 500; i >= 0; i--)
    {
        if (ans.data[i] > 0)
        {
            ans.length = i + 1;
            break;
        }
    }
    return ans;
}

//利用operator/()实现operator/=()
bign &bign::operator/=(const bign &bignum)
{
    *this = *this / bignum;
    return *this;
}

全部代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

class bign
{
private:
    int length;
    int data[500];

public:
    bign();
    void operator=(const string &);
    void operator=(const int &);
    bign &operator+=(const bign &);
    bign &operator-=(const bign &);
    bign &operator*=(const bign &);
    bign &operator/=(const bign &);
    bign operator+(const bign &);
    bign operator-(const bign &);
    bign operator*(const bign &);
    bign operator/(const bign &);
    bool operator>(const bign &);
    bool operator>=(const bign &);
    bool operator<(const bign &);
    bool operator<=(const bign &);
    friend bool operator==(const bign &, const bign &);
    friend bool operator!=(const bign &, const bign &);
    friend ostream &operator<<(ostream &, const bign &);
    friend istream &operator>>(istream &, bign &);
};

bign::bign()
{
    length = 0;
    for (int i = 0; i < 500; i++)
        data[i] = 0;
}

void bign::operator=(const string &str)
{
    length = str.length();
    int j = 0;
    for (int i = str.length() - 1; i >= 0; i--, j++)
        data[j] = str[i] - '0';
    for (int i = str.length(); i < 500; i++)
        data[i] = 0;
}

void bign::operator=(const int &num)
{
    string str = to_string(num);
    operator=(str);
}


bool operator==(const bign &n1, const bign &n2)
{
    if (n1.length != n2.length)
        return false;
    for (int i = 0; i < n1.length; i++)
        if (n1.data[i] != n2.data[i])
            return false;
    return true;
}

bool operator!=(const bign &n1, const bign &n2)
{
    return !(n1 == n2);
}

bool bign::operator>(const bign &bignum)
{
    if (this->length > bignum.length)
        return true;
    else if (this->length < bignum.length)
        return false;
    for (int i = length; i > 0; i--)
        if (data[i] != bignum.data[i])
            return data[i] > bignum.data[i];
    return false;
}

bool bign::operator>=(const bign &bignum)
{
    if (this->length > bignum.length)
        return true;
    else if (this->length < bignum.length)
        return false;
    for (int i = length; i > 0; i--)
        if (data[i] != bignum.data[i])
            return data[i] > bignum.data[i];
    return true;
}

bool bign::operator<(const bign &bignum)
{
    return !(*this >= bignum);
}

bool bign::operator<=(const bign &bignum)
{
    return !(*this > bignum);
}

istream &operator>>(istream &in, bign &bignum)
{
    string str;
    in >> str;
    bignum = str;
    return in;
}

ostream &operator<<(ostream &out, const bign &bignum)
{
    string s = "";
    for (int i = bignum.length - 1; i >= 0; i--)
        s += to_string(bignum.data[i]);
    out << s;
    return out;
}

bign bign::operator+(const bign &bignum)
{
    int longer_len = max(this->length, bignum.length);
    int carried = 0;
    bign temp;
    for (int i = 0; i < longer_len; i++)
    {
        temp.data[i] = (this->data[i] + bignum.data[i] + carried) % 10;
        carried = (this->data[i] + bignum.data[i] + carried) / 10;
    }
    if (carried > 0)
    {
        temp.data[longer_len] = carried;
        longer_len += 1;
    }
    temp.length = longer_len;
    return temp;
}

bign &bign::operator+=(const bign &bignum)
{
    *this = *this + bignum;
    return *this;
}

bign bign::operator-(const bign &bignum)
{
    int longer_len = max(this->length, bignum.length);
    int borrowed = 0;
    bign temp;
    for (int i = 0; i < longer_len; i++)
    {
        if (this->data[i] < bignum.data[i] + borrowed)
        {
            temp.data[i] = 10 + this->data[i] - bignum.data[i] - borrowed;
            borrowed = 1;
        }
        else
        {
            temp.data[i] = this->data[i] - bignum.data[i] - borrowed;
            borrowed = 0;
        }
    }
    for (int i = 500; i >= 0; i--)
    {
        if (temp.data[i] > 0)
        {
            temp.length = i + 1;
            break;
        }
    }
    return temp;
}

bign &bign::operator-=(const bign &bignum)
{
    *this = *this - bignum;
    return *this;
}

bign bign::operator*(const bign &bignum)
{
    bign temp;
    for (int i = 0; i < length; i++)
        for (int j = 0; j < bignum.length; j++)
            temp.data[i + j] += this->data[i] * bignum.data[j];
    for (int i = 0; i < 500; i++)
    {
        if (temp.data[i] >= 10)
        {
            temp.data[i + 1] += (temp.data[i] / 10);
            temp.data[i] %= 10;
        }
    }
    for (int i = 500; i >= 0; i--)
    {
        if (temp.data[i] > 0)
        {
            temp.length = i + 1;
            break;
        }
    }
    return temp;
}

bign &bign::operator*=(const bign &bignum)
{
    *this = *this * bignum;
    return *this;
}

bign bign::operator/(const bign &bignum)
{
    bign ans;
    ans = 0;
    if (*this < bignum)
        return ans;

    ans = 1;
    if (*this == bignum)
        return ans;

    int d_len = length - bignum.length;
    bign this_copy = *this;
    bign temp10;
    temp10 = 10;
    bign temp1;
    temp1 = 1;

    bign tempn;
    ans = 0;
    for (int i = d_len; i >= 0; i--)
    {
        tempn = bignum;
        for (int j = 0; j < i; j++)
            tempn *= temp10;

        bign temp_ans;
        temp_ans = 1;
        while ((temp_ans * tempn) <= this_copy)
            temp_ans += temp1;
        temp_ans -= temp1;
        this_copy -= (temp_ans * tempn);
        ans.data[i] = temp_ans.data[0];
    }

    for (int i = 500; i >= 0; i--)
    {
        if (ans.data[i] > 0)
        {
            ans.length = i + 1;
            break;
        }
    }
    return ans;
}

bign &bign::operator/=(const bign &bignum)
{
    *this = *this / bignum;
    return *this;
}

//主函数测试一下
int main()
{
    bign a, b, c;
    a = "123456789123456789987654321999999999999999999999999";
    cin >> b;
    c = 12345;
    cout << (a + b) << endl;
    cout << (a - b) << endl;
    cout << (a * b) << endl;
    cout << (a / b) << endl;
    cout << (a < b) << endl;
    cout << (a > c) << endl;
    a += b;
    cout << a << endl;
    cout << (a <= b) << endl;
    cout << (a >= c) << endl;
    a += c;
    cout << a << endl;
    cout << (a == b) << endl;
    cout << (a != c) << endl;
    return 0;
}
/*
    输入：
        6514
    输出：
        123456789123456789987654322000000000000000000006513
        123456789123456789987654321999999999999999999993485
        804197524350197529979580253507999999999999999999993486
        18952531336115564935163389929382867669634633097
        0
        1
        123456789123456789987654322000000000000000000006513
        0
        1
        123456789123456789987654322000000000000000000018858
        0
        1
*/

可以改进之处

• unsigned，不能储存负数。实际上这是一个比较好解决的问题，数据成员里加一个bool型的变量，对代码做一些小改动就能完善了。
• 没有异常处理，算法很朴素，类不够稳健。读者可以尝试自行改进。