当前位置：首页 > article >正文

大数运算：整数、小数的加减乘除与取余乘方（c++实现）

article 2025/1/30 16:33:22

前言

本文源码见【MyHeader】下的 Number 文件夹

c++ 中整型、浮点数等数据类型是由精度限制的，这就导致了使用 c++ 基本类型是无法正确进行大数运算的：
【例】

代码：

// test.cpp
#include <iostream>
#include <climits>

using namespace std;

int main()
{
    long long num1 = LONG_LONG_MAX;
    long long num2 = LONG_LONG_MAX;
    cout << num1 << " + " << num2 << " = " 
    	 << num1 + num2 << endl;
    return 0;
}

输出：

因此设计 Number 类来实现大数运算是本文的基本任务，本文将实现以下运算（包括整数、浮点数）：

加法：+
减法：-
乘法：*
除法：/
取余：%
乘方：^

一、基本思路

基本四则运算加减乘除，相信通过手算大家都会，Number 类的实现思路就是模拟手算。

怎么存储大数呢？用基础类型(long long、double等)，肯定不行，因为精度不够，那么可以采用数组、字符串等来存储大数的每一位数字，本文采用字符串。

class Number
{
public:
	/* ... */
private:
	std::string _val;
};

换句话说：

Number 的实现是建立在 实现字符串运算 的基础之上

二、API 设计

1. 构造函数

Number 类从定义上看，它就是一个数字，因此我们希望能用 long long、double 等类型初始化 Number：

Number num1{ 1000 };
Number num2{ 1.23 };

这对于在 c++ 允许的数据范围内的数字初始化，是有效的，但是对于更大的数是无效的，因此还需要有一个能初始化大数的构造函数，当然大数需要用字符串表示：

Number big_num{ "9999999999999999999999999" };

也就是说 Number 的构造函数如下：

class Number
{
public:
    Number(long long num)          :_val{ std::to_string(num) } { }
    Number(double num)             :_val{ std::to_string(num) } { }
    Number(const std::string& num) :_val{ num } { }
    ~Number() = default;
    
public:
	std::string str() const { return _val; }
	
private:
	std::string _val;
};

【修改】 浮点数精度问题

c++ double 类型，当小数位数过多时，会出现精度问题：

if (3.1234567890123456 == 3.1234567890123457) {
	cout << "true" << endl;
}

上面的程序会输出： true

在 Number(double num) 中，使用到了 std::to_string(double x) 函数，有如下代码：

Number num{3.1415926};
cout << num.str();

会输出：3.141593

上面两个问题涉及到浮点数精度问题，这是 c++ 内部实现 double 的问题，我们无法避免。
对于 Number 而言，显然我们希望 Number num{3.1415926} 就是 “3.1215926”，不应该是其他值，当然你可以自己设计一个算法能原样地将 double 转为 string，这显然仍然会遇到浮点数精度问题。

既然无法避免，那么就直接不要构造函数 Number(double num)，也就是说，使用 Number 时，遇到浮点数必须使用 Number(const std::string& num) 进行初始化，这样就不必考虑浮点数精度问题：

class Number
{
public:
    Number(long long num)          :_val{ std::to_string(num) } { }
    Number(const std::string& num) :_val{ num } { }
    ~Number() = default;

private:
    std::string _val;
};

// 浮点数初始化 Number
Number num{ "3.1215926" };

然而这样的设计存在一个问题：

Number num{ 3.14 };		// 将调用 Number(long long num)

也就是说，想要更安全的 Number 类，Number(long long num) 也应该被删除。这样的 Number 类虽然初始化较为复杂（不管大数还是小数，每次都必须用字符串），但是换来了更为安全的转换（不必担心浮点数精度不够、超出整型数据范围等问题），这是可以接受的。

【修改版本】

class Number
{
public:
    Number()                       :_val{ "0" } { }
    Number(const std::string& num) :_val{ num } { }
    ~Number() = default;
    
private:
    std::string _val;
};

2. 重载运算符函数

c++ 中，类有一类函数是很好用的，那就是重载运算符函数，它运行我们重新定义运算符的功能。
以加法运算为例，如果 Number 实现的加法功能是 add(const Number& other) 成员函数，那么使用加法：

Number num1, num2;
auto res = num1.add(num2);

但倘若在 Number 中重载了 + 运算符，那么使用加法：

Number num1, num2;
auto res = num1 + num2;

第二种对于类的使用者来说是比较友好的，因此 Number 重载运算符函数如下：

