4.1.2. 高精度整数算法(I) 数据的表示¶

算法编程中，有时候会遇到需要对超大整数进行运算，C++内置的整数类型都不够用的问题，高精度整数算法就是用来解决这个问题的。我们可以利用C++的内置整数类型拼接构造出一个理论上能达到无限位的超大整数类型，并且自己编程让它具备加减乘除等各种运算功能，这就是高精度整数算法，简称高精算法。

要实现一种完美的高精度整型及其运算不是一件容易的事情。一般来说，我们会定义一个结构作为它的基础，在结构中存储数据并重载运算符来实现各种必要的运算功能，最常见的有加减乘除、比较和赋值，更加完善的还可以让它支持自增减 ++,--、运算赋值 +=,-=,*=,/=,%=、移位 <<,>>,<<=,>>=、取模、按位逻辑运算等等。另外还有一些辅助功能，比如初始化、IO流输入输出等，根据实际需要还可能会有一些别的操作需要添加成员函数来实现，这就根据实际问题的需要来取舍了。这里面有一些功能的实现是相当复杂的，比如除法和取模，有些功能则很少用到。所以实践中也很少会去完全实现所有功能的。

算法编程最常见的高精算法场景一般会有以下几个需求：

实现一个理论上数值范围无限大的整型数据类型；
通常不要求支持负数；
实现加减乘除四则运算和相互比较大小；
能够用C++内置整型数或字面量进行初始化和赋值。

有时候，为了编程更加方便，还可以适当增加以下辅助功能需求：

能够用 cin >> 进行输入，用 cout << 进行输出；
能够用C++ string、C-string或字符串字面量进行初始化和赋值；
支持与C++内置整型数之间的加减乘除运算和相互比较大小；
支持 +=, -=, *=, \=, ++, -- 等能带来编程便捷性的运算；
声明变量时默认初始化为0。

从这一节起我们将逐步实现一个符合上述要求的非负高精度整数类型 BigInt。掌握了这些常用功能的实现之后，其他不常见的功能实现起来也应该不难了。最后我们会完成一个算法题，看看在实际解决问题的时候如何实现一个简化版的高精度整型。

4.1.2.1. BigInt数据结构¶

原理

为了实现高精度整型数，我们的基本思路很简单，用现有的C++基本整数类型构造一个顺序表来拼接出超大整型数。具体要怎样构造呢？

一个朴素的思路是这样的，既然我们的目标是无符号整数，那么何不用最大的基本类型 unsigned long long 来进行拼接呢？一个 unsigned long long 最大可以表示 \(2^{64}-1\)，所以两个拼接就能使上限达到 \(2^{128}-1\)，\(n\) 个 unsigned long long 就可以拼接成一个 \(64n\) 位的无符号二进制整数，最大可以表示十进制数 \(2^{64n}-1\)。

事实上这种朴素的思路是汇编语言实现高精度整数的标准思路，但是并不适合C++。因为这种表示方式是基于二进制的，二进制是汇编语言的拿手好戏，但C++毕竟是一种高级语言，它在表达上是按照人类的习惯采用十进制的。所以我们的实现也要基于十进制才能符合C++的表达习惯，这里涉及到好几个细节问题需要逐一确定。

问题一，用哪一种基本数据类型来作为拼接单位？答案当然是 int，因为C++标准规定，所有计算机系统上的所有C++版本，必须确保 int 是运算速度最快的数据类型！有人可能会问，既然我们的目标类型是非负的，那么为什么不用 unsigned int 呢？那是因为在做减法的时候，对位相减可能会出现负数需要借位，而 unsigned int 无法表示负数，用它来构造会很难实现减法运算。事实上，所有 unsigned 整型都不适合用来构造高精度整数。

问题二，采用多大的进制？用于拼接的每一个 int 数相当于整个 BigInt 数的一个数位，不妨把它叫做一个节（这是我自己给它取的名字，以避免和十进制的位产生混淆，并不是标准的名称）。前面已经说了拼接要基于十进制，所以 BigInt 要看成是 \(10^n\) 进制的数，一个节的取值范围相应就是 \(0\) 到 \(10^n-1\)，对应 \(n\) 个十进制位。所以 \(n\) 要取多大合适呢？由于 int 最大可表示的正数大约为21亿左右，所以理论上最大可以支持到 \(10^9\)，即十亿进制。实践中常见的有采用亿进制的，也有采用万进制的。

