概念导入：认识进制的世界

什么是进制？它有什么用？

进制，简单来说，就是一种“逢几进一”的计数系统。我们最熟悉的十进制就是逢十进一，使用 0-9 十个数字。

计算机内部的世界主要运行在二进制（逢二进一，只有 0 和 1）之上。因为电路的开和关正好对应 1 和 0。

为了方便程序员阅读和表示二进制数据，我们常用八进制（逢八进一，0-7）和十六进制（逢十六进一，0-9 和 A-F）作为二进制的简写。

应用场景：

  • 网络编程：IP地址（v4常用十进制，v6用十六进制），MAC地址（十六进制）
  • 数据编码：字符编码（如UTF-8）、颜色代码（如#FF0000）
  • 底层编程：内存地址、位运算、文件权限（八进制）
关键点：进制是计数基础，不同进制服务于不同场景（人类习惯 vs 计算机底层 vs 便捷表示）

常见进制的特点

二进制 (Base-2)：

  • 符号：0, 1
  • 特点：计算机物理基础，逻辑运算简单。
  • 示例：11012 = 1*2³ + 1*2² + 0*2¹ + 1*2⁰ = 8 + 4 + 0 + 1 = 13₁₀

八进制 (Base-8)：

  • 符号：0, 1, 2, 3, 4, 5, 6, 7
  • 特点：每3位二进制可直接转换成1位八进制。
  • 示例：110 101₂ = 65₈

十进制 (Base-10)：

  • 符号：0, 1, 2, 3, 4, 5, 6, 7, 8, 9
  • 特点：人类最常用的计数系统。
  • 示例：123₁₀

十六进制 (Base-16)：

  • 符号：0-9, A(10), B(11), C(12), D(13), E(14), F(15)
  • 特点：每4位二进制可直接转换成1位十六进制，常用于表示内存地址、颜色等。
  • 示例：1A₁₆ = 1*16¹ + 10*16⁰ = 16 + 10 = 26₁₀

任意进制 (Base-N)：

  • 符号：通常用 0 到 N-1 的符号表示。大于10时常用字母。
  • 特点：理论上 N 可以是任何大于等于 2 的整数。
  • 示例：七进制 (Base-7) 使用 0-6，123₇ = 1*7² + 2*7¹ + 3*7⁰ = 49 + 14 + 3 = 66₁₀
关键点：不同进制有不同的符号集和位权规则，二进制是计算机的基础，八/十六进制是其简写。

进制转换的基本思路

如何在不同进制之间转换呢？主要有两种策略：

1. 中转十进制法（最通用）：

  • 任意进制 → 十进制：使用“按权展开求和”法。将每一位数字乘以其对应的位权（基数的幂次方），然后相加。
  • 十进制 → 任意进制：使用“除基取余，逆序排列”法。不断用十进制数除以目标基数，记录每次的余数，直到商为0。将余数倒序排列即为结果。
  • 任意进制A → 任意进制B：先将 A 转换为 十进制，再将 十进制 转换为 B。

2. 直接转换法（特定情况）：

  • 二进制 ↔ 八进制：3位二进制 对应 1位八进制。
  • 二进制 ↔ 十六进制：4位二进制 对应 1位十六进制。
  • 利用这个关系可以快速互转，无需经过十进制。
关键点：掌握“按权展开”和“除基取余”是核心，十进制是重要的“中转站”。

算法演示：动手试试看！

请输入数值并选择进制，然后点击"开始转换"

👇

第一步：将 源进制() 转为 十进制
当前十进制累加值: 0
第二步：将 十进制() 转为 目标进制()
N ÷ B = Q ... R
(余数 ↓ 入栈)

🎉 转换完成！ 🎉

等待开始转换...
余数栈 (后进先出 LIFO)
中间十进制值
-
最终结果 (目标进制)
-

原理与代码：深入理解转换过程

1. 任意进制 (Base S) → 十进制 (Base 10)：“按权展开求和”

一个 Base S 的数 dndn-1...d1d0 (其中 di 是第 i 位的数字)，其十进制值计算如下：

Value10 = dn * Sn + dn-1 * Sn-1 + ... + d1 * S1 + d0 * S0

例如：十六进制数 1A516 转十进制 (S=16)

Value10 = 1 * 162 + A(10) * 161 + 5 * 160

Value10 = 1 * 256 + 10 * 16 + 5 * 1

Value10 = 256 + 160 + 5 = 42110

注意： 对于 A-F 或更高进制的字母，需要先转换为对应的十进制数值（A=10, B=11, ..., Z=35）。

2. 十进制 (Base 10) → 任意进制 (Base T)：“除基取余，逆序排列”

