大整数运算简介

最后更新：2019/09/18
前排提示，板子已经更新。~~（这篇博客写的什么垃圾玩意，完全没法看）~~
如果你只是来找板子的，可以点击这里下载。

一、大整数运算方式¹

由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。对于 $J a v a$ 、 $P y t h o n$ 这些自带高精度的语言来说，大数运算完全不是问题。但 $C / C$ ++ 选手就很难受了，因此，学会大数运算是非常有用的。

0.存储

一般来说，大整数是超过 $l o n g$ $l o n g$ ，甚至用 $d o u b l e$ 都放不下的数字，这个时候已经无法用一般的类型存储，只能被存为 $c h a r$ 类型的数组或是 $s t r i n g$ 类中，例如：

string a = "1234567890";
char b[100] = "987654321";

建议存入数组的时候为每一位减去'\0'以便于运算，但这么做的结果是要多维护一个数字的长度变量。
而且数字具有正负性，负号显然是不适合存储到存放数字的数组中去的，所以还要有一个代表数字正负的变量。下面是一个大数结构体的例子：

struct BigInt{
	char data[1000] = {};
	int length = 1;
	bool sign = true;
}

1. 加法

回忆一下我们是如何手算加法的：
$\begin{array}{r} 1234567890\\ + \quad 987654321\\ \hline 2222222211 \end{array}$ 相同数位对齐，从最低位开始运算，若和超过10，则向前进位。
当然，这是建立在两个正数的情况下。对于两个数字 $n u m 1$ 和 $n u m 2$ ，我们用 $a$ 来表示 $∣ n u m 1 ∣$ ， $b$ 来表示 $∣ n u m 2 ∣$ ，那么分为以下四种情况：

若 $n u m 1 > 0$ ， $n u m 2 > 0$ ，则 $n u m 1 + n u m 2 = a + b$
若 $n u m 1 < 0$ ， $n u m 2 < 0$ ，则 $n u m 1 + n u m 2 = - a + (- b) = - (a + b)$
若 $n u m 1 < 0$ ， $n u m 2 > 0$ ，则 $n u m 1 + n u m 2 = - a + b = b - a$
若 $n u m 1 > 0$ ， $n u m 2 < 0$ ，则 $n u m 1 + n u m 2 = a + (- b) = a - b$

2. 减法

只要我们加入了正负号，就不可避免地会从加法区域转移到减法来。
$\begin{array}{r} 1234567890\\ - \quad 987654321\\ \hline 246913569 \end{array}$ 相同数位对齐，从最低位开始运算，若差小于0，则从前一位借位。
图中列出的是被减数大于减数，且两者都为正数的情况。对于一般性的减法，我们有下列预处理：

若 $n u m 1 < 0$ ， $n u m 2 < 0$ ，则 $n u m 1 - n u m 2 = - a - (- b) = b - a$
若 $n u m 1 < 0$ ， $n u m 2 > 0$ ，则 $n u m 1 - n u m 2 = - a - b = - (a + b)$
若 $n u m 1 > 0$ ， $n u m 2 < 0$ ，则 $n u m 1 - n u m 2 = a - (- b) = a + b$
若 $n u m 1 > 0$ ， $n u m 2 > 0$ ，则 $n u m 1 - n u m 2 = a - b$
此时，若 $a < b$ ，则 $n u m 1 - n u m 2 = - (b - a)$

从而使一般的减法可以转换成被减数大于减数，且两者都为正数的减法来运算。

3. 乘法

乘法结果正负性很好判断，所以只考虑正数情况。
一般的，我们的竖式是这么写的：
$\begin{array}{r} 1234567890\\ \times \qquad \qquad 987654321\\ \hline 1234567890\\ 2469135780\ \ \\ 3703703670\quad \\ 4938271560\quad\ \ \\ 6172839450\qquad \\ 7407407340\qquad\ \ \\ 8641975230\qquad \quad \\ 9876543120\qquad \quad\ \ \\ 11111111010\qquad \qquad \\ \hline1219326311126352690 \end{array}$ 相同数位对齐，从最低位开始运算，最后把结果加和。
这个过程可以理解为：一个数的第 $i$ 位乘上另一个数的第 $j$ 位就应加在积的第 $i + j - 1$ 位上。

4. 除法²

除法的符号规则和乘法一样，因此只考虑正数的情况：
$\begin{array}{r} 1 \\ 987654321\sqrt{ 1234567890} \\ 987654321 \\ \hline 246913569 \\ \end{array}$

（长除法打不出来只好用蹩脚的方法代替了）

除法的关键点就在于试根，根据除数的大小从被除数中截取一段数字，然后不断试根，最后得出该位的数据，用被除数减去试出的根乘以除数的积。循环往复。

5. 细节

