基于C++的大整数类型的设计与实现

杨正

摘要：大整数类型能够提供运算符重载、四则运算在内的整套算法。本文针对基于C++的大整数类型的设计与实现的研究，将从数据结构的设计入手，结合相关算法的实现途径，对整数类型设计的应用实例展开论述。

关键词：C语言；大整数类型；系统设计；运算符

中图分类号：TP301.6 文献标识码：A 文章编号：1007-9416（2017）11-0153-01

对计算机而言，无穷大的数字范围需要进行一定限制。比如，常见的long型数据，其长度若为4个字节，其能表示的无符号数就为232-1，这样大的数字范围，对系统测试、天文观测、科学计算等方面的运算来说，就有些力不从心。因此，需要通过编程语言的算法设计，提供出可行方案。而大整数算法，就是实现对大数间进行运算的途径。因此，加强基于C++的大整数类型的设计与实现研究具有重要意义。

1 数据结构的设计

由于大数类对象的基本类型长度不够，因此数据结构内部需要采用数组的形式加以维护，在此基础上，还需要定义出bool型数据，对大数对象的正负性质进行标记。经规划后，大整数类的基本结构，除了bool标记外，还包括int变量数组以及char数组。另外，将大整数类命名为big integer，为节省空间内存，其结构设计为：

class big integer

{ protected：

char*base；

int size；int currentPos；

bool is Negative； }

2 相关算法的实现

2.1 输入输出实现

大数类程序的第一步是计算，第二部就是反馈结果。或者，实现数值的赋予与输出。输入输出实现中，主要包括两点：第一是通用的输入输出。该过程较为简单，输入外部数组，将数组中的数据进行复制，送到对象内部数组。输出就是将内部数组的地址送给外部，对currentPos等需要设立相应函数，保证外部对数值的获取。第二是标准输入输出，根据并操作符，对操作进行声明，遍历数组之后，需输出负号。在输入当中，需判定第一个数为负数后，再开始接收数据。然后，对高位地址的数组进行调整，保证其以低地址方式保存。

2.2 比较算法实现

大整数重载中的相关运算符号有很多，除了加减以外，还包括大于等于、不等于、小于等于、不等于类符号。大整数类具有支持负数的特性，因此许多运算底层有可能看起来不相符。例如，正负数之间的简单运算，很有可能是以减法运算为调用。操作的具体调用，与大整数绝对值大小相关。因此，需要对大整数对象之间进行绝对值比较。

加法实现是底层的加法，不可被外部直接访问，需要被类的其他成员进行调用。将加法实现函数进行meta-add命名后，无需考虑符号，其功能是实现基本加法操作。实现加法的代码十分精简，其主要思想就是利用for循环及while循环，实现逐位相加，然后再进行进位处理。减法实现与加法相似，在操作上与加法几乎一致。首先进行初始化，命名meta-sub然后同样利用for循环进行准备相减，再利用while循环实现出借位处理。乘法实现属于指元操作，函数初始化命名为meta-multi，其实现思路为，将比较后较小的数值每一位，逐一与较大的数值想成，得到n个结果后，将其保存在同一个向量之中。然后，将每个元素相加就会得到乘法的最终数值。

2.3 运算符的重载

运算符的重载主要包括三方面內容：第一，opretor+与opretor+=的实现，由于元操作无法被外部直接使用，因此需要提供一个连接内外部的端口，而运算符的重载就是一个有效途径。第二，oprator-和oprator-=的实现。与加减法相比，这两个算法的实现较为复杂，但是原理仍然是对绝对值大小的判断。不同的是，加法运算需要判断符号的异同，而减法需要判断操作数值的正负。第三，oprator*与oprator-/的实现。与加减法相比，乘法与除法运算复杂程度要大一些，但是在这两者的运算上却是十分简单，主需要对操作数值的相对大小进行判断即可，再根据一定顺序，对乘法运算进行调用。或者比较除数与被除数的关系，若前者较大，程序返回0，否则进行下一步操作。

3 大整数类型设计应用实例

在大整数编程算法当中，有一个简单而典型的问题，就是“兔子吃胡萝卜”问题，该问题经过改进后变为：兔子第一天得到a根胡萝卜，吃一部分剩下根。然后，又吃了一根，剩下b根。第二天，兔子继续吃，剩下根，在这个基础上又多吃一根。到了第十天只剩下一根胡萝卜，问题是第一天兔子获得了多少胡萝卜。

对待此问题，若利用c++数据类型，其中的long和int变量无法表示超出范围的数据，当运算到第五天，结果将强制溢出。因此，解决此问题，需要借助大整数工具，其测试代码过程大体为：引入自定义大整数类库，对该类型变量进行声明，并赋予初始值为1，利用for循环语句运算，输出为“第十天有<结果>根胡萝卜”，在短时间内，程序就可以完成计算并给出正确答案。

4 结语

综上所述，为了将C语言更好的应用在大整数问题的解决中，本文将基于C++的大整数类型的设计与实现作为主要研究内容，在对数据结构设计进行分析的基础上，从输入输出实现、比较算法实现、不同运算实现、运算符的重载等相关算法方面做出系统探究。研究结果表明，不同算法组成的C++类库，不仅能够应用于大整数实际问题解决中，还能够经修改后移植到其他操作系统。在未来，还需进一步加强对C++的大整数类型设计与实现研究，以此为其他语言环境下大数运算问题的解决提供思路。

Abstract：Large integer types provide a complete set of algorithms for operator overloading and four arithmetic operations. This paper focuses on the design and implementation of large integer types based on C ++. Starting with the design of data structures， this paper discusses the application examples of integer type design in combination with the realization of related algorithms.

Key Words：C language； big integer type； system design； operatorendprint