在这里，我们选用我喜欢的万进制。为什么？明明一个 int 最大可以表示到十亿的数量级，为什么要让一个节限制在一万以内呢？这不是极大的资源浪费吗？还是因为算法编程的特性使然。算法编程首要考虑的是编程方便、不易出错、运行速度足够快，而存储空间往往可以用来大把大把地挥霍以换取便捷性和高速性。所以我们有两个理由来支持万进制：

模拟乘法运算，基本操作是节与节之间的整数乘法，采用万进制，结果最大为9999×9999，这个结果恰好还在 int 的可表示范围之内。所以 BigInt 乘法运算时，可以直接在节上进行运算，无需引入 long long 型的中间变量，大大简化乘法运算的代码。这是编程便捷性、减少错误点的理由。
类似地，所有加减乘除运算都可以直接在节上采用 int 型运算完成，无需引入中间变量，能够提高运算速度，尤其是乘除法这样的复杂运算。这是提高速度的理由。

通常，我们把进制数称为基（Base），例如十进制的基是10，2进制的基是2，所以 BigInt 的基等于10000。每一个节所表示的十进制位数我们习惯上称之为宽（Width），这里 BigInt 的宽是4，表示每一个节对应4个十进制位。所以万进制的 BigInt 数和通常的十进制数是可以对位划分节的（就好像2进制和16进制一样）。

例如：十进制数1234567890987654321，总共19位。若表示成万进制，则字面上来看毫无区别，但实际是从个位开始每4位为1节：123|4567|8909|8765|4321，总共5节，其数值为 \(4321\times b^0+8765\times b^1+8909\times b^2+4567\times b^3+123\times b^4\)，其中 \(b\) 是基，等于10000。

问题三，具体用什么数据结构拼接？怎么拼接？从前面的叙述可以看出，最合适的数据结构是顺序表，一般 vector<int> 是最常用的。但怎么拼接却是有一定的技巧。熟悉汇编语言的人会知道，以Intel的x86架构为代表的现代计算机系统里，整数在内存中采用一种叫做小端序（Little-Endian）的方式存放，即“低位在前、高位在后”。例如一个两字节的数 1234，存放在内存里的时候会是 3412。为什么会这样？因为加减法和乘法运算都需要两个数低位对齐！虽然除法运算从最高位对齐开始，但整数除法往往是用减法来模拟的。所以为了方便地实现算术运算，小端序是更好用的存储方式。

补充

整数存放于内存时，为了计算方便，常采用小端序。但在网络传输时，没有了计算的需求，所以常采用大端序，以人们习惯的高位在前的方式进行传输，同时也便于接收一方查看。毕竟人眼看数，还是习惯先看高位。

鉴于上述原因，BigInt 也采用小端序！即低节在前、高节在后。例如 1234567890987654321，在 BigInt 内部的顺序表中存放的情形将是：[4321, 8765, 8909, 4567, 123]。看起来挺诡异，但是到编写算术运算代码时就会发现它的好处了。

基本结构

下面我们就可以写出最基础的结构体定义了。

#include <vector>

using namespace std;

struct BigInt {
	static const int _BASE = 10000;	// 基，每个节的数值范围为0-9999
	static const int _WIDTH = 4;	// 节数码宽度，每节4个十进制数码
	vector<int> _s;			// 用于存放数值的节向量，小端序存放
};

注解

在这个结构里面定义了两个成员常量 _BASE 和 _WIDTH。它们分别表示 BigInt 的基和宽，也说明了 BigInt 类型采用万进制，每一节对应4个十进制位。这两个常量是类型本身固有的属性，后面对它进行各种操作的代码中时常会用到这两个属性。所以我们事先把它们定义成结构的成员常量。

