进制

1. 什么是进制

我们日常生活中最熟悉的数是十进制数。数字 $123$ 究竟代表什么？它并不仅仅是符号 $1$, $2$, $3$ 的简单排列，它的值是：

$$1 \times 10^2 + 2 \times 10^1 + 3 \times 10^0$$

这种表示法被称为按权展开或位值表示法。其中，每个位置上的数字（数码）所代表的实际大小，取决于它所处的位置。每个位置都有一个关联的“权重”，这个权重是“基数”的幂。

• 数码 (Digit)：在特定位置上使用的符号，例如在十进制中是 $0, 1, ..., 9$。
• 基数 (Base/Radix)：每个数位上能使用的数码的个数。十进制的基数是 $10$。
• 权 (Weight)：每个位置的价值，是基数的整数次幂。从右往左，个位的权是 $10^0$，十位的权是 $10^1$，百位的权是 $10^2$，以此类推。

通用范式

这个概念可以推广到任意进制。对于一个 $R$ 进制数，其基数为 $R$。如果一个 $R$ 进制数写作 $(d_{k-1}d_{k-2}...d_1d_0)_R$，其中 $d_i$ 是该数在第 $i$ 位上的数码（$0 \le d_i < R$），那么它对应的十进制值 $N$ 为：

$$N = d_{k-1} \times R^{k-1} + d_{k-2} \times R^{k-2} + \dots + d_1 \times R^1 + d_0 \times R^0 = \sum_{i=0}^{k-1} d_i \times R^i $$

这个公式是所有进制转换的理论基石。

2. 常见进制

在计算机科学中，除了十进制，我们还频繁使用以下几种进制：

• 二进制 (Binary, Base-2)：基数为 $2$，数码仅为 $0$ 和 $1$。这是计算机的母语，因为计算机硬件中的晶体管等基本单元只有“开”和“关”两种状态，天然对应 $1$ 和 $0$。

• 八进制 (Octal, Base-8)：基数为 $8$，数码为 $0, 1, 2, 3, 4, 5, 6, 7$。在早期，它被用作二进制的一种紧凑表示法。

• 十六进制 (Hexadecimal, Base-16)：基数为 $16$。由于数码需要 $16$ 个，除了 $0-9$ 之外，还引入了字母来表示 $10$ 及以上的数码：

  • $A \to 10$
  • $B \to 11$
  • $C \to 12$
  • $D \to 13$
  • $E \to 14$
  • $F \to 15$ 十六进制是目前最常用的二进制紧凑表示法，广泛应用于内存地址、颜色代码等场景。

3. 核心转换方法

所有进制转换问题都可以归结为两种基本操作。

3.1 任意进制转十进制

方法：按权展开求和

直接应用我们在第一节中建立的通用范式 $\sum d_i \times R^i$。

示例 1：二进制转十进制 将 $(1101)_2$ 转换为十进制。 $N = 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 8 + 4 + 0 + 1 = 13$。 所以 $(1101)_2 = (13)_{10}$。

示例 2：十六进制转十进制 将 $(2AF)_{16}$ 转换为十进制。（记住 $A=10, F=15$） $N = 2 \times 16^2 + 10 \times 16^1 + 15 \times 16^0 = 2 \times 256 + 10 \times 16 + 15 \times 1 = 512 + 160 + 15 = 687$。 所以 $(2AF)_{16} = (687)_{10}$。

