C++ 高效率整型大数运算项目优化—

C++ 高效率整型大数运算项目优化——内置类型存储与计算

一、前言
二、优化设计
- 分析
- 类的设计
三、设计实现
- 加法
- 减法
- 乘法
- - 对于 lint：
  - 对于 iint：
- 左移与右移
- - 左移
  - 右移
- 除法
- - 基本除法
  - 借用内置类型计算
  - - 第一种情况
    - 第二种情况
    - 其他情况
    - - 区间定位
      - 二分计数
      - 内置类型求近似值
  - 内置类型除法实现
四、项目源代码
- 对于 lint
- - 在 lint.h 中
  - 在 lint.cpp 中
- 对于 iint
- - 在 iint.h 中
  - 在 iint.cpp 中
五、空间与时间效率评估(VS2022 release环境)
- 空间上
- 时间上
- - 加法测试
  - 减法测试
  - 乘法测试
  - 除法测试
  - 测试源代码

一、前言

在这篇博客 C++ 整型大数运算(大整数运算)项目中，我们实现了大数运算的基本功能，不过计算效率太低，接下来我们可以借用内置类型来优化。

以下代码环境为 VS2022 C++。

二、优化设计

分析

使用 string 类型对每个数位都进行检查进位，这是计算效率低下的原因，另外使用的是 char 存储 0 ~ 9 ，比较浪费空间。

我们知道内置类型在不溢出的情况下会自己计算和处理进位，如果替代 char 类型计算，使用能表示越长数位的内置类型就越有优势，这里我采取使用的是 long long 和 int 类型。

但是当内置类型溢出前，我们需要设置一个检查点，让当前位的内置类型溢出值进位到下一个内置类型。

另外要注意，我们的设计会被内置类型所占的空间也就是能表示的范围影响，这里确定我们使用的 long long 类型所用空间是 8 字节，int 类型所用空间是 4 字节。

检查点的设置考虑到加减法的效率，long long 类型的上限设置为 1 × 10 ^ 18，数位数量有 18 个，则一个 long long 类型可以表示 [ 0, 10 ^ 18 ) 范围的数，int 类型上限设置为 1 × 10 ^ 9，数位数量有 9 个，则一个 int 类型可以表示 [ 0, 10 ^ 9 ) 范围的数：
在这里插入图片描述

类的设计

对于 int 类型的大数运算，类简称 iint，对于 long long 类型的大数运算，类简称 lint。存储数据考虑到会频繁访问，则使用 vector 存储较为合适。

在 iint.h 中：

namespace my
{// iint == Effective_big_int_integerclass iint{private:typedef int unit;					//类型封装enum unit_sign{positive = '+',negative = '-'};//2147483647static const unit upLimit			= 1000000000;static const signed char unitDigit	= 9;std::vector<unit> _nums;unit_sign _sign = positive;};
}

在 lint.h 中：

namespace my
{// lint == Effective_big_long_long_integerclass lint{protected:typedef long long unit;enum unit_sign{positive = '+',negative = '-'};static const signed char unitDigit	= 18;static const unit half				= 1000000000;			// 方便乘法分段计算static const unit upLimit			= 1000000000000000000;//9223372036854775807//18446744073709551615std::vector<unit> _nums;unit_sign _sign = positive;};
}

三、设计实现

这里实现的四则运算思想还是竖式计算，上篇博客已讲解，原理这里不赘述。

因为内置类型加减乘除的效率都高于我们自己实现的，则应该尽可能的使用内置类型的计算。

另外考虑到会频繁的使用加、减、乘法，这里存储数据的方式采用倒序存储优化翻转效率的损失。

加法