这里我们又一次见到了 static 这个修饰词，我们上一次见到它是在生成排列组合的时候，用来在函数内部定义静态局部变量以便在函数的多次递归调用之间保持某些状态，忘了的话请回到静态局部变量复习。

当它用来修饰结构的成员时则表示另一种含义，这时候它表示 _BASE 和 _WIDTH 是隶属于结构类型 BigInt 本身的成员，而不是某个具体的 BigInt 结构变量的成员。换句话说，这两个常量对于所有的 BigInt 变量来说都是一样的，是大家共享的，没有你的我的之分。在内存中无论定义出多少个 BigInt 变量来，_BASE 和 _WIDTH 都永远只有一个，只此一家、别无分号。反过来，如果我们像通常那样的定义它们，不加上静态修饰，那么它们就是普通的成员常量，每个 BigInt 变量都存有自己的一份，这就造成了空间浪费。

同一个结构的成员函数要使用这样的静态成员时，只要简单地用它们的名字 _BASE 或者 _WIDTH 就可以了。其他地方如果要访问它们，就需要加上结构名的命名限定：BigInt::_BASE、BigInt::_WIDTH。类似地，成员变量和成员函数也可以用 static 修饰成静态的。凡是静态的成员，就升格为隶属于类型的成员，用 类型名::成员名 的方式访问。

请记住，在设计结构的时候，如果有某个成员变量是今后供所有结构变量共享使用，不分你我的，那么就应该定义成静态成员变量。如果是成员常量，那当然一定要定义成静态成员常量了。

P.S. 这里我们使用了名称前加下划线 _数据封装惯例，表示这些个成员都是“仅限内部使用”的。

现在我们已经有了最基本的 BigInt 的数据存储结构，但是它还没什么用，接下来我们要对它进行功能扩展。在此之前，请复习一下以前在3.5.6.3“C++结构类型的大小比较”小节中学过的关于成员变量、成员函数、运算符重载等的知识：C++结构语法。

4.1.2.2. BigInt构造器：初始化¶

我们先从利用构造器来实现C++风格的初始化功能开始。

目前的 BigInt 还只是一个C语言风格的结构类型，如果用它来定义新的变量，没有办法对它进行有效的初始化。我们希望可以在定义新变量时自动把它的值设置为0，或者我们可以用一个C++内置整数类型的数值来赋予它初始值。这种情况下用构造器是最合适的。构造器，在C++中通常被叫做构造函数，在生成新变量的时候它会被自动调用，可以用来设置结构变量的初始状态。

构造器没有返回类型，不需要返回语句，构造器的函数名必须和结构名完全相同。
构造器总是在一个结构变量被生成的时候首先被调用，它的作用就是初始化新变量。
一个结构可以有多个参数表不同的构造器，使其具有多种多样的构造方法。
构造器的使用方法是在定义新变量时在变量名后面加上构造器参数，就像调用一个函数一样。具体调用哪个构造器，C++会根据提供的参数来自动确定。
如果定义新变量时没有提供构造器参数，那么C++会检查有没有不需要提供参数的构造器，如果有就调用它，如果没有就什么都不干，那就是没有初始化了。

所以让我们先来实现我们想要的这个构造器：

#include <vector>

using namespace std;

struct BigInt {
	static const int _BASE = 10000;	// 基，每个节的数值范围为0-9999
	static const int _WIDTH = 4;	// 节数码宽度，每节4个十进制数码
	vector<int> _s;			// 用于存放数值的节向量，小端序存放
	// 内部功能函数
	void _assign(unsigned long long value);
	// 构造器
	BigInt(unsigned long long value = 0);
};

void BigInt::_assign(unsigned long long value) {
	_s.push_back(value % _BASE);
	while (value /= _BASE)
		_s.push_back(value % _BASE);
}

BigInt::BigInt(unsigned long long value) { _assign(value); }

注解

这里我们先定义了一个成员函数 void _assign(unsigned long long value)，它真正实现把一个C++整数转换为 BigInt 内部数据的功能。构造器 BigInt(unsigned long long value = 0) 只是简单地调用了它而已。为啥要把这个功能单独写成一个函数，而不是直接写在构造器里呢？这是因为这个功能以后在别的地方还用得着，单独写出来就可以重复利用了。这叫做代码的复用，是一种重要的软件设计思想。

