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

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

问题抽象

  • 输入为 ($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 库可自行实现相关类型。

#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;
}