目录

大数任意进制转换

https://cdn.lsvm.xyz/2020/03/2020-03-big-number-base-convert-00.jpg!on_blog

写算法题的时候经常会碰到一些大数相关的问题,比如大数乘法、大数加法等等,乘法和加法的原理基本上都比较符合正常的思维模式,因为加法和乘法的原理相对清晰,模拟数学计算步骤可以方便地分离,并转换为代码。

相对于常见的加法和乘法,进制转换出现的频率低一些,但同样是一个十分值得探讨的问题,并且难度较之加法和乘法更高。

问题抽象

  • 输入为 ($M$, $m$, $n$):

    • $M$: $m$ 进制整数 $M$,用字符串类型 string 储存
    • $m$: 大数基数 $m$
    • $n$: 大数目的基数 $n$
  • 输出为 N:

    • $N$: $n$ 进制整数 $N$,用字符串类型 string 储存

数学原理

$m$ 进制转换成 $n$ 进制,通常采用的是「模 $n$ 取余法」,也称「辗转相除法」,一般数进制转换的方法:

进制转换方法
  1. 输入 $m$ 进制数 $M$ 作为除数,对目标进制基数 $n$ 求整数商得到商 $Q^1$ ,对基数 $n$ 取余得到余数 $R^1$,

  2. 若商 $Q^1$ 为 $0$,循环终止,否则,用商 $Q^1$ 作为除数,继续对基数 $n$ 求整数商得到商 $Q^2$,取余得到余数 $R^2$,

  3. 循环第2步,直到商 $Q^t$ 为 $0$,此时得到余数 $R^t$,

    则余数序列 $R^tR^{t-1} \cdots R^1$ 为转换后的 $n$ 进制数 $N$。

一个简单的例子

如 $30 \to (11110)_2$

运算过程:

30 / 2 = 15, 0

15 / 2 = 7, 1​

7 / 2 = 3, 1

3 / 2 = 1, 1

1 / 2 = 0, 1

可以想象,大数转换步骤同样如此。

问题只在于大数的整数除取余比一般数字更复杂一些,这里将算法解释如下:

大数整数除及取余方法
  1. 设余数 $R=0$

  2. 由低位至高位,从大数中取数 $M^1$,用余数 $R$ 乘以进制基数 $m$ 后再加上数 $M^1$,得到数 $R \cdot m + M^1$,用该数对目标进制基数 $n$求整数商得到商 $Q^1$,对基数 $n$ 取余得到新的余数 $R$

  3. 循环第2步,直至取完大数所有位,得到商 $Q^t$ 和余数 $R$

    则商序列 $Q^tQ^{t-1}\cdots Q^1$ 为整数商,$R$ 为余数。

一个稍微复杂的例子

eg. $(11110)_2 \to 30$

序号 当前位 运算
0 null null
1 1 (0 * 2 + 1) / 10 = 0, 1
2 1 (1 * 2 + 1) / 10 = 0, 3
3 1 (3 * 2 + 1) / 10 = 0, 7
4 1 (7 * 2 + 1) / 10 = 1, 5
5 0 (5 * 2 + 0) / 10 = 1, 0

故商 $(11110)_2/10=(00011)_2=(11)_2$,余数为 $0$

将 $(11)_2$ 用作下一次循环的运算数

序号 当前位 运算
0 null null
1 1 (0 * 2 + 1) / 10 = 0, 0
2 1 (1 * 2 + 1) / 10 = 0, 3

故商 $(11)_2/10=(00)_2=0$,余数为 $3$

循环结束,得到余数序列 $03$,逆序后得到进制转换后的数 $30$

代码实现

这里给出 C++ 的算法实现,使用了大量内置的 STL,如不能使用 STL 库可自行实现相关类型。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include "string"
#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

/**
 * Mapping a n-base number to a int number
 * @param c the n-base number
 * return the int number
 */
int GetValue(char c) {
    if (c >= '0' && c <= '9') {
        return c - '0';
    }
    if (c >= 'a' && c <= 'z') {
        return c - 'a' + 10;
    }
    if (c >= 'A' && c <= 'A') {
        return c - 'A' + 36;
    }
    return -1;
}

/**
 * Convert a big num between different base.
 * @param a the string of big num
 * @param src_base the base of origin number,
 * @param to_base
 * @return the sring of big num in src_base
 */
string BaseConvert(string a, int src_base, int to_base = 10) {
    if (src_base < 2 || src_base > 62 || to_base < 2 || to_base > 62) {
        return reinterpret_cast<const char *>(1);
    }

    char num_alpha[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int temp = 0;
    vector<int> number, quotient, result;
    string s;

    // 将字母映射为数字
    for (char &c : a) {
        number.push_back(GetValue(c));
    }
    auto iter = number.begin();

    while (!number.empty()) {
        // 得到余数和商
        while (iter != number.end()) {
            temp *= src_base;
            temp += *iter++;
            quotient.push_back(temp / to_base);
            temp %= to_base;
        }
        // 得到余数,存入result
        result.push_back(temp);
        
        // 清空商的前置0
        auto i = quotient.begin();
        while (*i == 0 && i != quotient.end()) { i++; }
        if (i != quotient.begin()) {
            quotient.erase(quotient.begin(), i);
        }

        // 将商作为下一次的运算数,重置商数组和temp
        number = quotient;
        quotient.clear();
        iter = number.begin();
        temp = 0;
    }

    // 逆序余数位
    reverse(result.begin(), result.end());
    // 将数字映射为字母
    for (int &i:result) {
        s += num_alpha[i];
    }

    return s;
}

int main() {
    cout << BaseConvert("11110", 2, 10) << endl;
    cout << BaseConvert("30", 10, 2) << endl;

    return 0;
}