← 目录 / 算法文档 · 模块一 数学基础 / 1.6 进制转换

1.6　进制转换

二进制、八进制、十六进制和十进制之间互相转换——本质上还是 1.1 学过的"拆数字"和"拼数字"，只是把固定的 10 换成了别的数。

本页目录
① 什么是进制

我们平时写数字用的是十进制——大概是因为人有十个手指，数到 10 就习惯往前进一位。但"凑够几个就进一位"这个规则，其实和 10 没有必然联系：只要规定好这个"门槛"，可以用任何数字代替。二进制是凑够 2 个就进一位，八进制是凑够 8 个，十六进制是凑够 16 个——这个"门槛"就叫基数（base）。

1.1 节学过，十进制的每一位都有自己的"位权"：个位是 1，十位是 10，百位是 100……每往左一位，位权就乘 10。其他进制也完全一样的道理，只是位权乘的不是 10，而是各自的基数：

同一个数量，用不同进制表示 —— 位权乘的"倍数"不一样
1
×10
十位
3
×1
个位
十进制 "13" = 1×10 + 3×1 = 13
1
×8
第4位
1
×4
第3位
0
×2
第2位
1
×1
第1位
二进制 "1101" = 1×8 + 1×4 + 0×2 + 1×1 = 13
两组数字代表的数量完全一样（都是 13），只是因为"换了一种数法"，写出来的样子完全不同。十进制每往左一位乘 10，二进制每往左一位只乘 2——这就是为什么同样大小的数，二进制写出来位数会更多。
💡
常见的几种进制：二进制（基数 2，只用 0、1 两个数字）是计算机底层真正使用的进制；八进制（基数 8，用 0~7）和十六进制（基数 16，用 0~9 和 A~F 表示 10~15）则是为了让二进制写得更短一些，方便程序员阅读——三位二进制正好对应一位八进制，四位二进制正好对应一位十六进制。
② 其他进制 → 十进制

这个方向最直接——按照上面位值分解的思路，把每一位乘上它的位权，加起来就行。写代码的时候，有一个比"挨个算位权再相加"更顺手的写法：从左往右读这个数的每一位，每读一位就让"当前结果"乘一次基数、再加上这一位的数字。这个公式眼熟吗——result = result * base + digit，和 1.1 节 ReverseNumber 里的 rev = rev * 10 + digit 长得几乎一样，只是这里从左往右读（不需要倒序），乘的是 base，不是固定的 10。

C++ · 其他进制转十进制
1int ToDecimal(string s, int base)
2{
3 int result = 0;
4 for (int i = 0; i < s.length(); i++)
5 {
6 int digit;
7 if (s[i] >= '0' && s[i] <= '9')
8 {
9 digit = s[i] - '0';
10 }
11 else
12 {
13 digit = s[i] - 'A' + 10; // 处理16进制里的 A~F
14 }
15 result = result * base + digit;
16 }
17 return result;
18}
ToDecimal("1101", 2) 逐步执行过程
当前字符digitresult = result × 2 + digit
'1'→1→0×2+1 = 1
'1'→1→1×2+1 = 3
'0'→0→3×2+0 = 6
'1'→1→6×2+1 = 13
字符串读完 —— result = 13
从左往右每读一位，"当前结果"就先乘一次基数（相当于把之前的结果集体"挪一位"，给新数字腾出位置），再把新数字加进去——这正好和位权的累积方式完全对应。
③ 十进制 → 任意进制

这个方向反过来——其实就是 1.1 节最基础的"拆数字"，只是把固定的 % 10 和 / 10 换成了 % base 和 / base。每次拆出来的余数，就是目标进制下的一位数字；不断拆，直到数字变成 0 为止。

13 → 二进制 —— 反复 % 2 和 / 2
nn % 2（这一位）n / 2 之后
13取出 →1→ 变成6
6取出 →0→ 变成3
3取出 →1→ 变成1
1取出 →1→ 变成0
n = 0，结束 —— 取出的数字依次是：1 0 1 1
和 1.1 节一模一样的道理——第一个取出来的数字，是最终结果的最后一位（个位）。取出的顺序是 1 0 1 1，但真正的二进制写法应该是倒过来的 1101。
⚠️
别忘了倒过来！这是这个方向最容易出错的地方——拆出来的数字顺序和最终答案是反的。处理办法很简单：每拆出一个新数字，就把它拼到已有结果的最前面（而不是最后面），这样收集完之后就自动是正确顺序，不需要额外再反转一次。
C++ · 十进制转任意进制
1string ToBase(int n, int base)
2{
3 if (n == 0) return "0";
4 string result = "";
5 while (n != 0)
6 {
7 int digit = n % base;
8 char ch;
9 if (digit < 10)
10 {
11 ch = '0' + digit;
12 }
13 else
14 {
15 ch = 'A' + digit - 10; // 处理16进制里的 A~F
16 }
17 result = ch + result; // 新数字拼到最前面，自动得到正确顺序
18 n /= base;
19 }
20 return result;
21}
📌
递归写法同样很自然："先递归处理剩下更高位的部分，再把当前这一位接到后面"——递归调用天然会先把更靠前的部分处理完，等它返回之后，再把当前位拼上去，根本不需要"拼到最前面"这个技巧：
C++ · 十进制转任意进制（递归写法）
1string ToBase(int n, int base)
2{
3 int digit = n % base;
4 char ch = (digit < 10) ? ('0' + digit) : ('A' + digit - 10);
5 if (n < base) return string(1, ch); // 递归出口：只剩最高位了
6 return ToBase(n / base, base) + ch; // 先处理更高位，再接上当前这一位
7}
ToBase(13, 2) 的递归调用链
ToBase(13, 2)
13≥2，调用
↓
ToBase(6, 2)
6≥2，调用
↓
ToBase(3, 2)
3≥2，调用
↓
ToBase(1, 2)
1 < 2，递归到底 —— 直接返回 "1"
ToBase(3, 2) 收到 "1"，接上自己的 3%2=1 → 返回 "11"
ToBase(6, 2) 收到 "11"，接上自己的 6%2=0 → 返回 "110"
ToBase(13, 2) 收到 "110"，接上自己的 13%2=1 → 返回 "1101"
递归"往下调用"的时候只管把问题变小（n 不断除以 base），真正"拼字符串"的动作发生在"往上返回"的过程中——每一层把自己负责的那一位，接在从更高位那一层传回来的结果后面，最终拼出来的顺序自然就是正确的。
④ 完整代码与实用技巧
方向核心写法对应 1.1 节的哪个工具
其他进制→十进制result = result × base + digit（从左往右）ReverseNumber 的累积公式
十进制→任意进制digit = n % base；n /= base（循环到 0）最基础的拆数字写法
💡
C++ 自带的进制小工具：cout << hex << n 可以直接把 n 按十六进制输出，cout << oct << n 对应八进制——用完记得 cout << dec 切回十进制，否则后面的输出都会被影响。但二进制没有现成的输出方式，如果只是想快速看看一个数的二进制形式（不要求手写转换过程），可以借用上一章学过的 bitset：cout << bitset<8>(n) 会把 n 按 8 位二进制打印出来。不过竞赛题如果要求"实现进制转换"，通常还是要自己手写本节的算法，不能只靠这些输出技巧应付。
📌
本节只讨论非负整数的进制转换。负数在二进制下的表示方法（补码）属于更底层的内容，已经在第七章位运算里通过 ~n = -(n+1) 这类规律接触过，这里不再重复展开。