通过分析，我们可以得知，大部分的运算都是需要从最低位开始计算的。因此在存储数字的时候，逆序存储是一个更加优秀的方法：这样可以免去对位数没对齐的处理，同时循环可以从 $0$ 开始，也符合书写习惯。
因此，例如一个"1234567890"的字符串，在数组内部的存放情况就可能是：

下标	0	1	2	3	4	5	6	7	8	9	…
数据	0	9	8	7	6	5	4	3	2	1	0

6. 压位

让我们来思考一下 $1234567890$ 这个数字：

下标	0	1	2	3	4	5	6	7	8	9	…
数据	0	9	8	7	6	5	4	3	2	1	0

这样存放会浪费很大的空间，而且在运算过程中循环次数也很多。
考虑到高精度运算实质上是用低精度运算实现的，那么在低精度运算的时候能省力就省力才对。是否可以考虑让每一个数组空间存储的数字大一些，从而节省一些空间和循环次数呢？

下标	0	1	2	3	4	…
数据	90	78	56	34	12	0

同样是逆序存储数据，但每一位的元素范围不再是 $[1, 9]$ ，而是 $[1, 99]$ ，可以看成是100进制，对资源的利用度更加高。这种操作方法被称为压位。
一般来说，考虑到乘法的中间过程会出现两倍压位长度的数据，采用压4位的方式比较合理。对于数字 $1234567890$ 而言，压四位的结果如下：

下标	0	1	2	…
数据	7890	3456	12	0

二、大整数运算的代码实现

既然要压位，那么 $c h a r$ 数组肯定是无法存下了，本人在实现时利用了 $v e c t o r$ < $i n t$ > 作为存放数据的容器。因为这样可以动态分配空间，不容易 $M L E$ 。实现方法是创建了一个 $b i g i n t$ 类，可以直接拿来当作 $i n t$ 用。

1. 类私有成员

class bigint
{
public:
	//...
private:
    static const int __bit = 4;         //压缩的位数
    static const int __base = 10000;    //等于10^__bit;
    bool __sign;
    vector<int> __data;
};

2. 构造函数与重整函数

$r e f o r m$ 函数的作用是清除前导 $0$ ，并将空数据变为 $0$ ，因此在四则运算结束后都会进行一次调用。

	bigint()
    :  __sign( true ) 
    { __data.push_back(0); }
    
    bigint( const bigint& __bigint )
    :  __sign( __bigint.__sign )
    { __data.assign(__bigint.__data.begin(), 
    			__bigint.__data.end()); }

    void 
    reform()
    {
        while( __data.size()>1 && __data[__data.size()-1]==0 )
            __data.pop_back();
        if( __data.size()==0 )
            __data.push_back(0);
        if( __data.size()==1 && __data[__data.size()-1]==0 )
            __sign = true;
    }

3. 读取数据

重载了这些类型以后，就可以不用考虑 $b i g i n t$ 型与其他类型进行操作的问题了——他们会自己隐式转换。

	bigint& 
    operator=( const char* __str )
    {
        int __numberpos = 0;                //记录字符串中第一个非符号位
        int __strlength = strlen(__str);    //记录字符串的长度
        int __devider = 0;                  //分割数字时的临时变量
        __sign = true;
        __data.clear();

        //找到数字开始处，处理前导符号
        while( __numberpos<__strlength ){
            if( __str[__numberpos]=='+' ){
                __numberpos++;
            }else if( __str[__numberpos]=='-' ){
                __numberpos++;
                __sign = !__sign; 
            }else{
                break;
            }
        }

        //从字符串尾部开始，每__bit位分割并转int，存储入__data中
        for(int __i=__strlength-1; __i>=__numberpos; __i-=__bit){
            __devider = 0;
            for(int __j=__bit-1; __j>=0; __j--)
                if( __i-__j>=__numberpos )
                    __devider = __devider*10 + __str[__i-__j]-'0';
            __data.push_back(__devider);
        }

        this->reform();
        return *this;
    }
    
    bigint& 
    operator=( const long long& __num )
    {
        long long __number = __num;
        __number = abs(__number);
        __sign = __num>=0 ? true : false;
        __data.clear();

        while( __number>0 ){
            __data.push_back( __number%__base );
            __number /= __base;
        }
        return *this;
    }

	bigint& 
    operator=( const string& __str )
    { *this = __str.c_str(); return *this; }
    
    bigint& 
    operator=( const int& __num )
    { *this = (long long)__num; return *this; }

4. 剩下的构造函数

很好理解，就不多提了。

	bigint( const char* __str )
    { *this = __str; }
    
    bigint( const string& __str )
    { *this = __str.c_str(); }
    
    bigint( const long long& __num )
    { *this = __num; }
    
    bigint( const int& __num )
    { *this = __num; }

