C++大整数运算（五）：进制转换

C++大整数运算系列文章讲述了实现大整数四则运算的基本思路和方法，对算法做简单的介绍并采用C++代码做进一步说明。本文并不试图写成一篇教程，而是对实现过程进行整理和概括。实现过程中学习了 Donald E. Knuth 著作的 The Art of Computer Programming 中的相关内容，特此致敬。

本文是C++大整数运算系列文章的第五篇，主要介绍如何在大整数与十进制字符串之间转换。

目录

• C++大整数运算（一）：概述
• C++大整数运算（二）：加法和减法
• C++大整数运算（三）：乘法
• C++大整数运算（四）：除法
• C++大整数运算（五）：进制转换

由于在计算过程中的优势，我们选择了采用2^32作为大整数的基数，但这使得大整数与十进制之间的转换变得略微复杂。

十进制转大整数

定义一个大整数的变量，将十进制从高位到低位依次添加到大整数即可，记得每增加一位数需要将大整数乘以10。

unsigned_bigint to_big(string s)
{
    unsigned_bigint result;
    for(size_t i = 0; i < s.length(); ++i)
    {
        result *= 10;
        result += s[i] - '0';
    }
    return result;
}

上述代码已经基本可以完成转换，为了更快地完成计算，还可以每次循环计算多个数位，也就是把十进制数当作1000、1000000等进制的数来处理，但同时要注意其中的细节。

大整数转十进制

既然十进制转大整数是“乘十加数位”，显然逆向的转换可以通过“除十取余”来实现，例如：

string to_string(unsigned_bigint ubig)
{
    if(ubig == 0) return "0";
    string result;
    while(ubig > 0)
    {
        result.push_back(ubig%10 + '0');
        ubig /= 10;
    }
    return reverse(result); // 假设已经实现了反转字符串的函数
}

显然，频繁的除法操作会给效率带来很大的影响，如果你对效率没有要求，那这种方法既容易理解，又便于实现。作者使用这种转换方法与python3的整数转字符串比较了一下，发现运行时间是python的5倍，显然有更好的方法完成这样的转换。

假设我们实现了另一个10的幂次为基数的大整数tbig，既然十进制转大整数可以使用乘法，那么大整数转十进制(tbig)也可以使用乘法实现：

tbig to_tbig(unsigned_bigint ubig)
{
    tbig t = 0;
    for(digit in ubig) // 从高位到低位遍历
    {
        t *= 2^32;
        t += digit;
    }
    return t;
}

上述代码并不是可以编译的C++代码，而是由于unsigned_bigint的实现细节不同而忽略了部分细节。当我们得到以10的幂次表示的大整数之后，再将其转换为十进制的字符串就很简单了。

本文介绍了十进制与大整数之间的转换方法，在实际的操作中，还可能需要其它进制与大整数之间的转换，但基本方法是相似的。需要注意的是，由于大整数采用了2的幂次作为基数，二进制、八进制、十六进制与大整数之间的转换可以使用位运算快速完成，这里就不再详细介绍了。下一节将介绍如何根据无符号大整数类实现有符号的大整数类。