将十进制数 N 转换为 Base T 的数，步骤如下：

  1. 用 N 除以 T，得到商 Q1 和 余数 R1 (0 ≤ R1 < T)。R1 是目标数的最低位。
  2. 若 Q1 不为 0，则用 Q1 除以 T，得到商 Q2 和 余数 R2。R2 是次低位。
  3. 重复此过程，直到商 Qk 为 0。最后一个余数 Rk 是目标数的最高位。
  4. 将所有余数逆序排列 RkRk-1...R2R1，即得到 Base T 的表示。

例如：十进制数 4210 转二进制 (T=2)

  • 42 ÷ 2 = 21 ... 0 (R1)
  • 21 ÷ 2 = 10 ... 1 (R2)
  • 10 ÷ 2 = 5 ... 0 (R3)
  • 5 ÷ 2 = 2 ... 1 (R4)
  • 2 ÷ 2 = 1 ... 0 (R5)
  • 1 ÷ 2 = 0 ... 1 (R6)

逆序排列余数：101010。所以 42₁₀ = 101010₂。

注意： 如果余数大于9，需要转换为对应的字母（10=A, 11=B, ...）。这个过程天然地使用栈结构来存储余数，因为最后得到的余数最先输出。

3. 任意进制 (Base S) → 任意进制 (Base T)：“十进制中转”

结合以上两种方法：

Base S → Base 10 → Base T

这是处理任意进制间转换最通用和不易出错的方法。

// 全局常量/查找表 (用于处理 A-Z) Digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" // 函数：将任意进制字符串转换为十进制整数 function baseSToDecimal(numStr, baseS) { decimalValue = 0 power = 0 // 从字符串末尾（最低位）开始处理 for i from numStr.length - 1 down to 0 { digitChar = numStr[i] // 查找字符在 Digits 中的索引，即该位的十进制值 digitValue = indexOf(Digits, digitChar) // 检查数字是否合法（不能大于等于进制基数） if digitValue >= baseS or digitValue == -1 { return "错误：输入包含无效字符" } // 累加按权展开的值 decimalValue = decimalValue + digitValue * (baseS ** power) power = power + 1 } return decimalValue } // 函数：将十进制整数转换为任意进制字符串 function decimalToBaseT(decimalNum, baseT) { if decimalNum == 0 { return "0" } resultStr = "" num = decimalNum stack = createStack() // 使用栈来存储余数 // 除基取余法 while num > 0 { remainder = num % baseT // 将余数对应的字符压入栈 push(stack, Digits[remainder]) // 更新数值为商 num = floor(num / baseT) // 取整 } // 从栈中弹出字符，构建最终结果字符串 (逆序) while not isEmpty(stack) { resultStr = resultStr + pop(stack) } return resultStr } // 主转换函数 function convertBase(inputNumStr, baseS, baseT) { // 1. 源进制转十进制 decimalResult = baseSToDecimal(inputNumStr, baseS) if isError(decimalResult) { return decimalResult // 返回错误信息 } // 2. 十进制转目标进制 finalResult = decimalToBaseT(decimalResult, baseT) return finalResult }
// 包含必要的头文件 #include <iostream> #include <string> #include <vector> #include <algorithm> // 用于 reverse #include <cmath> // 用于 pow (或手动实现) #include <stack> // 可以使用栈简化 decimalToBaseT // 辅助函数：获取字符对应的十进制值 (0-35) int getCharValue(char c) { if (c >= '0' && c <= '9') { return c - '0'; } else if (c >= 'A' && c <= 'Z') { return c - 'A' + 10; } else if (c >= 'a' && c <= 'z') { // 也支持小写字母 return c - 'a' + 10; } return -1; // 无效字符 } // 辅助函数：获取十进制值对应的字符 (0-35) char getValueChar(int v) { if (v >= 0 && v <= 9) { return v + '0'; } else if (v >= 10 && v <= 35) { return v - 10 + 'A'; } return '\0'; // 无效值 } // 函数：任意进制字符串转十进制 (使用 long long 处理大数) long long baseSToDecimal(const std::string& numStr, int baseS, bool& error) { long long decimalValue = 0; long long power = 1; // 位权，从 S^0 开始 error = false; for (int i = numStr.length() - 1; i >= 0; --i) { int digitValue = getCharValue(numStr[i]); if (digitValue == -1 || digitValue >= baseS) { error = true; // 发现无效字符 return 0; } decimalValue += digitValue * power; // 防止溢出，并为下一位准备位权 if (i > 0) { // 检查 power * baseS 是否会溢出 long long if (power > (LLONG_MAX / baseS)) { // LLONG_MAX 在 <climits> error = true; // 位权计算溢出 return 0; } power *= baseS; } } return decimalValue; } // 函数：十进制转任意进制字符串 (使用 long long 处理大数) std::string decimalToBaseT(long long decimalNum, int baseT) { if (decimalNum == 0) { return "0"; } if (baseT < 2 || baseT > 36) { return "错误：目标进制无效"; } std::string resultStr = ""; std::stack<char> remainderStack; while (decimalNum > 0) { int remainder = decimalNum % baseT; remainderStack.push(getValueChar(remainder)); decimalNum /= baseT; } while (!remainderStack.empty()) { resultStr += remainderStack.top(); remainderStack.pop(); } return resultStr; } // 主转换函数 std::string convertBase(const std::string& inputNumStr, int baseS, int baseT) { if (baseS < 2 || baseS > 36 || baseT < 2 || baseT > 36) { return "错误：源或目标进制超出范围 (2-36)"; } bool conversionError = false; long long decimalValue = baseSToDecimal(inputNumStr, baseS, conversionError); if (conversionError) { if (decimalValue == 0 && inputNumStr != "0") { // 区分真正的0和错误 return "错误：输入包含无效字符或数值溢出"; } // 如果输入就是 "0"，没有错误 } return decimalToBaseT(decimalValue, baseT); } // --- 示例用法 --- /* int main() { std::string input = "1A"; int source = 16; int target = 2; std::string result = convertBase(input, source, target); std::cout << input << " (base " << source << ") = " << result << " (base " << target << ")" << std::endl; // 输出: 1A (base 16) = 11010 (base 2) input = "101010"; source = 2; target = 10; result = convertBase(input, source, target); std::cout << input << " (base " << source << ") = " << result << " (base " << target << ")" << std::endl; // 输出: 101010 (base 2) = 42 (base 10) input = "XYZ"; // 假设用 36 进制 source = 36; target = 10; result = convertBase(input, source, target); // X=33, Y=34, Z=35 => 33*36^2 + 34*36^1 + 35*36^0 = 42768 + 1224 + 35 = 44027 std::cout << input << " (base " << source << ") = " << result << " (base " << target << ")" << std::endl; // 输出: XYZ (base 36) = 44027 (base 10) return 0; } */