由于原理一样代码除了类名称都相同，这里就展示 lint，对于 lint：

	lint& lint::operator+=(const lint& number){if (_sign == positive && number._sign == negative){										number.signChange();*this -= number;number.signChange();return *this;}if (_sign == negative && number._sign == positive){										signChange();*this -= number;signChange();return *this;}size_t len1 = 0;size_t len2 = 0;unit next = 0;std::vector<unit> copy;copy.reserve(std::max(_nums.size(), number._nums.size()) + 1);while (len1 < _nums.size() || len2 < number._nums.size() || next > 0){unit num1 = len1 <		  _nums.size() ?		_nums[len1++] : 0;unit num2 = len2 < number._nums.size() ? number._nums[len2++] : 0;unit ret = num1 + num2 + next;next = ret / upLimit;				// 进位ret %= upLimit;						copy.push_back(ret);				// 当前位保存}_nums = std::move(copy);return *this;}

减法

减法同上，对于 lint：

	lint& lint::operator-=(const lint& number){if (_sign == positive && number._sign == negative){number.signChange();*this += number;number.signChange();return *this;}if (_sign == negative && number._sign == positive){signChange();*this += number;signChange();return *this;}int change = 1;						unit compare = justThanSize(number);	if (compare < 0){change = -1;					}else if (compare == 0){return *this = 0;}size_t len1 = 0;size_t len2 = 0;unit next = 0;std::vector<unit> copy;copy.reserve(std::max(_nums.size(), number._nums.size()));while (len1 < _nums.size() || len2 < number._nums.size()){unit num1 = len1 <		  _nums.size() ?		_nums[len1++] : 0;unit num2 = len2 < number._nums.size() ? number._nums[len2++] : 0;unit ret = change * (num1 - num2) + next;if (ret < 0){next = -1;ret += upLimit;}else{next = 0;}copy.push_back(ret);}while (copy.size() > 1 && copy[copy.size() - 1] == 0){copy.pop_back();}if (change == -1){signChange();}_nums = std::move(copy);return *this;}

乘法

上篇博客证明了两个不为 0 的整数位数数量为 x，y，乘积的位数数量 z ∈ [ x + y - 1，x + y ]，而我们能使用的最大内置类型为 8 字节的 unsigned long long。

对于 iint 来说，x = 9，y = 9，结果 z 一定不会超过 18，则 iint 的每个 unit 使用乘法时接收的类型可以使用 8 字节来接收而保证不会溢出。
对于 lint 来说，x = 18，y = 18，结果 z 在 8 字节中一定会溢出，则我们可以使用分段乘法来解决。

在这里插入图片描述

对于 lint：

	lint& lint::operator*=(const lint& number){if (*this == 0 || number == 0){return *this = 0;}if (_sign == positive && number._sign == negative){_sign = negative;}else if (_sign == negative && number._sign == negative){_sign = positive;}size_t len1 = 0;size_t len2 = 0;size_t index = 0;std::vector<unit> copy(_nums.size() + number._nums.size(), 0);while (len1 < _nums.size()){unit num1Up		= _nums[len1] / half;				unit num1Down	= _nums[len1] % half;unit next = 0;size_t i = index;for (size_t line = 0; line < number._nums.size(); ++line){unit num2Up		= number._nums[line] / half;unit num2Down	= number._nums[line] % half;unit ret = num1Down * num2Down + next;			// 不进位计算ret += (num1Up * num2Down % half) * half;		// 第一个半进位后半ret += (num1Down * num2Up % half) * half;		// 第二个半进位后半next = ret / upLimit;							// 进位next += num1Up * num2Up;						// 全进位next += (num1Up * num2Down / half);				// 第一个半进位前半next += (num1Down * num2Up / half);				// 第二个半进位前半ret %= upLimit;next += (copy[i] + ret) / upLimit;				// 边计算边进位copy[i] = (copy[i] + ret) % upLimit;++i;}while (next > 0){copy[i++] += next % upLimit;next /= upLimit;}++index;++len1;}if (copy.size() > 1 && copy[copy.size() - 1] == 0){copy.pop_back();}_nums = std::move(copy);return *this;}

对于 iint：

	iint& iint::operator*=(const iint& number){if (*this == 0 || number == 0){return *this = 0;}if (_sign == positive && number._sign == negative){_sign = negative;}else if (_sign == negative && number._sign == negative){_sign = positive;}size_t len1 = 0;size_t len2 = 0;size_t index = 0;std::vector<unit> copy(_nums.size() + number._nums.size(), 0);while (len1 < _nums.size()){size_t num1 = _nums[len1];size_t next = 0;size_t i = index;for (size_t line = 0; line < number._nums.size(); ++line){size_t num2 = number._nums[line];size_t ret = num1 * num2 + next;next = ret / upLimit;ret %= upLimit;next += (copy[i] + ret) / upLimit;copy[i] = (copy[i] + ret) % upLimit;++i;}while (next > 0){copy[i++] += next % upLimit;next /= upLimit;}++index;++len1;}if (copy.size() > 1 && copy[copy.size() - 1] == 0){copy.pop_back();}_nums = std::move(copy);return *this;}

左移与右移

由于我们实现的是内置类型封装的大数运算，左移和右移是可以借助内置类型实现的。

左移

由于有进位上限，左移增大会有检查进位消耗。
两者代码基本一样，这里只展示 lint，对于 lint：

	lint& lint::operator<<=(const long long n){for (int move = 0; move < n; ++move){unit next = 0;for (size_t i = 0; i < _nums.size(); ++i){_nums[i] = (_nums[i] << 1) + next;		next = _nums[i] / upLimit;				// 进位处理_nums[i] %= upLimit;		}if (next > 0){_nums.push_back(next);}}return *this;}

右移

由于整型会取整，右移不需要考虑小数，也不用进位，可以说它的效率在大数基本运算中是最高的。
同理于左移，对于 lint：

	lint& lint::operator>>=(const long long n){for (int move = 0; move < n; ++move){unit prev = _nums[_nums.size() - 1] & 1;				// 最高位的 unit 检查最后一个比特位是否有数_nums[_nums.size() - 1] >>= 1;							// 右移for (int i = _nums.size() - 2; i >= 0; --i){unit temp = _nums[i] & 1;							// 检查最后 bite 且保存_nums[i] = (_nums[i] >> 1) + (prev * upLimit >> 1);	// 右移 + 上一个 unit 下移的值prev = temp;										// 保存当前 unit 的下移值，用于下一个 unit}if (_nums.size() > 1 && _nums[_nums.size() - 1] == 0){_nums.pop_back();}}return *this;}

除法

基本除法

除法计算不能完全的使用内置类型，这里先实现上篇博客中的除法竖式计算。

因为内置类型的数都是存在一起的，一位一位的试商就需要取出来，lint 与 iint 代码上一样，这里展示 lint：

	lint& lint::operator/=(const lint& number){assert(number != 0);if (justThanSize(number) < 0){return *this = 0;}unit_sign sign1 = _sign;unit_sign sign2 = number._sign;int len1 =		  _nums.size() - 1;int len2 = number._nums.size() - 1;int condition = len1 - len2 + 1;int count = 0;std::string copy;copy.reserve((len1 - len2) * unitDigit + 1);while (len1 - len2 - count >= 0){for (int oneUnit = 1; oneUnit <= unitDigit; ++oneUnit){int left = -1;int right = 10;while (left + 1 < right){int mid = left + (right - left) / 2;if (justThanSize(number * mid * _pow(10, condition * unitDigit - oneUnit)) >= 0){left = mid;}else{right = mid;}}if (left != 0)					{if (_sign == number._sign){*this -= (left * number) * _pow(10, condition * unitDigit - oneUnit);}else{*this += (left * number) * _pow(10, condition * unitDigit - oneUnit);}}copy += (left + '0');}++count;--condition;}*this = std::move(lint(copy));if (sign1 == positive && sign2 == negative){_sign = negative;}else if (sign1 == negative && sign2 == negative){_sign = positive;}else{_sign = sign1;}return *this;}

借用内置类型计算

注意到除法不像乘法有分配律，但我们可以分情况讨论。

第一种情况

虽然不能将两个大数直接使用内置类型除法，但除数在内置类型范围内还是可以用的：
在这里插入图片描述
通过逐步拆解分子上的大数，我们可以使用大数 / 内置类型。

第二种情况

由于我们实现的大数一个 unit 存储的是 10 的整数次幂，可以直接删掉或增加 vector 的元素达到除或乘 10 ^ n 的效果，而且因为是整型不用考虑小数点后面的数位，实现上是简单的，对于 lint：

		void _downTen(long long n){_nums.erase(_nums.begin(), _nums.begin() + n / unitDigit);*this /= _pow(10, n % unitDigit);}void _upTen(long long n){_nums.insert(_nums.begin(), n / unitDigit, 0);*this *= _pow(10, n % unitDigit);}

则有这种情况：
在这里插入图片描述

先计算 a / 10 ^ n，这等价将 long long 大数 a 的尾数元素直接删除 n / 18 个，再除以 10 ^ (n % 18) 这个内置类型，此时 b 也为内置类型，两者可以借用第一种情况。

但要注意，若 c != b × 10 ^ n 的话，计算是有误差的，也就是说只有高位上有数，且在内置类型范围内才可正确计算：
在这里插入图片描述
检查高位操作也简单，先将高位内置类型保存，再 - 1，会向上借 1，如果借到了内置类型，说明除了高位其他位为 0，则 - 1 前后两者不相等，再 + 1，将数还原即可：

		bool _isJustHead18() const{if (_nums.size() == 1){return true;}unit Head = _getHead18();*((lint*)this) -= 1;bool just = !(Head == _getHead18());*((lint*)this) += 1;return just;}

其他情况

其他情况内置类型就求不出精确值了，相对于使用除法的竖式计算，使用二分查找在代码上要容易实现且效率高（只用O(logN)次乘法，不用被除数 - 中间的试商值和额外的乘法）。

但是要注意，我们需要对二分查找的左右区间进行定位，若直接使用 left = 1，right = *this 这种方法，当 number(除数) 接近 this(被除数) 时，二分查找会出现 (this / 2) × this 这种无意义的消耗。

接下来对于二分查找 left 和 right 区间进行分析。

区间定位

这里需要先证明商的位数个数：
在这里插入图片描述
所以当被除数大于除数且都为整数，被除数、除数位数个数为 x、y，则商整数的位数个数范围为 [ x - y，x - y + 1 ]。

我们可以用这个原理来进行区间定位，则商的答案在 [ 10 ^ (x - y - 1)，10 ^ (x - y + 1) )，可以优化一些不必要的查找。

二分计数

除法计数是除法的基本思想，被除数一直减除数，减到被除数小于除数，减的次数是商，余数就是剩余留下的数。

商的区间使用区间定位在 [ 10 ^ (x - y - 1)，10 ^ (x - y + 1) )内，二分计数可以定位到 [ 2 ^ n，2 ^ (n + 1) ) 内。

当除数接近被除数时，使用二分除法计数定位区间与区间定位效率上相差无几的，并且可以减少二分查找的乘法次数：
在这里插入图片描述
这里使用右移运算符，定位计算会很快。当然，number 远远小于 *this 时，它的定位效率为 O(log N)，相对于区间定位的O(1) ，效率过低了。

内置类型求近似值

注意到 long long 类型使用除法可能会溢出，但是转成 unsigned long long 类型(也就是 size_t) 是可以刚好容纳的：
在这里插入图片描述
则我们可以使用第二种情况来求近似值：

内置类型求近似值所确定的区间是在原来区间定位的基础上除以 10 ^ 18 (lint的) 次方（这里只是估算，没有确切探究），即 [ 10 ^ (x - y - 1)，10 ^ (x - y + 1) ) => [ 10 ^ (x - y - 1 - 18)， 10 ^ (x - y + 1 - 18) )，相当于减少二分查找 60 次左右的乘法。

内置类型除法实现

使用内置类型求近似值就不用区间定位和二分计数了，而且要注意，int 也应该使用 long long 型的内置除法，但这里我没有实现，则对于 iint 超过 10 ^ 9 但在 10 ^ 18 之内，iint 使用二分查找的效率明显不如 lint 使用内置类型的。

对于 lint：

	lint& lint::operator/=(const lint& number)		{assert(number != 0);if (justThanSize(number) < 0){return *this = 0;}unit_sign sign1 = _sign;unit_sign sign2 = number._sign;size_t digit1 =		   digitCount();			// 统计位数数量										size_t digit2 = number.digitCount();size_t num2 = number._getHead18();				// 最高且有效的 18 位bool isHead18 = number._isJustHead18();			// 判断是否是有效位在前 18 位lint tempBinaryThan = 0;if (number._nums.size() != 1)					// 当 number 不为内置类型时，对应第二种情况{if (isHead18 == false)						// 为假则走二分计算，会用到 *this 的精确值进行计算{tempBinaryThan = *this;}downTen(number.digitCount() - unitDigit);	// 降 10 ^ ndigit1 -= number.digitCount() - unitDigit;	digit2 = unitDigit;							// number 现在也降的话会消耗资源，这是没必要的，直接改 digit2 即可 }size_t len1 = _nums.size() - 1;size_t len2 = digit2 / unitDigit - (digit2 % unitDigit == 0 ? 1 : 0);std::vector<unit> copy((digit1 - digit2) / unitDigit + 1, 0);// 先将高位计算完copy[(digit1 - digit2) / unitDigit] = _nums[len1] / num2;size_t prev = _nums[len1] % num2;				// 高位的余数for (int i = len1 - 1; i >= 0; --i){size_t ans = 0;								// 试商结果不会超过 unsigned long long 长度for (int j = 17; j >= 0; --j)				// 一个一个 long long 类型的 unit 去取{size_t num1 = prev * 10 + _nums[i] / (size_t)std::pow(10, j) % 10;ans = ans * 10 + num1 / num2;prev = num1 % num2;						// 高位余数保留到下一位}copy[i - len2] = ans;}if (copy.size() > 1 && copy[copy.size() - 1] == 0){copy.pop_back();}// 到达这里有三种情况：// 1. number 为内置类型// 2. number 有效位在前 18 位// 3. number 有效为不止 18 个，计算有误差if (isHead18 == true)						// 1 和 2 可以归类为有效位在前 18 位{_nums = std::move(copy);}else										// 3 走二分精确计算{lint right = std::move(copy);			// 右区间lint left = *this / (num2 + 1);			// 左区间 当 num2 = 999999999999999999 + 1 = 10 ^ 18，走的是第 2 种情况，否则走第 1 种情况while (left < right){lint mid = (((left + right) += 1) >>= 1);if (mid * number <= tempBinaryThan)	// 这里就算保留 *this 减少损耗，在 left 计算时反而会有更多消耗{									// 而且这样实现对 copy 获取内置类型答案的代码实现会更简单，不用考虑对齐left = std::move(mid);}else{right = std::move(mid -= 1);}}_nums = std::move(left._nums);}if (sign1 == positive && sign2 == negative){_sign = negative;}else if (sign1 == negative && sign2 == negative){_sign = positive;}else{_sign = sign1;}return *this;}

对于 iint：

	iint& iint::operator/=(const iint& number){assert(number != 0);if (justThanSize(number) < 0){return *this = 0;}unit_sign sign1 = _sign;unit_sign sign2 = number._sign;size_t digit1 = digitCount();												size_t digit2 = number.digitCount();size_t num2 = number._getHead9();				// 前 9 位			bool isHead9 = number._isJustHead9();			// 判断前 9 位iint tempBinaryThan = 0;if (number._nums.size() != 1)					{if (isHead9 == false)						{tempBinaryThan = *this;}downTen(number.digitCount() - unitDigit);	digit1 -= number.digitCount() - unitDigit;digit2 = unitDigit;							 }size_t len1 = _nums.size() - 1;size_t len2 = digit2 / unitDigit - (digit2 % unitDigit == 0 ? 1 : 0);std::vector<unit> copy((digit1 - digit2) / unitDigit + 1, 0);copy[(digit1 - digit2) / unitDigit] = _nums[len1] / num2;size_t prev = _nums[len1] % num2;				for (int i = len1 - 1; i >= 0; --i){size_t ans = 0;								for (int j = unitDigit - 1; j >= 0; --j)	 {size_t num1 = prev * 10 + _nums[i] / (size_t)std::pow(10, j) % 10;ans = ans * 10 + num1 / num2;prev = num1 % num2;						}copy[i - len2] = ans;}if (copy.size() > 1 && copy[copy.size() - 1] == 0){copy.pop_back();}if (isHead9 == true)						{_nums = std::move(copy);}else										{iint right = std::move(copy);			iint left = *this / (num2 + 1);			while (left < right){iint mid = (((left + right) += 1) >>= 1);if (mid * number <= tempBinaryThan)	{									left = std::move(mid);}else{right = std::move(mid -= 1);}}_nums = std::move(left._nums);}if (sign1 == positive && sign2 == negative){_sign = negative;}else if (sign1 == negative && sign2 == negative){_sign = positive;}else{_sign = sign1;}return *this;}

四、项目源代码

对于 lint

在 lint.h 中

#pragma once#include <vector>
#include <string>
#include <iostream>namespace my
{// lint == Effective_big_long_long_integerclass lint{protected:typedef long long unit;enum unit_sign{positive = '+',negative = '-'};static const signed char unitDigit	= 18;static const unit half				= 1000000000;static const unit upLimit			= 1000000000000000000;//9223372036854775807//18446744073709551615std::vector<unit> _nums;unit_sign _sign = positive;private:bool _isJustHead18() const{if (_nums.size() == 1){return true;}unit Head = _getHead18();*((lint*)this) -= 1;bool just = !(Head == _getHead18());*((lint*)this) += 1;return just;}size_t _getHead18() const{if (_nums.size() == 1){return _nums[0];}unit HeadNum = _nums[_nums.size() - 1];unit temp = _nums[_nums.size() - 2];int rest = unitDigit - digitCountUnit(HeadNum);size_t setDigit = upLimit / 10;while (rest){HeadNum = HeadNum * 10 + temp / setDigit % 10;setDigit /= 10;--rest;}return HeadNum;}void _downTen(long long n){_nums.erase(_nums.begin(), _nums.begin() + n / unitDigit);*this /= _pow(10, n % unitDigit);}void _upTen(long long n){_nums.insert(_nums.begin(), n / unitDigit, 0);*this *= _pow(10, n % unitDigit);}void signChange() const{int* change = (int*)(&_sign);*change = (_sign == positive ? negative : positive);}unit justThanSize(const lint& number) const;static lint _pow(const lint& number, long long index);static unit_sign signExpressSolve(const std::string& str);static size_t signLastIndex(const std::string& str);static unit atoi(const std::string& number, int left, int right){unit sum = 0;for (int i = left; i < right; ++i){sum = sum * 10 + (number[i] - '0');}return sum;}static size_t digitCountUnit(unit n){size_t count = 0;for (size_t temp = 1; temp <= n; temp *= 10){++count;}return count;}public:std::string to_string() const;void downTen(long long n){if (n <= 0){return;}_downTen(n);}void upTen(long long n){if (n <= 0){return;}_upTen(n);}size_t digitCount() const{return digitCountUnit(_nums[_nums.size() - 1]) + (_nums.size() - 1) * unitDigit;}static lint pow(const lint& number, long long index){if (index == 0){return 1;}if (number == 0 || index < 0){return 0;}return _pow(number, index);}public:void swap(lint& number){std::swap(_nums, number._nums);std::swap(_sign, number._sign);}lint(lint&& number) = default;lint(const lint& number) = default;lint& operator=(const lint& number) = default;lint& operator=(lint&& number) = default;lint(const char* number){*this = std::string(number);}lint(const std::string& number){_sign = signExpressSolve(number);int downLimit = signLastIndex(number);_nums.reserve(number.size() / unitDigit + 1);for (int len = number.size(); len > downLimit + 1; len -= unitDigit){_nums.push_back(atoi(number, (len - unitDigit >= 0 ? len - unitDigit : 0), len));}while (_nums.size() > 1 && _nums[_nums.size() - 1] == 0){_nums.pop_back();}}lint(const std::vector<unit>&& number){_nums = std::move(number);}lint(unsigned long long number):_sign(positive){if (number >= upLimit){_nums.push_back(number % upLimit);number /= upLimit;}_nums.push_back(number);}lint(const long long number = 0):_sign(number < 0 ? negative : positive){unit temp = number;if (temp < 0){temp = -temp;}unit next = temp / upLimit;_nums = { temp % upLimit };if (next > 0){_nums.push_back(next);}}lint(const unsigned int number){*this = lint((long long)number);}lint(const int number){*this = lint((long long)number);}lint(const unsigned short number){*this = lint((long long)number);}lint(const short number){*this = lint((long long)number);}lint(const unsigned char number){*this = lint((long long)number);}lint(const signed char number){*this = lint((long long)number);}public:lint& operator+=(const lint& number);lint& operator-=(const lint& number);lint& operator*=(const lint& number);lint& operator/=(const lint& number);lint& operator%=(const lint& number);lint& operator<<=(const long long n);lint& operator>>=(const long long n);public:lint operator-() const{lint temp = *this;temp.signChange();return temp;}lint& operator--(){return *this -= 1;}lint operator--(int){lint temp = *this;--(*this);return temp;}lint operator+() const{return *this;}lint& operator++(){return *this += 1;}lint operator++(int){lint temp = *this;++(*this);return temp;}public:friend bool operator==(const lint& number1, const lint& number2);friend bool operator< (const lint& number1, const lint& number2);friend std::ostream& operator<<(std::ostream& out, const lint& number);friend std::istream& operator>>(std::istream& in, lint& number);};lint operator+(const lint& number1, const lint& number2);lint operator-(const lint& number1, const lint& number2);lint operator*(const lint& number1, const lint& number2);lint operator/(const lint& number1, const lint& number2);lint operator%(const lint& number1, const lint& number2);lint operator<<(const lint& number1, const long long n);lint operator>>(const lint& number1, const long long n);bool operator<=(const lint& number1, const lint& number2);bool operator>(const lint& number1, const lint& number2);bool operator>=(const lint& number1, const lint& number2);bool operator!=(const lint& number1, const lint& number2);bool operator!(const lint& number);
}

在 lint.cpp 中

#include "lint.h"
#include <utility>
#include <cassert>
#include <iomanip>namespace my
{std::string lint::to_string() const{std::string ans;if (_sign == negative){ans += '-';}ans += std::to_string(_nums[_nums.size() - 1]);for (long long i = _nums.size() - 2; i >= 0; --i){int count = unitDigit - digitCountUnit(_nums[i]);ans += std::string(count, '0');if (_nums[i] != 0){ans += std::to_string(_nums[i]);}}return ans;}size_t lint::signLastIndex(const std::string& str){size_t index = -1;for (auto e : str){if (e == negative || e == positive){++index;}else{break;}}return index;}lint::unit_sign lint::signExpressSolve(const std::string& str){signed char sign = 1;for (auto e : str){if (e == negative){sign = -sign;}else if (e == positive){;}else{break;}}return sign == 1 ? positive : negative;}lint::unit lint::justThanSize(const lint& number) const{if (_nums.size() != number._nums.size()){return _nums.size() - number._nums.size();}for (long long i = _nums.size() - 1; i >= 0; --i){if (_nums[i] != number._nums[i]){return _nums[i] - number._nums[i];}}return 0;}lint lint::_pow(const lint& number, long long index){if (index == 0){return 1;}lint temp = _pow(number, index / 2);if (index % 2 == 0){return temp *= temp;}else{return (temp *= temp) *= number;}}lint& lint::operator+=(const lint& number){if (_sign == positive && number._sign == negative){number.signChange();*this -= number;number.signChange();return *this;}if (_sign == negative && number._sign == positive){signChange();*this -= number;signChange();return *this;}size_t len1 = 0;size_t len2 = 0;unit next = 0;std::vector<unit> copy;copy.reserve(std::max(_nums.size(), number._nums.size()) + 1);while (len1 < _nums.size() || len2 < number._nums.size() || next > 0){unit num1 = len1 < _nums.size() ? _nums[len1++] : 0;unit num2 = len2 < number._nums.size() ? number._nums[len2++] : 0;unit ret = num1 + num2 + next;next = ret / upLimit;				// 进位ret %= upLimit;copy.push_back(ret);				// 当前位保存}_nums = std::move(copy);return *this;}lint& lint::operator-=(const lint& number){if (_sign == positive && number._sign == negative){number.signChange();*this += number;number.signChange();return *this;}if (_sign == negative && number._sign == positive){signChange();*this += number;signChange();return *this;}int change = 1;unit compare = justThanSize(number);if (compare < 0){change = -1;}else if (compare == 0){return *this = 0;}size_t len1 = 0;size_t len2 = 0;unit next = 0;std::vector<unit> copy;copy.reserve(std::max(_nums.size(), number._nums.size()));while (len1 < _nums.size() || len2 < number._nums.size()){unit num1 = len1 < _nums.size() ? _nums[len1++] : 0;unit num2 = len2 < number._nums.size() ? number._nums[len2++] : 0;unit ret = change * (num1 - num2) + next;if (ret < 0){next = -1;ret += upLimit;}else{next = 0;}copy.push_back(ret);}while (copy.size() > 1 && copy[copy.size() - 1] == 0){copy.pop_back();}if (change == -1){signChange();}_nums = std::move(copy);return *this;}lint& lint::operator*=(const lint& number){if (*this == 0 || number == 0){return *this = 0;}if (_sign == positive && number._sign == negative){_sign = negative;}else if (_sign == negative && number._sign == negative){_sign = positive;}size_t len1 = 0;size_t len2 = 0;size_t index = 0;std::vector<unit> copy(_nums.size() + number._nums.size(), 0);while (len1 < _nums.size()){unit num1Up = _nums[len1] / half;unit num1Down = _nums[len1] % half;unit next = 0;size_t i = index;for (size_t line = 0; line < number._nums.size(); ++line){unit num2Up = number._nums[line] / half;unit num2Down = number._nums[line] % half;unit ret = num1Down * num2Down + next;			// 不进位计算ret += (num1Up * num2Down % half) * half;		// 第一个半进位后半ret += (num1Down * num2Up % half) * half;		// 第二个半进位后半next = ret / upLimit;							// 进位next += num1Up * num2Up;						// 全进位next += (num1Up * num2Down / half);				// 第一个半进位前半next += (num1Down * num2Up / half);				// 第二个半进位前半ret %= upLimit;next += (copy[i] + ret) / upLimit;				// 边计算边进位copy[i] = (copy[i] + ret) % upLimit;++i;}while (next > 0){copy[i++] += next % upLimit;next /= upLimit;}++index;++len1;}if (copy.size() > 1 && copy[copy.size() - 1] == 0){copy.pop_back();}_nums = std::move(copy);return *this;}lint& lint::operator/=(const lint& number){assert(number != 0);if (justThanSize(number) < 0){return *this = 0;}unit_sign sign1 = _sign;unit_sign sign2 = number._sign;size_t digit1 = digitCount();					// 统计位数数量										size_t digit2 = number.digitCount();size_t num2 = number._getHead18();				// 最高且有效的 18 位bool isHead18 = number._isJustHead18();			// 判断是否是有效位在前 18 位lint tempBinaryThan = 0;if (number._nums.size() != 1)					// 当 number 不为内置类型时，对应第二种情况{if (isHead18 == false)						// 为假则走二分计算，会用到 *this 的精确值进行计算{tempBinaryThan = *this;}downTen(number.digitCount() - unitDigit);	// 降 10 ^ ndigit1 -= number.digitCount() - unitDigit;digit2 = unitDigit;							// number 现在也降的话会消耗资源，这是没必要的，直接改 digit2 即可 }size_t len1 = _nums.size() - 1;size_t len2 = digit2 / unitDigit - (digit2 % unitDigit == 0 ? 1 : 0);std::vector<unit> copy((digit1 - digit2) / unitDigit + 1, 0);// 先将高位计算完copy[(digit1 - digit2) / unitDigit] = _nums[len1] / num2;size_t prev = _nums[len1] % num2;				// 高位的余数for (int i = (long long)len1 - 1; i >= 0; --i){size_t ans = 0;								// 试商结果不会超过 unsigned long long 长度for (int j = unitDigit - 1; j >= 0; --j)				// 一个一个 long long 类型的 unit 去取{size_t num1 = prev * 10 + _nums[i] / (size_t)std::pow(10, j) % 10;ans = ans * 10 + num1 / num2;prev = num1 % num2;						// 高位余数保留到下一位}copy[i - len2] = ans;}if (copy.size() > 1 && copy[copy.size() - 1] == 0){copy.pop_back();}// 到达这里有三种情况：// 1. number 为内置类型// 2. number 有效位在前 18 位// 3. number 有效为不止 18 个，计算有误差if (isHead18 == true)						// 1 和 2 可以归类为有效位在前 18 位{_nums = std::move(copy);}else										// 3 走二分精确计算{lint right = std::move(copy);			// 右区间lint left = *this / (num2 + 1);			// 左区间 当 num2 = 999999999999999999 + 1 = 10 ^ 18，走的是第 2 种情况，否则走第 1 种情况while (left < right){lint mid = (((left + right) += 1) >>= 1);if (mid * number <= tempBinaryThan)	// 这里就算保留 *this 减少损耗，在 left 计算时反而会有更多消耗{									// 而且这样实现对 copy 获取内置类型答案的代码实现会更简单，不用考虑对齐left = std::move(mid);}else{right = std::move(mid -= 1);}}_nums = std::move(left._nums);}if (sign1 == positive && sign2 == negative){_sign = negative;}else if (sign1 == negative && sign2 == negative){_sign = positive;}else{_sign = sign1;}return *this;}lint& lint::operator%=(const lint& number){lint temp = *this;temp /= number;return *this -= temp * number;}lint& lint::operator<<=(const long long n){for (int move = 0; move < n; ++move){unit next = 0;for (size_t i = 0; i < _nums.size(); ++i){_nums[i] = (_nums[i] << 1) + next;next = _nums[i] / upLimit;				// 进位处理_nums[i] %= upLimit;}if (next > 0){_nums.push_back(next);}}return *this;}lint& lint::operator>>=(const long long n){for (int move = 0; move < n; ++move){unit prev = _nums[_nums.size() - 1] & 1;				// 最高位的 unit 检查最后一个比特位是否有数_nums[_nums.size() - 1] >>= 1;							// 右移for (int i = _nums.size() - 2; i >= 0; --i){unit temp = _nums[i] & 1;							// 检查最后 bite 且保存_nums[i] = (_nums[i] >> 1) + (prev * upLimit >> 1);	// 右移 + 上一个 unit 下移的值prev = temp;										// 保存当前 unit 的下移值，用于下一个 unit}if (_nums.size() > 1 && _nums[_nums.size() - 1] == 0){_nums.pop_back();}}return *this;}lint operator+(const lint& number1, const lint& number2){return lint(number1) += number2;}lint operator-(const lint& number1, const lint& number2){return lint(number1) -= number2;}lint operator*(const lint& number1, const lint& number2){return lint(number1) *= number2;}lint operator/(const lint& number1, const lint& number2){return lint(number1) /= number2;}lint operator%(const lint& number1, const lint& number2){return lint(number1) %= number2;}lint operator<<(const lint& number, const long long n){return lint(number) <<= n;}lint operator>>(const lint& number, const long long n){return lint(number) >>= n;}bool operator==(const lint& number1, const lint& number2){if (number1._sign != number2._sign){return false;}if (number1._nums.size() != number2._nums.size() || number1.justThanSize(number2) != 0){return false;}return true;}bool operator< (const lint& number1, const lint& number2){if (number1._sign == lint::positive && number2._sign == lint::negative){return false;}if (number1._sign == lint::negative && number2._sign == lint::positive){return true;}lint::unit lessNum = number1.justThanSize(number2);if (lessNum < 0){return number1._sign == lint::positive ? true : false;}else{return number1._sign == lint::positive ? false : true;}}bool operator>=(const lint& number1, const lint& number2){return !(number1 < number2);}bool operator!=(const lint& number1, const lint& number2){return !(number1 == number2);}bool operator<=(const lint& number1, const lint& number2){return number1 < number2 || number1 == number2;}bool operator> (const lint& number1, const lint& number2){return !(number1 <= number2);}bool operator! (const lint& number){return number == 0;}std::ostream& operator<<(std::ostream& out, const lint& number){if (number._sign == lint::negative){out << '-';}out << number._nums[number._nums.size() - 1];for (int i = number._nums.size() - 2; i >= 0; --i){out << std::setw(lint::unitDigit) << std::setfill('0') << number._nums[i];}return out;}std::istream& operator>>(std::istream& in, lint& number){std::string temp;in >> temp;number = temp;return in;}
}

对于 iint

在 iint.h 中

#pragma once#include <vector>
#include <iostream>
#include <string>namespace my
{// iint == Effective_big_int_integerclass iint{private:typedef int unit;enum unit_sign{positive = '+',negative = '-'};//2147483647static const unit upLimit			= 1000000000;static const signed char unitDigit	= 9;std::vector<unit> _nums;unit_sign _sign = positive;private:void signChange() const{int* change = (int*)(&_sign);*change = (_sign == positive ? negative : positive);}static iint _pow(const iint& number, long long index);unit justThanSize(const iint& number) const;static unit_sign signExpressSolve(const std::string& str);static size_t signLastIndex(const std::string& str);static unit atoi(const std::string& number, int left, int right){unit sum = 0;for (int i = left; i < right; ++i){sum = sum * 10 + (number[i] - '0');}return sum;}static size_t digitCountUnit(unit n){size_t count = 0;for (size_t temp = 1; temp <= n; temp *= 10){++count;}return count;}size_t _getHead9() const{if (_nums.size() == 1){return _nums[0];}unit HeadNum = _nums[_nums.size() - 1];unit temp = _nums[_nums.size() - 2];int rest = unitDigit - digitCountUnit(HeadNum);size_t setDigit = upLimit / 10;while (rest){HeadNum = HeadNum * 10 + temp / setDigit % 10;setDigit /= 10;--rest;}return HeadNum;}bool _isJustHead9() const{if (_nums.size() == 1){return true;}unit Head = _getHead9();*((iint*)this) -= 1;bool just = !(Head == _getHead9());*((iint*)this) += 1;return just;}void _downTen(long long n){_nums.erase(_nums.begin(), _nums.begin() + n / unitDigit);*this /= _pow(10, n % unitDigit);}void _upTen(long long n){_nums.insert(_nums.begin(), n / unitDigit, 0);*this *= _pow(10, n % unitDigit);}public:std::string to_string() const;size_t digitCount() const{return digitCountUnit(_nums[_nums.size() - 1]) + (_nums.size() - 1) * unitDigit;}void downTen(long long n){if (n <= 0){return;}_downTen(n);}void upTen(long long n){if (n <= 0){return;}_upTen(n);}static iint pow(const iint& number, long long index){if (index == 0){return 1;}if (number == 0 || index < 0){return 0;}return _pow(number, index);}public:void swap(iint& number){std::swap(_nums, number._nums);std::swap(_sign, number._sign);}iint(iint&& number)					= default;iint(const iint& number)			= default;iint& operator=(const iint& number) = default;iint& operator=(iint&& number)		= default;iint(const char* number){*this = std::string(number);}iint(const std::string& number){_sign = signExpressSolve(number);int downLimit = signLastIndex(number);_nums.reserve(number.size() / unitDigit + 1);for (int len = number.size(); len > downLimit + 1; len -= unitDigit){_nums.push_back(atoi(number, (len - unitDigit >= 0 ? len - unitDigit : 0), len));}while (_nums.size() > 1 && _nums[_nums.size() - 1] == 0){_nums.pop_back();}}iint(const std::vector<unit>&& number){_nums = std::move(number);}iint(unsigned long long number):_sign(positive){_nums.push_back(number % upLimit);if (number >= upLimit){number /= upLimit;_nums.push_back(number % upLimit);number /= upLimit;if (number != 0){_nums.push_back(number % upLimit);}}}iint(const long long number = 0):_sign(number < 0 ? negative : positive){long long temp = number < 0 ? -number : number;unit prevHead = temp / upLimit / upLimit;unit prevNext = temp / upLimit % upLimit;_nums.push_back(temp % upLimit);if (prevHead > 0){_nums.push_back(prevNext);_nums.push_back(prevHead);}else if (prevNext > 0){_nums.push_back(prevNext);}}iint(const unsigned int number){*this = iint((long long)number);}iint(const int number){*this = iint((long long)number);}iint(const unsigned short number){*this = iint((long long)number);}iint(const short number){*this = iint((long long)number);}iint(const unsigned char number){*this = iint((long long)number);}iint(const signed char number){*this = iint((long long)number);}public:iint& operator+=(const iint& number);iint& operator-=(const iint& number);iint& operator*=(const iint& number);iint& operator/=(const iint& number);iint& operator%=(const iint& number);iint& operator<<=(const long long n);iint& operator>>=(const long long n);public:iint operator-() const{iint temp = *this;temp.signChange();return temp;}iint& operator--(){return *this -= 1;}iint operator--(int){iint temp = *this;--(*this);return temp;}iint operator+() const{return *this;}iint& operator++(){return *this += 1;}iint operator++(int){iint temp = *this;++(*this);return temp;}public:friend bool operator==(const iint& number1, const iint& number2);friend bool operator< (const iint& number1, const iint& number2);friend std::ostream& operator<<(std::ostream& out, const iint& number);friend std::istream& operator>>(std::istream& in, iint& number);};iint operator+(const iint& number1, const iint& number2);iint operator-(const iint& number1, const iint& number2);iint operator*(const iint& number1, const iint& number2);iint operator/(const iint& number1, const iint& number2);iint operator%(const iint& number1, const iint& number2);iint operator<<(const iint& number1, const long long n);iint operator>>(const iint& number1, const long long n);bool operator<=(const iint& number1, const iint& number2);bool operator>(const iint& number1, const iint& number2);bool operator>=(const iint& number1, const iint& number2);bool operator!=(const iint& number1, const iint& number2);bool operator!(const iint& number);
}

在 iint.cpp 中

#include "iint.h"
#include <utility>
#include <cassert>
#include <iomanip>namespace my
{std::string iint::to_string() const{std::string ans;if (_sign == negative){ans += '-';}ans += std::to_string(_nums[_nums.size() - 1]);for (long long i = _nums.size() - 2; i >= 0; --i){int count = unitDigit - digitCountUnit(_nums[i]);ans += std::string(count, '0');if (_nums[i] != 0){ans += std::to_string(_nums[i]);}}return ans;}iint iint::_pow(const iint& number, long long index){if (index == 0){return 1;}iint temp = _pow(number, index / 2);if (index % 2 == 0){return temp *= temp;}else{return (temp *= temp) *= number;}}iint::unit iint::justThanSize(const iint& number) const{if (_nums.size() != number._nums.size()){return _nums.size() - number._nums.size();}for (long long i = _nums.size() - 1; i >= 0; --i){if (_nums[i] != number._nums[i]){return _nums[i] - number._nums[i];}}return 0;}size_t iint::signLastIndex(const std::string& str){size_t index = -1;for (auto e : str){if (e == negative || e == positive){++index;}else{break;}}return index;}iint::unit_sign iint::signExpressSolve(const std::string& str){signed char sign = 1;for (auto e : str){if (e == negative){sign = -sign;}else if (e == positive){;}else{break;}}return sign == 1 ? positive : negative;}iint& iint::operator+=(const iint& number){if (_sign == positive && number._sign == negative){number.signChange();*this -= number;number.signChange();return *this;}if (_sign == negative && number._sign == positive){signChange();*this -= number;signChange();return *this;}size_t len1 = 0;size_t len2 = 0;unit next = 0;std::vector<unit> copy;copy.reserve(std::max(_nums.size(), number._nums.size()) + 1);while (len1 < _nums.size() || len2 < number._nums.size() || next > 0){unit num1 = len1 <		  _nums.size() ?		_nums[len1++] : 0;unit num2 = len2 < number._nums.size() ? number._nums[len2++] : 0;unit ret = num1 + num2 + next;next = ret / upLimit;ret %= upLimit;copy.push_back(ret);}_nums = std::move(copy);return *this;}iint& iint::operator-=(const iint& number){if (_sign == positive && number._sign == negative){number.signChange();*this += number;number.signChange();return *this;}if (_sign == negative && number._sign == positive){signChange();*this += number;signChange();return *this;}int change = 1;unit compare = justThanSize(number);if (compare < 0){change = -1;}else if (compare == 0){return *this = 0;}size_t len1 = 0;size_t len2 = 0;unit next = 0;std::vector<unit> copy;copy.reserve(std::max(_nums.size(), number._nums.size()));while (len1 < _nums.size() || len2 < number._nums.size()){unit num1 = len1 < _nums.size() ? _nums[len1++] : 0;unit num2 = len2 < number._nums.size() ? number._nums[len2++] : 0;unit ret = change * (num1 - num2) + next;if (ret < 0){next = -1;ret += upLimit;}else{next = 0;}copy.push_back(ret);}while (copy.size() > 1 && copy[copy.size() - 1] == 0){copy.pop_back();}if (change == -1){signChange();}_nums = std::move(copy);return *this;}iint& iint::operator*=(const iint& number){if (*this == 0 || number == 0){return *this = 0;}if (_sign == positive && number._sign == negative){_sign = negative;}else if (_sign == negative && number._sign == negative){_sign = positive;}size_t len1 = 0;size_t len2 = 0;size_t index = 0;std::vector<unit> copy(_nums.size() + number._nums.size(), 0);while (len1 < _nums.size()){size_t num1 = _nums[len1];size_t next = 0;size_t i = index;for (size_t line = 0; line < number._nums.size(); ++line){size_t num2 = number._nums[line];size_t ret = num1 * num2 + next;next = ret / upLimit;ret %= upLimit;next += (copy[i] + ret) / upLimit;copy[i] = (copy[i] + ret) % upLimit;++i;}while (next > 0){copy[i++] += next % upLimit;next /= upLimit;}++index;++len1;}if (copy.size() > 1 && copy[copy.size() - 1] == 0){copy.pop_back();}_nums = std::move(copy);return *this;}iint& iint::operator/=(const iint& number){assert(number != 0);if (justThanSize(number) < 0){return *this = 0;}unit_sign sign1 = _sign;unit_sign sign2 = number._sign;size_t digit1 = digitCount();												size_t digit2 = number.digitCount();size_t num2 = number._getHead9();				// 前 9 位			bool isHead9 = number._isJustHead9();			// 判断前 9 位iint tempBinaryThan = 0;if (number._nums.size() != 1)					{if (isHead9 == false)						{tempBinaryThan = *this;}downTen(number.digitCount() - unitDigit);	digit1 -= number.digitCount() - unitDigit;digit2 = unitDigit;							 }size_t len1 = _nums.size() - 1;size_t len2 = digit2 / unitDigit - (digit2 % unitDigit == 0 ? 1 : 0);std::vector<unit> copy((digit1 - digit2) / unitDigit + 1, 0);copy[(digit1 - digit2) / unitDigit] = _nums[len1] / num2;size_t prev = _nums[len1] % num2;				for (int i = len1 - 1; i >= 0; --i){size_t ans = 0;								for (int j = unitDigit - 1; j >= 0; --j)	 {size_t num1 = prev * 10 + _nums[i] / (size_t)std::pow(10, j) % 10;ans = ans * 10 + num1 / num2;prev = num1 % num2;						}copy[i - len2] = ans;}if (copy.size() > 1 && copy[copy.size() - 1] == 0){copy.pop_back();}if (isHead9 == true)						{_nums = std::move(copy);}else										{iint right = std::move(copy);			iint left = *this / (num2 + 1);			while (left < right){iint mid = (((left + right) += 1) >>= 1);if (mid * number <= tempBinaryThan)	{									left = std::move(mid);}else{right = std::move(mid -= 1);}}_nums = std::move(left._nums);}if (sign1 == positive && sign2 == negative){_sign = negative;}else if (sign1 == negative && sign2 == negative){_sign = positive;}else{_sign = sign1;}return *this;}iint& iint::operator%=(const iint& number){iint temp = *this;temp /= number;return *this -= temp * number;}iint& iint::operator<<=(const long long n){for (int move = 0; move < n; ++move){unit next = 0;for (size_t i = 0; i < _nums.size(); ++i){_nums[i] = (_nums[i] << 1) + next;next = _nums[i] / upLimit;_nums[i] %= upLimit;}if (next > 0){_nums.push_back(next);}}return *this;}iint& iint::operator>>=(const long long n){for (int move = 0; move < n; ++move){unit prev = _nums[_nums.size() - 1] & 1;_nums[_nums.size() - 1] >>= 1;for (int i = _nums.size() - 2; i >= 0; --i){unit temp = _nums[i] & 1;_nums[i] = (_nums[i] >> 1) + (prev * upLimit >> 1);prev = temp;}if (_nums.size() > 1 && _nums[_nums.size() - 1] == 0){_nums.pop_back();}}return *this;}iint operator+(const iint& number1, const iint& number2){return iint(number1) += number2;}iint operator-(const iint& number1, const iint& number2){return iint(number1) -= number2;}iint operator*(const iint& number1, const iint& number2){return iint(number1) *= number2;}iint operator/(const iint& number1, const iint& number2){return iint(number1) /= number2;}iint operator%(const iint& number1, const iint& number2){return iint(number1) %= number2;}iint operator<<(const iint& number1, const long long n){return iint(number1) <<= n;}iint operator>>(const iint& number1, const long long n){return iint(number1) >>= n;}bool operator==(const iint& number1, const iint& number2){if (number1._sign != number2._sign){return false;}if (number1._nums.size() != number2._nums.size() || number1.justThanSize(number2) != 0){return false;}return true;}bool operator< (const iint& number1, const iint& number2){if (number1._sign == iint::positive && number2._sign == iint::negative){return false;}if (number1._sign == iint::negative && number2._sign == iint::positive){return true;}iint::unit lessNum = number1.justThanSize(number2);if (lessNum < 0){return number1._sign == iint::positive ? true : false;}else{return number1._sign == iint::positive ? false : true;}}bool operator>=(const iint& number1, const iint& number2){return !(number1 < number2);}bool operator!=(const iint& number1, const iint& number2){return !(number1 == number2);}bool operator<=(const iint& number1, const iint& number2){return number1 < number2 || number1 == number2;}bool operator> (const iint& number1, const iint& number2){return !(number1 <= number2);}bool operator! (const iint& number){return number == 0;}std::ostream& operator<<(std::ostream& out, const iint& number){if (number._sign == iint::negative){out << '-';}out << number._nums[number._nums.size() - 1];for (int i = number._nums.size() - 2; i >= 0; --i){out << std::setw(iint::unitDigit) << std::setfill('0') << number._nums[i];}return out;}std::istream& operator>>(std::istream& in, iint& number){std::string temp;in >> temp;number = temp;return in;}
}

五、空间与时间效率评估(VS2022 release环境)

空间上

lint 使用的是 long long 类型为底层存储数据，64 bite 中有 4 个完全没有使用，有 1 个存储了大半，可以说空间利用率高达 93% 左右。

iint 使用的是 int 型为底层存储数据，32 bite 中有 2 个完全没有使用，有 1 个存储了大半，可以说空间利用率也是 93% 左右。

可以说两者空间上效率都差不多。

时间上

在时间上 iint 每次计算基本比 lint 要多一次内置类型的除法与取模，并且在大数快速增长的计算环境，使用 vector 的 int 类型的扩容消耗是 long long 类型两倍的。这里我们可以详细用代码测试一下，当然，这是在我个人的电脑上测试，准确度不敢保证：

加法测试

在这里插入图片描述
可以看到在 10 ^ 300000 上进行简单加法运算，lint 优于 iint。

减法测试

在这里插入图片描述
减法也一样。

乘法测试

在这里插入图片描述
乘法阶乘测试也一样。

除法测试

在这里插入图片描述
纯内置类型 10 ^ 9 以内的除法上两者差不多。

在这里插入图片描述
除数为第三种情况时，lint 更优。

测试源代码

我将测试源码放这，大家可以自己试试。
在 test.cpp 中

#include "lint.h"
#include "iint.h"
#include <iostream>
using namespace std;void testAdd()
{int move = 300000;int k = 5;while (k--){my::lint a = my::lint::pow(10, move);my::iint b = my::iint::pow(10, move);int Lint1 = clock();for (int i = 0; i < 1000; ++i){++a;}int Lint2 = clock();int Iint1 = clock();for (int i = 0; i < 1000; ++i){++b;}int Iint2 = clock();cout << "lint: " << Lint2 - Lint1 << endl;cout << "iint: " << Iint2 - Iint1 << endl;cout << "是否相等: " << (a.to_string() == b.to_string()) << endl << endl;}
}void testSub()
{int move = 300000;int k = 5;while (k--){my::lint a = my::lint::pow(10, move);my::iint b = my::iint::pow(10, move);int Lint1 = clock();for (int i = 0; i < 1000; ++i){--a;}int Lint2 = clock();int Iint1 = clock();for (int i = 0; i < 1000; ++i){--b;}int Iint2 = clock();cout << "lint: " << Lint2 - Lint1 << endl;cout << "iint: " << Iint2 - Iint1 << endl;cout << "是否相等: " << (a.to_string() == b.to_string()) << endl << endl;}
}void testMul()
{int move = 10000;int k = 5;while (k--){my::lint a = 1;my::iint b = 1;int Lint1 = clock();for (int i = 1; i <= move; ++i){a *= i;}int Lint2 = clock();int Iint1 = clock();for (int i = 1; i <= move; ++i){b *= i;}int Iint2 = clock();cout << "lint: " << Lint2 - Lint1 << endl;cout << "iint: " << Iint2 - Iint1 << endl;cout << "是否相等: " << (a.to_string() == b.to_string()) << endl << endl;}
}void testDiv1()
{int move = 100000;int k = 5;while (k--){my::lint a = my::lint::pow(10, move);my::iint b = my::iint::pow(10, move);int randNum = rand() % 10000 * 10000 + rand() % 10000 + 1;int Lint1 = clock();for (int i = 1; i <= 1000; ++i){a /= randNum;}int Lint2 = clock();int Iint1 = clock();for (int i = 1; i <= 1000; ++i){b /= randNum;}int Iint2 = clock();cout << "lint: " << Lint2 - Lint1 << endl;cout << "iint: " << Iint2 - Iint1 << endl;cout << "是否相等: " << (a.to_string() == b.to_string()) << endl << endl;}
}void testDiv2()
{int move = 100000;int k = 5;while (k--){my::lint a = my::lint::pow(10, move);my::iint b = my::iint::pow(10, move);int randNum = rand() % 10000 * 10000 + rand() % 10000 + 1;my::lint aa = randNum * my::lint::pow(10, 100);my::iint bb = randNum * my::iint::pow(10, 100);int Lint1 = clock();for (int i = 1; i <= 1000; ++i){a / aa;}int Lint2 = clock();int Iint1 = clock();for (int i = 1; i <= 1000; ++i){b / bb;}int Iint2 = clock();cout << "lint: " << Lint2 - Lint1 << endl;cout << "iint: " << Iint2 - Iint1 << endl;cout << "是否相等: " << (a.to_string() == b.to_string()) << endl << endl;}
}void testDiv3()
{int move = 5000;int k = 5;while (k--){my::lint a = my::lint::pow(9, move);my::iint b = my::iint::pow(9, move);int randNum = rand() % 10 + 100;my::lint aa = my::lint::pow(2, randNum);my::iint bb = my::iint::pow(2, randNum);int Lint1 = clock();for (int i = 1; i <= 10; ++i){a /= aa;}int Lint2 = clock();int Iint1 = clock();for (int i = 1; i <= 10; ++i){b /= bb;}int Iint2 = clock();cout << "lint: " << Lint2 - Lint1 << endl;cout << "iint: " << Iint2 - Iint1 << endl;cout << "是否相等: " << (a.to_string() == b.to_string()) << endl << endl;}
}int main()
{srand((unsigned int)time(NULL));//testAdd();//testSub();//testMul();//testDiv1();//testDiv2();testDiv3();return 0;
}