5. 输入输出流重载

    friend istream&
    operator>>( istream &in, bigint& num )
    {
        string str;
        in >> str;
        num = str;
        return in;
    }

    friend ostream&
    operator<<( ostream &out, const bigint& __bigint )
    {
        if( !__bigint.__sign )
            out << '-';
        for(int __i=__bigint.__data.size()-1; __i>=0; __i--)
            if( __i == (int)__bigint.__data.size()-1 ){
                out << __bigint.__data[__i];
            }else{
                out << setw(__bigint.__bit) << setfill('0')
                	<< __bigint.__data[__i];
            }
        return out;
    }

输出的时候需要经过格式控制，这里提几个细节：
1.逆序输出
2.由于是 $10000$ 进制，所以非首位输出时都要补零
3.首先输出负号

6. 比较运算符

由于减法和除法中要比较两个大整数的大小，所以比较符的重载也是必要的。

	inline bool
    operator<( const bigint& __compare ) const
    {
    	//两者异号，结果显而易见
        if( __sign ^ __compare.__sign )
            return __compare.__sign;
        //同号，数字长度不同，结果显而易见
        if( __data.size() != __compare.__data.size() )
            return __sign ? (__data.size()<__compare.__data.size())
                        : (__data.size()>__compare.__data.size());
        //同号，长度相同，按每位比较，发现有数字不同即判断出结果
        for(int __i=__data.size()-1; __i>=0; __i--){
        if( __data[__i] != __compare.__data[__i] )
            return __sign ? (__data[__i] < __compare.__data[__i])
                        : (__data[__i] > __compare.__data[__i]);
        }
        //如果相同返回假
        return false;
    }

    inline bool 
    operator>( const bigint& __compare ) const
    { return (__compare < *this); }

    inline bool 
    operator<=( const bigint& __compare ) const
    { return !(*this > __compare); }

    inline bool 
    operator>=( const bigint& __compare ) const
    { return !(*this < __compare); }
    
    inline bool 
    operator==( const bigint& __compare ) const
    {	
    //可以写成return !(*this < __compare || *this > __compare);的形式
        if( __sign ^ __compare.__sign )
            return false;
        if( __data.size() != __compare.__data.size() )
            return false;
        for(int __i=__data.size()-1; __i>=0; __i--)
            if( __data[__i] != __compare.__data[__i] )
                return false;
        //没有找到不同则返回true，否则就是false
        return true;
    }

    inline bool 
    operator!=( const bigint& __compare ) const
    { return !(*this == __compare); }

7.四则运算

在这些都写好以后，四则运算实际上并没有那么难了，照着之前的思路去实现即可。

	//模拟手算加法
    friend bigint 
    operator+( const bigint& __addend1, const bigint& __addend2 )
    {
    	if( __addend1.__sign ^ __addend2.__sign ){
            bigint __negative_addend;
            __negative_addend = __addend1.__sign ? __addend2 : __addend1;
            __negative_addend.__sign = true;
            return __addend1.__sign ? (__addend1 - __negative_addend)
                                    : (__addend2 - __negative_addend);
        }
        
        bigint __sum;
        int __carry = 0;
        __sum = __addend1;
        __sum.__data.resize(max(__addend1.__data.size(), 
                                __addend2.__data.size())
                            +1, 0);
        for(int __i=0; __i<(int)__addend2.__data.size(); __i++){
            __sum.__data[__i] += __addend2.__data[__i] + __carry;
            __carry = __sum.__data[__i] / __sum.__base;
            __sum.__data[__i] %= __sum.__base;
        }
        if( __carry != 0 )
            __sum.__data[__addend2.__data.size()] += __carry;
        __sum.reform();
        __sum.__sign = __addend1.__sign;
        return __sum;
    }

    //模拟手算减法
    friend bigint 
    operator-( const bigint& __min, const bigint& __sub )
    {
        bigint __minuend = __min, __subtrahend = __sub;
        // 使减法恒定被减数大于减数
        //(-a)-(-b) = b-a
        if( !__minuend.__sign && !__subtrahend.__sign ){
            __minuend.__sign = true;
            __subtrahend.__sign = true;
            return __subtrahend - __minuend;
        //(a)-(-b) = a+b
        }else if( __minuend.__sign && !__subtrahend.__sign ){
            __subtrahend.__sign = true;
            return __minuend + __subtrahend;
        //(-a)-b = -(a+b)
        }else if( !__minuend.__sign && __subtrahend.__sign ){
            __minuend.__sign = true;
            bigint __sum = __minuend + __subtrahend;
            __sum.__sign = false;
            return __sum;
        //a-b = -(b-a)
        }else if( __minuend < __subtrahend ){
            bigint __difference = __subtrahend - __minuend;
            __difference.__sign = false;
            return __difference;
        }

        //同号，被减数大于减数的减法
        bigint __difference = __minuend;
        int __borrow = 0;
        for(int __i=0; __i<(int)__subtrahend.__data.size(); __i++){
            __difference.__data[__i] -= __subtrahend.__data[__i]+__borrow;
            if( __difference.__data[__i]>=0 ){
                __borrow = 0;
            }else{
                __borrow = 1;
                __difference.__data[__i] += __difference.__base;
            }
        }
        if( __borrow==1 )
            __difference.__data[__subtrahend.__data.size()]--;
        __difference.reform();
        return __difference;
    }

	//模拟手算乘法
    friend bigint 
    operator*( const bigint& __multiplier1, const bigint& __multiplier2 )
    {
        bigint __product;
        __product.__data.resize(__multiplier1.__data.size()+ 
                                __multiplier2.__data.size(), 0);
        for(int __i=0; __i<(int)__multiplier1.__data.size(); __i++){
            for(int __j=0; __j<(int)__multiplier2.__data.size(); __j++){
                __product.__data[__i+__j] += 
                    __multiplier1.__data[__i] * __multiplier2.__data[__j];
                __product.__data[__i+__j+1] += 
                    __product.__data[__i+__j]/__product.__base;
                __product.__data[__i+__j] %= __product.__base;
            }
        }
        __product.reform();
        __product.__sign = __multiplier2.__sign==__multiplier1.__sign;
        return __product;
    }