在程序实现中，一个更高效的计算方式是使用秦九韶算法 (Horner's method)。对于数 $(d_{k-1}d_{k-2}...d_0)_R$，其值为：

$$N = ((...((d_{k-1} \times R + d_{k-2}) \times R + d_{k-3})...)\times R + d_0) $$

这个过程避免了计算高次幂，只需进行一系列的乘法和加法。

代码实现：任意进制转十进制

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 题意：将一个b进制的数s（字符串形式）转换为十进制数。
ll toDec(string s, int b) {
    ll res = 0;
    for (char c : s) {
        int d;
        if (c >= '0' && c <= '9') {
            d = c - '0';
        } else {
            d = c - 'A' + 10;
        }
        res = res * b + d; // 秦九韶算法核心
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s;
    int b;
    cin >> s >> b;
    cout << toDec(s, b) << endl;
    return 0;
}

• 复杂度分析：
  • 时间复杂度: $O(L)$，其中 $L$ 是输入字符串 s 的长度。我们需要遍历一次字符串。
  • 空间复杂度: $O(1)$，除了存储输入和结果外，只使用了常数个额外变量。

3.2 十进制转任意进制

方法：除基取余法（短除法）

将一个十进制数 $N$ 转换为 $R$ 进制数，过程如下：

1. 用 $N$ 除以基数 $R$，得到商 $q$ 和余数 $r$。这个余数 $r$ 就是 $R$ 进制数的最右边一位（第 $0$ 位）。
2. 用商 $q$ 代替 $N$，重复步骤 1，得到的余数是下一位（第 $1$ 位）。
3. 持续这个过程，直到商为 $0$。
4. 将所有得到的余数逆序排列，即为转换结果。

示例：十进制转二进制 将 $(13)_{10}$ 转换为二进制。

• $13 \div 2 = 6 \quad \text{余} \quad \mathbf{1}$
• $6 \div 2 = 3 \quad \text{余} \quad \mathbf{0}$
• $3 \div 2 = 1 \quad \text{余} \quad \mathbf{1}$
• $1 \div 2 = 0 \quad \text{余} \quad \mathbf{1}$

商为 $0$，停止。将余数从下往上读：$1101$。 所以 $(13)_{10} = (1101)_2$。

代码实现：十进制转任意进制

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 题意：将一个十进制数n转换为b进制数，并以字符串形式输出。
string fromDec(ll n, int b) {
    if (n == 0) return "0"; // 特殊处理0
    string res = "";
    const string tbl = "0123456789ABCDEF"; // 数码查找表
    
    while (n > 0) {
        res += tbl[n % b]; // 取余得到当前位，并追加
        n /= b; // 更新n为商
    }
    
    reverse(res.begin(), res.end()); // 结果需要反转
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n;
    int b;
    cin >> n >> b;
    cout << fromDec(n, b) << endl;
    return 0;
}

• 复杂度分析：
  • 时间复杂度: $O(\log_b N)$，其中 $N$ 是输入的十进制数，b 是目标基数。循环的次数取决于 $N$ 被 b 整除多少次才能变为 $0$。
  • 空间复杂度: $O(\log_b N)$，用于存储结果字符串。

4. 特殊进制转换的捷径

当转换的两个基数之间存在幂关系时（如 $R$ 和 $R^k$），存在非常高效的快捷方法。最典型的就是二进制、八进制和十六进制之间的转换。

• $8 = 2^3$，所以一位八进制数码正好对应三位二进制数码。
• $16 = 2^4$，所以一位十六进制数码正好对应四位二进制数码。

方法：分组转换

4.1 二进制 $\leftrightarrow$ 十六进制

• 二进制转十六进制：从二进制数的右侧开始，每四位分为一组（不足四位的在左侧补 $0$），然后将每组独立转换为一位十六进制数码。

示例：转换 $(1110100101)_2$。

1. 分组：$0011 \quad 1010 \quad 0101$ （左侧补了两个 $0$）
2. 转换每组：
   • $(0011)_2 = 3$
   • $(1010)_2 = 10 \to A$
   • $(0101)_2 = 5$
3. 合并：$(3A5)_{16}$

• 十六进制转二进制：将每一位十六进制数码独立转换为四位二进制数码（不足四位要在左侧补 $0$），然后拼接。

示例：转换 $(3A5)_{16}$。

1. 转换每位：
   • $3 \to (0011)_2$
   • $A \to 10 \to (1010)_2$
   • $5 \to (0101)_2$
2. 拼接：$001110100101 \to (1110100101)_2$

4.2 二进制 $\leftrightarrow$ 八进制

转换规则与十六进制完全相同，只是分组的长度变为三位。

• 二进制转八进制：每三位一组。 示例：转换 $(10111001)_2$。

1. 分组：$010 \quad 111 \quad 001$
2. 转换：$2 \quad 7 \quad 1$
3. 合并：$(271)_8$

• 八进制转二进制：每位转三位。 示例：转换 $(271)_8$。

1. 转换：$2 \to 010$, $7 \to 111$, $1 \to 001$
2. 拼接：$010111001 \to (10111001)_2$

5. 任意进制之间的转换

对于两个任意进制（例如 $7$ 进制转 $13$ 进制）之间的转换，最通用、最不易出错的方法是：

使用十进制作为“桥梁”

1. 将源进制数（如 $7$ 进制）使用“按权展开法”转换为十进制。
2. 将得到的十进制数使用“除基取余法”转换为目标进制（如 $13$ 进制）。

代码实现：任意进制到任意进制

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 将b进制数s转为十进制
ll toDec(string s, int b) {
    ll res = 0;
    for (char c : s) {
        int d;
        if (c >= '0' && c <= '9') d = c - '0';
        else d = c - 'A' + 10;
        res = res * b + d;
    }
    return res;
}

// 将十进制数n转为b进制
string fromDec(ll n, int b) {
    if (n == 0) return "0";
    string res = "";
    const string tbl = "0123456789ABCDEF";
    while (n > 0) {
        res += tbl[n % b];
        n /= b;
    }
    reverse(res.begin(), res.end());
    return res;
}

// 题意：将b1进制的数s，转换为b2进制的数。
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int b1, b2;
    string s;
    cin >> b1 >> s >> b2;
    
    // 步骤1: 源进制 -> 十进制
    ll dec_val = toDec(s, b1);
    
    // 步骤2: 十进制 -> 目标进制
    string ans = fromDec(dec_val, b2);
    
    cout << ans << endl;
    
    return 0;
}

• 复杂度分析：
  • 设输入字符串长度为 $L$，数值大小为 $N$。
  • toDec 复杂度为 $O(L)$。
  • fromDec 复杂度为 $O(\log_{b2} N)$。
  • 由于 $N$ 的值与 $L$ 和 $b1$ 相关 ($N \approx b1^L$)，$\log_{b2} N \approx L \cdot \log_{b2} b1$。
  • 总时间复杂度: $O(L + L \cdot \log_{b2} b1) = O(L \log_{b2} b1)$。
  • 空间复杂度: $O(\log_{b2} N)$，即 $O(L \log_{b2} b1)$，主要由最终结果字符串占据。

6. 例题

6.1 选择/判断题

这类题通常考察基本概念和快速手动计算能力。

例题：在下列数值中，最大的是哪一个？ A. $(100)_{16}$ B. $(250)_{10}$ C. $(377)_8$ D. $(11111110)_2$

解法：将所有选项都转换为十进制进行比较，这是最可靠的方法。 A. $(100)_{16} = 1 \times 16^2 + 0 \times 16^1 + 0 \times 16^0 = 256$ B. $(250)_{10}$ 已是十进制，值为 $250$ C. $(377)_8 = 3 \times 8^2 + 7 \times 8^1 + 7 \times 8^0 = 3 \times 64 + 56 + 7 = 192 + 56 + 7 = 255$ D. $(11111110)_2$ 可以利用特殊转换。它比 $(100000000)_2$（即 $2^8=256$）小 $2$。具体地，它是 $2^7+2^6+...+2^1 = 254$。或者直接按权展开计算。 比较 $256, 250, 255, 254$，最大的是 $256$。答案：A。

6.2 程序阅读题

这类题会给出一个实现进制转换的代码片段，要求你分析其功能或预测输出。

例题：分析以下C++函数，f(21, 8)的输出是什么？

void f(int n, int r) {
    if (n == 0) return;
    f(n / r, r);
    cout << n % r;
}

解法：这是一个递归实现的十进制转任意进制的函数。我们来追踪执行过程：

1. f(21, 8) 调用 f(21/8, 8) 即 f(2, 8)，然后等待打印 21 % 8 (即 5)。
2. f(2, 8) 调用 f(2/8, 8) 即 f(0, 8)，然后等待打印 2 % 8 (即 2)。
3. f(0, 8) 直接返回。
4. f(2, 8) 的调用栈返回，打印 2。
5. f(21, 8) 的调用栈返回，打印 5。 由于递归调用在打印之前，这个过程实际上是正序生成了余数，但因为函数返回的顺序是从内到外，所以打印的顺序是 2 然后是 5。 最终输出是 25。这恰好是 $(21)_{10}$ 转换成八进制的结果 $(25)_8$。

6.3 程序补全题

这类题会提供一个不完整的代码框架，要求你填入关键部分。

例题：补全以下将十六进制字符串转为十进制整数的函数。

ll hexToDec(string s) {
    ll res = 0;
    for (char c : s) {
        int d;
        if (c >= '0' && c <= '9') {
            d = c - '0';
        } else if (c >= 'A' && c <= 'F') {
            // [--- 待填充代码 ---]
        } else {
            return -1; // 非法字符
        }
        res = res * 16 + d;
    }
    return res;
}

解法：需要填充的部分是将字符 'A' 到 'F' 转换为对应的数值 10 到 15。字符 'A' 的ASCII码比 '0' 大，但它们不连续。一个稳健的转换方式是利用 'A' 本身的ASCII码。

• d 应该等于 c - 'A' + 10。
  • 当 c 是 'A' 时, 'A' - 'A' + 10 = 10。
  • 当 c 是 'B' 时, 'B' - 'A' + 10 = 11。
  • ...
  • 当 c 是 'F' 时, 'F' - 'A' + 10 = 15。

所以，填充的代码是 d = c - 'A' + 10;。这考察了对字符编码和进制转换逻辑细节的掌握。