这里还可以看到，构造器也和普通的成员函数一样，可以采用函数原型与定义分离的代码书写方式。

这个构造器需要一个 unsigned long long 型参数，这是C++内置整型的最大者，用它就可以使实参支持C++所有的内置整型。另外我们还把这个参数定义为默认值参数，于是构造器就有了两个版本，既可以提供一个初始值参数，也可以不提供任何参数而默认初始化为0。

注意：当函数采用原型和定义分离的方式来写的时候，默认参数只能写在一个地方，要么写在函数原型的参数表里，要么写在函数定义中函数头的参数表里，不能两个地方都出现。一般我们都建议写在函数原型的参数表里。

至于 _assign() 函数内部将参数值转成节，并用小端序依次存入 _s 中的功能是怎样实现的，我想应该很容易看懂，就不多做解释了，请务必自己看懂它。

现在，我们可以像这样来定义 BigInt 型的变量了：

BigInt b1, b2(347), b3(123456789000012), b4(100001);  // b1 会被初始化为0

好像还缺点什么？对了，我们现在的构造器只能支持最大不超过 unsigned long long 的整数初始值，可是 BigInt 的目标是要理论上能支持无限长的整数的。如果我们要用一个100位的超长整数来初始化怎么办？

显然这样超长的整数在C++本身的数据类型中，恐怕也只能用字符串来模拟它。所以我们是不是还应该有一个可以用字符串来进行初始化的构造器呢？有了前面的经验，这项任务也并不难办到。于是 BigInt 结构再一次升级：

#include <string>
#include <vector>

using namespace std;

struct BigInt {
	static const int _BASE = 10000;	// 基，每个节的数值范围为0-9999
	static const int _WIDTH = 4;	// 节数码宽度，每节4个十进制数码
	vector<int> _s;			// 用于存放数值的节向量，小端序存放
	// 内部功能函数
	void _assign(unsigned long long value);
	void _assign(const string &str);
	// 构造器
	BigInt(unsigned long long value = 0);
	BigInt(const string &str);
};

void BigInt::_assign(unsigned long long value) {
	_s.push_back(value % _BASE);
	while (value /= _BASE)
		_s.push_back(value % _BASE);
}

void BigInt::_assign(const string &str) {
	int p = str.size(), h, v;
	if (p == 0)
		_s.push_back(0);
	else
		while (p > 0) {
			h = p >= _WIDTH ? p - _WIDTH : 0;
			v = 0;
			while (p > h) v = v * 10 + str[h++] - '0';
			_s.push_back(v);
			p -= _WIDTH;
		}
	while (_s.size() > 1 && _s.back() == 0) _s.pop_back();
}

BigInt::BigInt(unsigned long long value) { _assign(value); }

BigInt::BigInt(const string &str) { _assign(str); }

注解

这里利用C++函数重载的能力，定义了另一套基于字符串的构造器和 _assign() 函数。看起来用字符串来初始化的代码稍微复杂一点，但是也不难理解，请务必看懂理解。

由于C++ string和C-string、字符串字面量之间能很好的自动转换，所以我们现在又具备了这样的能力：

string s1 = "";
BigInt b5(s1);    // 空字符串使初始值为0
BitInt b6("987654321012345678909876543210123456789000");

警告

这里我们没有对字符串进行有效性验证，如果字符串不是一个合法的整数形式，那么会出现错误。这是因为考虑到算法编程题目的输入数据格式都是确保有效的，所以我们不费心去进行有效性验证。这也是算法编程的特殊性，在实际的软件开发中，输入有效性验证是必不可少的。

4.1.2.3. BigInt赋值运算¶

光有初始化显然还不够，我们当然还需要有给 BigInt 变量赋值的能力，而且有了赋值的能力后我们还能像通常的内置数据类型一样使用 BigInt x = 3; 这样的语句来初始化变量。

