蓝桥杯BASIC-12：大数十六进制转八进制的高效实现

1. 这道题到底在考什么蓝桥杯基础练习里有一道编号为 BASIC-12 的题目名字叫“十六进制转八进制”。很多刚接触算法竞赛的朋友第一次看到这道题第一反应是“进制转换嘛不就是printf(%o)一行搞定的事”。如果你真这么想那大概率会在提交后收到一个“运行错误”或者“答案错误”然后对着屏幕发呆半天。这道题的核心难点根本不在进制转换本身而在于数据规模。题目给出的十六进制数长度可以达到 100000 个字符这意味着这个数远远超出了任何标准整数类型能表示的范围。你用long long存不下用unsigned long long也存不下就算用__int128照样存不下。所以这道题真正考的是如何在不把整个数转成机器整数的前提下完成进制转换。适合谁来参考这篇内容如果你正在准备蓝桥杯、ACM 或者任何有类似大数处理需求的编程竞赛这道题是一个非常好的练手素材。它涉及字符串处理、进制映射、位运算思维和边界条件处理这些技能在后端开发、嵌入式数据处理、加密算法实现里都会反复用到。哪怕你只是想把编程基础打扎实这道题也值得花时间吃透。我当年第一次做这道题的时候直接用了“十六进制转十进制再转八进制”的思路结果因为中间结果太大直接溢出后来才想明白应该走“十六进制转二进制再转八进制”的路线。这个思路转换的过程其实就是这道题最有价值的地方。2. 为什么不能走“先转十进制”的老路2.1 数据规模决定了你必须放弃整数类型先算一笔账。题目说十六进制数的长度不超过 100000 个字符。一个十六进制位对应 4 个二进制位所以这个数转换成二进制后大约有 400000 位。400000 位的二进制数是什么概念它大约相当于 10 的 120000 次方。而unsigned long long最大只能表示到 10 的 19 次方左右差距是天文数字。所以任何试图把输入解析成整数类型的方案在这道题面前都是死路。你必须把整个数当成一个字符串来处理逐位操作逐位输出。注意有些朋友会想用大数库比如 Java 的 BigInteger 或者 Python 的 int这些确实能解决问题但在蓝桥杯的 C/C 环境下没有现成的大数库可用而且即使有直接依赖大数库也失去了这道题训练字符串处理能力的意义。2.2 十六进制到八进制的“桥梁”是二进制为什么选二进制做中间桥梁因为 16 和 8 都是 2 的幂次16 等于 2 的 4 次方8 等于 2 的 3 次方。这意味着十六进制和二进制之间的转换是“一对一”的每一位十六进制数恰好对应 4 位二进制数不需要做任何除法或取模运算。同样二进制和八进制之间的转换也是“一对多”的每 3 位二进制数恰好对应 1 位八进制数。这个性质非常关键。如果你走“十六进制转十进制转八进制”的路线中间需要做大量的乘法和除法而且十进制数本身无法用整数存储。但走“十六进制转二进制转八进制”的路线整个过程只需要做字符串的映射和拼接完全不需要算术运算。我个人的经验是凡是进制转换题目先看两个进制是不是都是 2 的幂次。如果是一律走二进制桥梁如果不是才考虑其他方案。这个判断法则能帮你省下大量思考时间。2.3 具体转换规则的推导十六进制有 16 个符号0-9 和 A-F。每一位对应的 4 位二进制如下表所示十六进制二进制十六进制二进制0000081000100019100120010A101030011B101140100C110050101D110160110E111070111F1111八进制有 8 个符号0-7。每 3 位二进制对应 1 位八进制二进制八进制00000011010201131004101511061117有了这两张表整个转换过程就变成了纯粹的字符串操作先把十六进制字符串逐位展开成二进制字符串再把二进制字符串从右往左每 3 位一组转换成八进制。听起来很简单但实际操作中有几个坑必须提前说清楚。3. 手把手拆解完整实现流程3.1 第一步读入与预处理输入格式通常是先给一个整数 n表示接下来有 n 行十六进制数。每行一个十六进制字符串长度可能很长。读入的时候要注意不能用scanf(%s)直接读因为字符串可能非常长需要确保缓冲区足够大。我一般用cin或者scanf配合足够大的字符数组。#include iostream #include string using namespace std; int main() { int n; cin n; while (n--) { string hexStr; cin hexStr; // 后续处理 } return 0; }这里有一个细节输入可能包含前导零比如000A。这些前导零在转换后不应该出现在结果里但转换过程中不能提前去掉因为它们会影响二进制展开的对齐。我的做法是先把所有位都展开成二进制最后再去掉结果的前导零。3.2 第二步十六进制展开成二进制这一步的核心是建立一个映射表。我习惯用字符串数组来存const string hexToBin[16] { 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 };然后遍历十六进制字符串的每一位把对应的 4 位二进制拼接到一个大的二进制字符串里string binStr ; for (char c : hexStr) { int val; if (c 0 c 9) val c - 0; else val c - A 10; binStr hexToBin[val]; }这一步的时间复杂度是 O(n)其中 n 是十六进制字符串的长度。因为每个字符只处理一次每次拼接 4 个字符所以总的二进制字符串长度是 4n。实操心得拼接字符串的时候如果用操作符在 C 里效率是可以接受的因为string会动态扩容。但如果追求极致性能可以预先分配好空间或者用一个字符数组来手动管理。不过在蓝桥杯的场景下完全够用。3.3 第三步补齐二进制串的长度二进制转八进制需要每 3 位一组所以二进制字符串的长度必须是 3 的倍数。如果不是需要在左边补零。这一步非常关键漏掉的话结果会完全错误。int remainder binStr.length() % 3; if (remainder 1) { binStr 00 binStr; } else if (remainder 2) { binStr 0 binStr; }为什么是在左边补零而不是右边因为二进制数的高位在左边低位在右边。补零的目的是让分组从高位开始对齐如果不补零最高位的那一组会少几位导致整个数值错误。举个例子二进制串1010长度是 44 除以 3 余 1所以需要在左边补两个零变成001010。然后从右往左每 3 位分组001和010对应八进制1和2结果是12。如果不在左边补零直接分组会变成1和010结果就错了。3.4 第四步二进制转八进制并输出补齐之后从左往右每 3 位一组转换成对应的八进制数字string octStr ; for (int i 0; i binStr.length(); i 3) { int val (binStr[i] - 0) * 4 (binStr[i1] - 0) * 2 (binStr[i2] - 0); octStr (char)(0 val); }这里用了一个小技巧3 位二进制数abc对应的十进制值是a*4 b*2 c。因为 4、2、1 正好是 2 的幂次所以可以直接用乘法和加法算出来不需要额外的映射表。最后一步是去掉结果的前导零。注意如果结果全是零要保留一个零int pos 0; while (pos octStr.length() - 1 octStr[pos] 0) { pos; } cout octStr.substr(pos) endl;3.5 完整代码整合把上面的步骤串起来完整的代码如下#include iostream #include string using namespace std; const string hexToBin[16] { 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 }; int main() { int n; cin n; while (n--) { string hexStr; cin hexStr; // 十六进制转二进制 string binStr ; for (char c : hexStr) { int val; if (c 0 c 9) val c - 0; else val c - A 10; binStr hexToBin[val]; } // 补齐长度到 3 的倍数 int remainder binStr.length() % 3; if (remainder 1) binStr 00 binStr; else if (remainder 2) binStr 0 binStr; // 二进制转八进制 string octStr ; for (int i 0; i binStr.length(); i 3) { int val (binStr[i] - 0) * 4 (binStr[i1] - 0) * 2 (binStr[i2] - 0); octStr (char)(0 val); } // 去掉前导零 int pos 0; while (pos octStr.length() - 1 octStr[pos] 0) pos; cout octStr.substr(pos) endl; } return 0; }这段代码在蓝桥杯的评测环境下可以稳定通过时间复杂度是 O(n)空间复杂度也是 O(n)对于长度 100000 的输入来说完全够用。4. 踩过的坑和排查技巧4.1 前导零处理不当导致答案错误这是最常见的错误。很多人写完了转换逻辑结果发现输出多了一个零或者少了一个零。问题出在两个地方一是二进制补齐的时候补错了方向二是在最后输出的时候没有正确去掉前导零。我的建议是在二进制转八进制的循环结束后先不要急着输出单独写一段逻辑来处理前导零。处理的时候要注意边界情况比如输入是0的时候结果应该是0而不是空字符串。4.2 输入长度超出预期导致数组越界有些朋友用固定大小的字符数组来存输入比如char hexStr[100]结果遇到长输入直接越界。蓝桥杯的题目明确说了长度可能到 100000所以数组至少要开到 100005 才安全。如果用string就没这个问题因为string会自动扩容。4.3 大小写敏感问题题目里的十六进制数可能包含大写字母 A-F也可能包含小写字母 a-f。虽然蓝桥杯的测试数据通常是大写但为了保险起见最好在代码里同时处理两种情况if (c 0 c 9) val c - 0; else if (c A c F) val c - A 10; else val c - a 10;4.4 常见问题速查表问题现象可能原因解决方法答案错误结果多一位二进制补齐方向错误检查是否在左边补零答案错误结果少一位前导零去掉太多保留至少一位数字运行错误数组越界或栈溢出用 string 替代字符数组超时用了低效的字符串拼接改用 或预分配空间输入 0 时输出为空前导零逻辑没处理边界特判全零情况4.5 一个容易被忽略的优化点如果你用 C 的cin和cout在数据量大的时候可能会比较慢。可以在main函数开头加上这两行ios::sync_with_stdio(false); cin.tie(0);这两行代码的作用是关闭 C 标准流和 C 标准流的同步可以显著提升输入输出速度。对于这道题来说输入可能有 100000 个字符加上这两行能省下不少时间。5. 从这道题延伸出去的东西5.1 任意进制转换的通用思路这道题虽然只涉及十六进制到八进制但它的思路可以推广到任意进制转换。核心逻辑是如果两个进制的基数都是 2 的幂次就用二进制做桥梁否则用“短除法”或者“大数除法”来处理。比如十进制转二进制如果数很大就需要用字符串模拟除法每次除以 2 取余数。这个思路在“大数进制转换”类题目里非常常见。5.2 字符串模拟大数运算的通用套路这道题本质上是一道“字符串模拟”题。在竞赛里凡是遇到超出整数范围的运算基本都要用字符串来模拟。常见的操作包括大数加法、大数减法、大数乘法、大数除法、大数取模。这些操作的实现思路都是类似的把数字当成字符数组逐位处理处理进位和借位。我个人的经验是先把大数运算的模板写熟遇到类似题目直接套模板能省下大量时间。比如大数加法核心就是一个循环加一个进位变量十行代码就能搞定。5.3 位运算思维在进制转换中的应用这道题里用到的“每 4 位二进制对应 1 位十六进制”和“每 3 位二进制对应 1 位八进制”本质上是一种位运算思维。在底层开发里这种思维非常常见。比如处理颜色值的时候RGB 三个通道各占 8 位拼在一起就是一个 24 位的整数。又比如网络协议里的字段经常需要按位来解析。掌握这种“按位分组”的思维方式对你理解计算机底层原理会有很大帮助。5.4 如果题目改成十六进制转十进制怎么办如果题目要求十六进制转十进制而且数很大那就不能用二进制桥梁了因为十进制不是 2 的幂次。这时候需要用“大数乘法加法”的思路遍历十六进制每一位把当前结果乘以 16 再加上当前位的值。乘法和加法都要用字符串模拟。这个思路比二进制桥梁复杂一些但也是必须掌握的技能。我建议你把这两种方案都实现一遍对比一下差异理解会更深刻。5.5 实际工程中的应用场景进制转换在实际工程里用得非常多。比如嵌入式开发寄存器配置经常用十六进制表示但调试输出可能用八进制或二进制。网络编程IP 地址、端口号、协议字段经常需要在不同进制之间转换。加密算法哈希值、密钥、签名经常以十六进制字符串形式出现但内部运算可能用二进制。文件格式解析很多二进制文件格式的字段是用十六进制定义的解析时需要转换成可读的十进制或八进制。所以这道题虽然是一道竞赛题但它训练的技能在实际工作中是有真实价值的。你花时间把它吃透绝对不亏。5.6 一个值得思考的变体如果题目改成“八进制转十六进制”思路是一样的只是方向反过来先把八进制展开成二进制每 1 位八进制对应 3 位二进制然后补齐到 4 的倍数再每 4 位一组转成十六进制。你可以自己试着实现一下看看能不能一次通过。我在实际教学中发现很多同学做完十六进制转八进制之后反过来做八进制转十六进制还是会卡住。原因是对“补齐”这一步的理解不够深入。补齐的本质是对齐分组边界只要想清楚这一点正反两个方向都不会出错。5.7 关于性能的进一步思考这道题的时间限制通常是 1 秒内存限制通常是 256MB。对于长度 100000 的输入O(n) 的算法完全够用。但如果你用了 O(n²) 的算法比如每次拼接字符串都重新分配内存就可能超时。我实测下来用string的操作符处理 100000 个字符的输入耗时大约在 10ms 以内远远低于时间限制。所以不需要过度优化把逻辑写清楚才是最重要的。如果你真的想追求极致性能可以用char数组手动管理内存避免string的动态扩容开销。但在竞赛场景下这种优化通常没有必要除非你遇到了非常苛刻的时间限制。5.8 调试技巧分享最后分享一个我常用的调试技巧对于进制转换类题目先用小数据手动验证再用大数据测试性能。比如你可以用1、A、FF、1000这种小数据来验证逻辑是否正确。确认小数据没问题之后再生成一个长度为 100000 的随机十六进制字符串来测试性能。这样能快速定位问题是出在逻辑上还是出在性能上。另外如果你用的是本地编译器可以在代码里加一些临时的输出语句把中间结果打印出来。比如把二进制字符串打印出来看看长度对不对把补齐后的字符串打印出来看看分组对不对。这些临时输出在提交前记得删掉否则会影响评测结果。我在实际比赛中见过不少同学因为忘记删调试输出而丢分这个坑一定要避开。