Number  operator+ (const Number& other);	// res = num1 + num2
Number& operator+=(const Number& other);	// num1 += num2
Number  operator- (const Number& other);
Number& operator-=(const Number& other);
Number  operator* (const Number& other);
Number& operator*=(const Number& other);
// @brief 整除
Number  operator/ (const Number& other);
// @brief 整除
Number& operator/=(const Number& other);
Number  operator% (const Number& other);
Number& operator%=(const Number& other);
Number  operator^ (Number other);
Number& operator^=(const Number& other);

Number& operator= (const std::string& number);
Number& operator= (const Number& number);

bool    operator==(const Number& other);
bool    operator!=(const Number& other);
bool    operator> (const Number& other);
bool    operator>=(const Number& other);
bool    operator< (const Number& other);
bool    operator<= (const Number& other);

operator/(const Number& other)：
1 / 3 = 0.333…，它是个无限循环小数，显然不可能表示完；因此对于除法需要特殊处理：保留指定的小数位数。使用这个函数显然不能指定保留小数位数的参数，此外，在 c++ 中，/ 是整除的含义，为了与 c++ 保持一致，Number 类的 / 运算符的含义也是整除，同时增加一个成员函数 div(…)，此函数就是普通意义的除法，可指定保留的小数位数，它的设计在后续再详细说明。
Number& operator=(const std::string& number)
赋值运算符，有了这个函数，这就能实现一下语句：
```
Number num;
num = "1";    // 使用较为方便
```

以上仅仅是它们的声明，具体实现在第三章讲解。

3. other