除法的代码就比较麻烦了，而且效率很低

	//模拟手算除法
    friend bigint 
    operator/( const bigint& __divid, const bigint& __divis )
    {
        if( __divid.__data.size()-__divis.__data.size()+1 <= 0 ||
        (__divid.__data.size()==1 && __divid.__data[0]==0) ||
        (__divis.__data.size()==1 && __divis.__data[0]==0) )
        //这里为了使num/0的形式不报错返回了0
            { bigint zero; return zero; }
        
        bigint __quotient, __partition,
            __dividend = __divid, __divisor = __divis;
        __dividend.__sign = __divisor.__sign = true;
        __quotient.__data.resize(__divid.__data.size()-
                                __divis.__data.size()+1, 
                            0);
        int __partitionbegin = __divid.__data.size()-1;
        int __partitionend = __quotient.__data.size()-1;
        int __factorleft, __factorright, __factor;
        string __multiple = "1";
        while( __partitionend>=0 ){
            __partitionbegin = __dividend.__data.size()-1;
            while( __partitionbegin>0 && 
            __dividend.__data[__partitionbegin]==0 )
                __partitionbegin--;
            if( __partitionend>__partitionbegin )
                __partitionend = __partitionbegin;
            __partition.__data.assign(__dividend.__data.begin()+__partitionend, 
                                    __dividend.__data.begin()+__partitionbegin+1);
            if( __partition<__divisor ){
                __partitionend--;
                continue;
            }
            //二分试根
            __factorleft = 1; __factorright = __quotient.__base-1;
            while( __factorleft<__factorright ){
                __factor = (__factorleft+__factorright)/2;
                if( __factor*__divisor<=__partition ){
                    __factorleft = __factor+1;
                }else{
                    __factorright = __factor-1;
                }
            }
            while( __factor*__divisor<__partition ) __factor++;
            while( __factor*__divisor>__partition ) __factor--;
            __quotient.__data[__partitionend] = __factor;
            __multiple.resize(__partitionend*__quotient.__bit+1, '0');
            __dividend = __dividend-__multiple*__divisor*__factor;
            __partitionend--;
        }
        __quotient.reform();
        __quotient.__sign = __divid.__sign==__divisor.__sign;
        return __quotient;
    }

8. 使用方法

嗯， $i n t$ 怎么用要我教你吗（滑稽）

int main()
{
	bigint a, b;
	cin >> a >> b;
	cout << a+b << endl;
	return 0;
}

完整代码可以从这里下载。

如未特殊说明，本文均采用十进制 ↩︎
在程序设计竞赛中，很少会遇到真正的模拟除法，最多也就是高精度除以低精度，所以这部分内容并不那么重要。 ↩︎

秒客网

大整数运算简介

一、大整数运算方式¹

0.存储

1. 加法

2. 减法

3. 乘法

4. 除法²

5. 细节

6. 压位

二、大整数运算的代码实现

1. 类私有成员

2. 构造函数与重整函数

3. 读取数据

4. 剩下的构造函数

5. 输入输出流重载

6. 比较运算符

7.四则运算

8. 使用方法

相关文章

大整数运算简介

一、大整数运算方式1

0.存储

1. 加法

2. 减法

3. 乘法

4. 除法2

5. 细节

6. 压位

二、大整数运算的代码实现

1. 类私有成员

2. 构造函数与重整函数

3. 读取数据

4. 剩下的构造函数

5. 输入输出流重载

6. 比较运算符

7.四则运算

8. 使用方法

相关文章

一、大整数运算方式¹

4. 除法²