对于二进制与八进制、十六进制之间的转换，有更快捷的方法，无需经过十进制：

二进制 → 八进制：

  1. 从二进制数的小数点（或末尾）开始，向左每三位一组进行分组，不足三位的在高位补0。
  2. 将每组三位二进制数独立转换为对应的八进制数字（000₂=0₈, 001₂=1₈, ..., 111₂=7₈）。
  3. 将转换后的八进制数字按原顺序排列。

示例：11010110₂ → 分组 011 010 110 → 转换 3 2 6 → 结果 326₈

八进制 → 二进制：

  1. 将每一位八进制数字独立转换为对应的三位二进制数（不足三位在高位补0）。
  2. 将转换后的二进制数组按原顺序排列。

示例：72₈ → 转换 7=111₂, 2=010₂ → 结果 111010₂

二进制 ↔ 十六进制： 转换方法类似，只是分组/转换时按四位二进制进行。

示例：11010110₂ → 分组 1101 0110 → 转换 D 6 → 结果 D6₁₆

示例：A5₁₆ → 转换 A=1010₂, 5=0101₂ → 结果 10100101₂

这种方法在处理底层数据时非常高效。

当需要转换的数字非常大，超过了标准整数类型（如 C++ 的 `long long`）的表示范围时，就需要使用“大数”处理技术。通常有以下方法：

1. 使用字符串模拟运算：

  • 任意进制 → 十进制： 实现大数乘法和大数加法。按权展开时，每次乘以基数 S 和累加都需要用大数运算完成。
  • 十进制 → 任意进制： 实现大数除法和大数取模。不断用大数除以目标基数 T，记录余数。

这种方法实现相对复杂，需要自己编写或使用现成的大数库。

2. 借助现有大数库：

  • 很多编程语言提供了内置或第三方的大数库（如 Python 内置支持任意精度整数，Java 的 `BigInteger`，C++ 的 GMP 或 Boost.Multiprecision）。
  • 这些库通常已经实现了高效的大数算术运算，可以直接用于进制转换算法中。
  • 将输入字符串解析为库支持的大数对象，然后进行相应的乘、加、除、模运算，最后将结果格式化为目标进制的字符串。

性能考量： 大数运算比普通整数运算慢得多。对于非常大的数字，转换效率会显著降低。选择合适的算法和库实现很重要。