前言

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型的变量,对代码做一些小改动就能完善了。
  • 没有异常处理,算法很朴素,类不够稳健。读者可以尝试自行改进。


Welcome, and just relax!