要让自定义数据类型具有赋值运算的功能，就需要用到C++的神技运算符重载。现在我们就来看看怎样为 BigInt 重载赋值运算符 =。由于已经有了可以复用的函数 _assign()，赋值运算的重载就很方便了，先在结构内部声明重载函数的原型：

struct BigInt {
        // ...
        BigInt &operator=(unsigned long long value);
        // ...
};

然后给出它的定义：

BigInt &BigInt::operator=(unsigned long long value)
{
	_s.clear();
	_assign(value);
	return *this;
}

现在我们可以在程序里使用这样的代码了：

BigInt b7 = b8 = 666, b9 = 0;
b9 = 373 + 737;

注解

赋值运算要返回变量被赋予的值，这通过以引用方式返回 *this 来实现。this 是指向调用者自己的指针，所以返回 *this 就是返回调用者自己的值。

调用 _assign() 函数完成赋值之前先调用的 _s.clear() 是用来清空原有数据的。

运算符重载函数本身也是可以重载的，所以我们可以用类似的方式来实现用字符串赋值。函数原型：

struct BigInt {
        // ...
        BigInt &operator=(const string &str);
        // ...
};

函数定义：

BigInt &BigInt::operator=(const string &str)
{
	_s.clear();
	_assign(str);
	return *this;
}

现在我们比较完美地完成了 BigInt 类型的赋值功能，我们可以这样来使用：

b9 = "1234567890987654321";
b8 = b9;      // 别忘了结构变量天生具有相互赋值的能力

唯一的遗憾是如果要用C-string初始化 BigInt 变量，则不能用传统的赋初始值方式

BigInt b10 = "12345";   // 这样是不行的，编译会报错：不支持的类型转换
// 替代方案1：用C++构造器
BigInt b11("12345");
// 替代方案2：先定义，后赋值
BigInt b12;
b12 = "12345";
// 替代方案3：生成临时的c++ string
BigInt b13 = string("12345");

4.1.2.4. BigInt输入输出¶

如果可以让 BigInt 也能像内置数据类型一样使用IO流输入输出的话，它就更加完美了。为了达到这个目的，我们可以重载C++的IO流运算符 << 和 >>。它们是属于IO流的运算符，要重载它们需要引入 iostream 库。为了在输出的时候能够控制输出格式，还需要引入 iomanip 库（流操纵库）。

由于它们俩并不是属于 BigInt 的运算符，而是输出流 ostream 和 istream 的，所以重载函数不定义在结构内部。重载函数的原型如下：

#include <iostream>
#include <iomanip>

// 输入输出流运算不能重载为成员函数，只能重载为普通函数
ostream &operator<<(ostream &os, const BigInt &bi);
istream &operator>>(istream &is, BigInt &bi);

注解

ostream 和 istream 是C++输出流和输入流的基础类型（基类），所有实际的输入输出流都是从它们两个继承而来的，比如最常见的标准输入输出流 cin 和 cout，还有文件流、字符串流等。所以重载了这两个运算符之后，不光我们可以实现用 cin >> 和 cout << 来从键盘输入、向屏幕输出 BigInt 型数据，而且我们同时实现了读写文件等其他所有方式的 BigInt 数据输入输出。这一点非常棒！

上面这两个重载函数的原型格式是固定的，如果我们还要实现对其他自定义类型的输入输出，那么也参考这两个原型，只需改一下参数表中第二个参数的类型就可以了。

实现 BigInt 输入的方法非常简单，因为我们已经有了用字符串赋值的方法，所以我们只要先以字符串形式读入数据，然后用这个字符串去赋值就可以了。

实现输出的方法同样很简单，只要从高到低输出每一个节的数值就可以了。第一个节，也就是最高位上的节，用默认格式输出即可。从第二个节开始，每个节要确保按4位十进制整数的格式输出，不足4位的要在左边补0。比如12，就要输出为0012这样的形式。这里涉及到一些格式化输出的技巧：

