C++大整数运算(五):进制转换

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

本文是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的幂次作为基数,二进制、八进制、十六进制与大整数之间的转换可以使用位运算快速完成,这里就不再详细介绍了。下一节将介绍如何根据无符号大整数类实现有符号的大整数类。

发表评论

电子邮件地址不会被公开。 必填项已用*标注