div(const Number& other, int precision, int flag)
对于平常的除法而言，我们关心连个问题：(1) 保留小数的位数 precision；(2) 小数最后一位采用的保留方式 flag (四舍五入、截断等方式）
str()
返回数字字符串
… …

【综上】 Number 完整定义如下：

class Number
{
public:
    using size_type = std::string::size_type;

public:
    static const int PRECISION = 6;

public:
    enum class DivFlag  /* 小数最后一个保留方式 */
    {
        round,          // 四舍五入
        truncate        // 截断
    };

public:
    Number()                       :_digit{ "0" } { }
    Number(const std::string& num) :_digit{ num } { }
    ~Number() = default;
    
public:
    Number  operator+ (const Number& other);
    Number& operator+=(const Number& other);
    Number  operator- (const Number& other);
    Number& operator-=(const Number& other);
    Number  operator* (const Number& other);
    Number& operator*=(const Number& other);
    // @brief 整除
    Number  operator/ (const Number& other);
    // @brief 整除
    Number& operator/=(const Number& other);
    Number  operator% (const Number& other);
    Number& operator%=(const Number& other);
    Number  operator^ (Number other);
    Number& operator^=(const Number& other);
    Number& operator= (const std::string& number);
    Number& operator= (const Number& number);
    bool    operator==(const Number& other);
    bool    operator!=(const Number& other);
    bool    operator> (const Number& other);
    bool    operator>=(const Number& other);
    bool    operator< (const Number& other);
    bool    operator<=(const Number& other);

public:
    /**
     * @brief 小数除法
     * @param other 除数
     * @param n 保留小数位数
     * @param flag 小数最后一个保留的方式
     */
    Number      div(const Number& other, int n = PRECISION, DivFlag flag = DivFlag::round);
    std::string str() const;
    
private:
    std::string _digit;     // 删除小数点后的数字 (数字部分)
    int         _point;     // 小数位数，则小数点位于 _digit[len - _point]
    bool        _signed;    // true: negative
};

看完定义，你会发现它的成员变量从原来的单个 _val 变成了三个，这样做的目的是什么呢？这是为了方便实现算术运算，因为负数运算、小数运算都能转为正整数运算。用加法举个例子（假设已经实现了所有的正整数运算）：

负数运算：“- 2 + 1” 可以转为 “2 - 1” 再取相反数即可
小数运算：“3 + 2.1” 可以转为 “30 + 21 = 51” 然后再结果上添加一位小数，即 “5.1”

也就是说，其他运算则是在正整数运算的基础上，进行 _point、_signed 的转换。

这里增加一个我自定义的术语：数字部分(_digit，表示删除小数点后剩余的数字
【例】

3.14： _digit = 314，_point = 2，_signed = false
-3.0： _digit = 300，_point = 1，_signed = true

当然，由于成员变量的改变，那么构造函数的实现也要改变，即给定数字字符串，它能计算出 _digit、_point、_signed，这不在本文讨论范围内，读者可自行实现。

下文中一些自定义函数的实现也不给出，仅给出它的功能介绍

三、具体实现

在上面，我说过 “负数运算、小数运算都能转为正整数运算”，因此这里的主要任务是 实现正整数运算。

1. 加法

1.1 正整数加法

基本思路：用代码模拟手算正整数加法
在这里插入图片描述
给定两个字符串，计算它们之间的加法，只需要将两字符串末尾对齐，然后每一位对应相加，同时记录进位即可：

std::string add_int(std::string num1, std::string num2)
{
    std::string res;
    // 记录当前位相加的结果: 
    // 1. 其个位 (cur % 10) 为 res 当前位的结果
	// 2. 其十位 (cur / 10) 为 当前位相加的进位
    int cur = 0;	
    int p1 = num1.size() - 1, p2 = num2.size() - 1;		// 末尾对齐
    while (p1 >= 0 || p2 >= 0 || cur > 0) {
        if(p1 >= 0) cur += num1[p1--] - '0';
        if(p2 >= 0) cur += num2[p2--] - '0';
        res = std::to_string(cur % 10) + res;	// 倒序
        cur = cur / 10;
    }
    return res;
}

在这里用到一个小技巧：数字字符转对应数字

‘9’ - ‘0’ == 9
… …
‘0’ - ‘0’ == 0

1.2 正小数加法

对于小数加法，手算的话需要将小数点对齐。前面说过：小数加法可转为正整数加法，在计算小数点位数即可：
在这里插入图片描述
观察上图：对齐小数点后，去掉小数点，对于小数位数较少的数字需要在末尾补 0，那么剩下的就是正整数加法，其结果的小数位数就是两个加数的最大小数位数。

/**
 * @brief 浮点数加法
 * @param num1 第一个浮点数的数据部分
 * @param p1   第一个浮点数的小数点位数
 * @param num2 第二个浮点数的数据部分
 * @param p2   第二个浮点数的小数点位数
 * @return 返回正常的小数 (包含小数点)
 */
inline std::string add_double(std::string num1, int p1, std::string num2, int p2)
{
    int p = std::max(p1, p2);
    int dif = abs(p1 - p2);
    if (dif != 0) {
        if (p1 > p2) num2 += std::string(dif, '0');
        else num1 += std::string(dif, '0');
    }
    std::string res = add_int(num1, num2);
    // to_double: 自定义函数，根据指定数据部分以及小数位数，返回小数的字符串形式
    // 例：to_double("100", 2) == "1.00" 
    res = to_double(res, p);	
    return res;
}

1.3 operator+

前面实现了正整数、正浮点数的加法，那么剩余的就是有负数参与的加法，这里分为四种情况：

正 + 正：直接调用 add_int 即可
正 + 负：相当于 “正 - 正”，调用 sub_int 即可（后续实现 sub_int）
负 + 正：相当于 “正 + 负”，同上述
负 + 负：相当于 “- (正 + 正)”

Number operator+(const Number& other)
{
    if (!_signed) {
        if (!other._signed) return Number{add_double(_digit, _point, other._digit, other._point)};
        else return Number{sub_double(_digit, _point, other._digit, other._point)};
    }
    else {
        if (!other._signed) return Number{sub_double(other._digit, other._point, _digit, _point)};
        else return Number{"-" + add_double(_digit, _point, other._digit, other._point)};
    }
    return Number{};
}

2. 减法

2.1 正整数减法

减法与加法类似，需要将末尾对齐，每一位对应相减，同时记录借位即可。不过减法多了一点：需要比较两个数的大小。
在这里插入图片描述

std::string sub_int(std::string num1, std::string num2)
{
    bool is_signed = false;		// 记录结果的正负性
    // cmp_int：比较 num1 与 num2 的大小
    // 1. return  1:  num1 > num2
    // 2. return  0:  num1 = num2
    // 3. return -1:  num1 < num2
    if (cmp_int(num1, num2) == -1) {
        std::swap(num1, num2);
        is_signed = true;
    }
    std::string res;
    // 记录当前位相减的结果 (结果一定是一位数)
    // 1. cur < 0: 说明需要借位，结果为 cur + 10
    // 2. cur > 0: 不需要结尾，结果就是 cur
    int cur = 0;	
    bool is_carry = false;      // 是否借位
    int len1 = num1.size() - 1, len2 = num2.size() - 1;
    while (len1 >= 0 || len2 >= 0 || cur > 0) {
        if(len1 >= 0) {
            cur += num1[len1--] - '0' - is_carry;	// 第一个用 +，同时减去借位
            is_carry = false;
        }
        if(len2 >= 0) cur -= num2[len2--] - '0';	// 第二个用 -
        if (cur < 0) {
            cur += 10;
            is_carry = true;
        }
        res = std::to_string(cur) + res;	// 逆序
        cur = 0;
    }
    if (is_signed) res = "-" + res;
    return res;    
}

在上述代码中，is_carry 用于记录是否借位，将它转为 int 的话，要么是 0 要么是 1，你会发现这恰恰是减法借位的范围（向高位要么借1要么借0）

2.2 正小数减法

浮点数减法与浮点数加法思路一致：

std::string sub_double(std::string num1, int p1, std::string num2, int p2)
{
    int p = std::max(p1, p2);
    int dif = abs(p1 - p2);
    if (dif != 0) {
        if (p1 > p2) num2 += std::string(dif, '0');
        else num1 += std::string(dif, '0');
    }
    std::string res = sub_int(num1, num2);
    res = to_double(res, p);
    return res;
}

2.3 operator-

同加法，不再赘述

Number operator-(const Number& other)
{
    if (!_signed) {
        if (!other._signed) return Number{sub_double(_digit, _point, other._digit, other._point)};
        else return Number{add_double(_digit, _point, other._digit, other._point)};
    }
    else {
        if (!other._signed) return Number{"-" + add_double(_digit, _point, other._digit, other._point)};
        else return Number{sub_double(other._digit, other._point, _digit, _point)};
    }
    return Number{};
}

3. 乘法

3.1 正整数乘法

手算乘法，如下图左边是我们比较熟悉的方式，实际上在简化每一步的操作，那么就对应右边的式子：
在这里插入图片描述
对于 m 位数字与 n 位数字相乘，其结果最多有 m + n 位，对于上述例子的加法部分，当然可以用前面实现的字符串加法，但采用 int 数组来存储数字在再计算加法来模拟上述的过程效率更高些：

std::string mul_int(std::string num1, std::string num2)
{
    int m = num1.size(), n = num2.size();
    std::vector<int> res(m + n);
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + res[p2];
            res[p2] = sum % 10;
            res[p1] += sum / 10;
        }
    }
    int i = 0;
    while (i < res.size() && res[i] == 0) i++;
    std::string str;
    for (; i < res.size(); i++) str.push_back(res[i] + '0');
    return str.empty() ? "0" : str;
}