在输出流中，可以使用一些叫做流操纵算子的函数来控制输出格式，它们包含在 iomanip 库中，所以要引入这个库；
使用 setw() 算子，可以控制下一次输出时的最短宽度，比如 cout << setw(4) << x 就可以使得变量 x 的值在输出时至少占用4个字符的宽度；
使用 left、right 这两个算子，可以控制下一次输出时数据的对齐方式，左对齐或右对齐，默认是右对齐；
使用 setfill() 算子，可以控制下一次输出时如果实际数值位数小于指定的最小宽度，那么在空余地方填进什么字符，默认是填空格；
请注意每次使用操纵算子设置的格式都是一次性的，仅针对下一次输出，随即就会自动复原为默认格式。

所以每次在输出非最高位的节之前应这样控制输出格式：... << right << setw(4) << setfill('0') << ...。

现在我们已经让 BigInt 类初具雏形了，已经实现了定义、初始化、赋值和输入输出。为了给今后实现加减乘除的算术运算时提供一点小便利，我们还给 BigInt 增加了一个小小的辅助功能函数 zero() 用来判断自己是不是等于0。下面给出到目前为止的完整代码：

#include <string>
#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

struct BigInt {
	static const int _BASE = 10000;	// 基，每个节的数值范围为0-9999
	static const int _WIDTH = 4;	// 节数码宽度，每节4个十进制数码
	vector<int> _s;			// 用于存放数值的节向量，小端序存放
	// 内部功能函数
	void _assign(unsigned long long value);
	void _assign(const string &str);
	// 构造器
	BigInt(unsigned long long value = 0);
	BigInt(const string &str);
	// 辅助功能函数
	bool zero() const;		// 判断是不是等于0
	// 赋值运算
	BigInt &operator=(unsigned long long value);
	BigInt &operator=(const string &str);
};

// 输入输出流运算不能重载为成员函数，只能重载为普通函数
ostream &operator<<(ostream &os, const BigInt &bi);
istream &operator>>(istream &is, BigInt &bi);

// 以下为函数定义。算法编程中通常函数定义放在main()函数的后面，工程编程中则往往写在另一个单独的程序文件里
ostream &operator<<(ostream &os, const BigInt &bi)
{
	int i = bi._s.size();
	os << bi._s[--i];
	while (--i >= 0)
		os << right << setw(4) << setfill('0') << bi._s[i];

	return os;
}

istream &operator>>(istream &is, BigInt &bi)
{
	string str;
	is >> str;
	bi._s.clear();
	bi._assign(str);

	return is;
}

void BigInt::_assign(unsigned long long value) {
	_s.push_back(value % _BASE);
	while (value /= _BASE)
		_s.push_back(value % _BASE);
}

void BigInt::_assign(const string &str) {
	int p = str.size(), h, v;
	if (p == 0)
		_s.push_back(0);
	else
		while (p > 0) {
			h = p >= _WIDTH ? p - _WIDTH : 0;
			v = 0;
			while (p > h) v = v * 10 + str[h++] - '0';
			_s.push_back(v);
			p -= _WIDTH;
		}
	while (_s.size() > 1 && _s.back() == 0) _s.pop_back();
}

BigInt::BigInt(unsigned long long value) { _assign(value); }

BigInt::BigInt(const string &str) { _assign(str); }

bool BigInt::zero() const { return _s.size() == 1 && _s[0] == 0; }

BigInt &BigInt::operator=(unsigned long long value)
{
	_s.clear();
	_assign(value);
	return *this;
}

BigInt &BigInt::operator=(const string &str)
{
	_s.clear();
	_assign(str);
	return *this;
}

注意

为了比较完整地说明自定义数据类型和高精度整数类型的实现技术，我们实现了比较多的功能，比如用多种方式进行初始化，比如流输入输出等。在实际编程解决算法问题的时候，往往并不一定要用到所有的功能。考场编程必然是采取“极简”的策略，只实现必不可少的部分，任何可有可无的代码都应该避免。所以具体解决问题的时候，高精度整数算法要如何实现，实现哪些功能，还需不需要增加一些其他功能等等问题，都是要临场判断随机应变的。

重要的是理解方法，记住必须记住的语法，不要死记硬背代码。

目录

上一个主题

下一个主题

本页