此函数有优化的算法（Karatsuba、FFT），读者可自行查略资料

3.2 正小数乘法

对于两数相乘，其结果的小数位数为两乘数的小数位数之和：

std::string mul_double(std::string num1, int p1, std::string num2, int p2)
{
    std::string res = mul_int(num1, num2);
    res = to_double(res, p1 + p2);
    return res;
}

3.3 operator*

对于正负数乘法：符号相同为正，符号不同为负

Number operator*(const Number& other)
{
    if (!_signed) {
        if (!other._signed) return Number{mul_double(_digit, _point, other._digit, other._point)};
        else return Number{"-" + mul_double(_digit, _point, other._digit, other._point)};
    }
    else {
        if (!other._signed) return Number{"-" + mul_double(_digit, _point, other._digit, other._point)};
        else return Number{mul_double(_digit, _point, other._digit, other._point)};
    }
    return Number{};
}

4. 除法

4.1 正整数除法

对于除法来说，前面说过其参数应该有保留小数位数 precision、最后一位小数保留方式 flag，因此函数声明应如下：

/**
 * @brief 计算 num1 / num2，保留 n 位小数 (如果能整除，无论 n 为几，都不保留小数)
 */
std::string div_int(std::string num1, std::string num2, int precision = PRECISION, DivFlag flag = DivFlag::round)

上面说明能整除的，div_int 的后两个参数将无效：

div_int(“4”, “2”) 应等于 “2” 而不是 “2.000000”

对于除法而言，其商分为两个部分：整数部分与小数部分，也就是说模拟手算除法分为两部分：

计算整数部分
对于 num1 / num2，整数部分恰恰是 num1 整除 num2，因此需要一个字符串整除函数 divide(…)；同时，小数部分需要余数，故此函数还需返回余数。利用除法转减法的思想实现整除函数：

/**
 * @brief 返回余数的除法 
 * @param num1 被除数，接收相除后的余数
 * @return 商
 */
std::string divide(std::string& num1, std::string num2)
{
    if (num2 == "0") throw NumberExcep{"The divisor cannot be 0"};
    std::string res = "0";
    while (cmp_int(num1, num2) != -1) {
        num1 = sub_int(num1, num2);
        add_int(res, "1");
    } 
    return res;
}

这是最简单但是时间开销很大的版本，此函数有很大的优化空间，读者可自行查略资料

计算小数部分
无非就是用余数继续除以除数，不够除的乘以10继续除，直到余数为0或者小数位数达到指定位数

/**
 * @brief 计算 num1 / num2，保留 n 位小数 (如果能整除，无论 n 为几，都不保留小数)
 */
std::string div_int(std::string num1, std::string num2, int precision = PRECISION, DivFlag flag = DivFlag::round)
{
    std::string res;
    res = divide(num1, num2);
    if (num1 == "0") return res;
    // 小数部分
    for (int i = 0; i < precision; ++i) {
        if (num1 != "0") num1 += "0";
        res += divide(num1, num2);
    }
    // 最后一位保留方式
    switch (flag) {
        case DivFlag::round:
        {
            if (num1 != "0") num1 += "0";
            std::string last = divide(num1, num2);
            if (cmp_int(last, "5") == -1) break;
            res = add_double(res, precision, "1", precision);
            return res;
        }
        case DivFlag::truncate: break;
        default: THROW_SWITCH_DEFAULT_OUTDATED;
    }
    return to_double(res, precision);
}

4.2 正小数除法

对于小数，直接转为整数即可：
在这里插入图片描述

std::string div_double(std::string num1, int p1, std::string num2, int p2, int precision = PRECISION, DivFlag flag = DivFlag::round)
{
    int p = std::max(p1, p2);
    int dif = abs(p1 - p2);
    if (dif != 0) {
        if (p1 > p2) num2 += std::string(dif, '0');
        else num1 += std::string(dif, '0');
    }
    return div_int(num1, num2, precision, flag);
}

4.3 operator/

前面说过，这是整除，因此代码如下：

// @brief 整除
Number operator/(const Number& other)
{
    if (!_signed) {
        if (!other._signed) return Number{div_double(_digit, _point, other._digit, other._point, 0, DivFlag::truncate)};
        else return Number{"-" + div_double(_digit, _point, other._digit, other._point, 0, DivFlag::truncate)};
    }
    else {
        if (!other._signed) return Number{"-" + div_double(_digit, _point, other._digit, other._point, 0, DivFlag::truncate)};
        else return Number{div_double(_digit, _point, other._digit, other._point, 0, DivFlag::truncate)};
    }
    return Number{};
}

5. 取余

5.1 正数取余

取余，即计算余数。有如下式子：

num1 / num2 = s … m 即 num1 % num2 = m
【分析】现在相当于已知 num1 与 num2，求 m

根据前式可知：num2 * s + m = num1，因此 m = num1 - num2 * s，现在仅 s 未知，s 是商，即 num1 整除 num2，因此 m 可求

std::string mod(std::string num1, int p1, std::string num2, int p2)
{
    std::string dif = div_double(num1, p1, num2, p2, 0, DivFlag::truncate);     // 整除
    std::string mul = mul_double(num2, p2, dif, 0);
    // cal_digit_point(n, p): 计算 n 的数据部分(结果赋值给 n) 与 小数位数(结果赋值给 p)
    // 例：n = "1.00" ⇒ n = "100", p == 2
    cal_digit_point(mul, p2);
    return sub_double(num1, p1, mul, p2);
}

5.2 operator%

当加入负数时，结果不变，只是正负性改变，满足以下规律：
对于 num1 % num2 = m，m 的正负性与 num1 一致

读者可自行推导

Number operator%(const Number& other)
{
    if (_signed) return Number{"-" + mod(_digit, _point, other._digit, other._point)};
    else return Number{mod(_digit, _point, other._digit, other._point)};
}

6. 乘方

对于乘方运算，为了方便要求指数必须为整数，那么使用快速幂算法可快速求出结果

Number  operator^ (Number other)
{
    bool is_signed = other._signed;   
    if (other._point != 0) throw NumberExcep{"Decimal exponents are not supported"};
    if (other == "0") return "1";
    if (*this == Number{ "0" }) return "0";
    Number res = "1";
    while (cmp_int(other._digit, "0") == 1) {
        if (other % "2" == "1") res *= (*this);
        other /= "2";
        *this *= (*this);
    }
    return (is_signed) ? Number{"1"}.div(res) : res;
}