1. 从一道“看着简单”的题说起十六进制转八进制到底难在哪如果你刷过蓝桥杯基础练习的题目BASIC-12 这道“十六进制转八进制”大概率会在某个时刻让你停下来挠头。题目描述本身非常朴素给定若干个十六进制数要求输出对应的八进制表示。很多人第一反应是——这不就是个进制转换吗printf一行不就完事了但真正动手写的时候你会发现事情没那么简单。这道题之所以被归到“复杂进制转换”这一类核心原因在于数据规模。题目里的十六进制数长度可能达到十万位级别这意味着它远远超出了任何内置整数类型的表示范围。你没法用long long存也没法用unsigned long long存甚至用__int128都不够。这时候就必须回到进制转换的本质用字符串模拟手工转换的过程。我见过不少初学者在这道题上卡住不是因为不会进制转换的原理而是因为没意识到“大数”这个隐藏条件。他们写出来的代码在小数据上跑得好好的一提交就报错或者超时。所以这篇文章我想从头到尾把这道题拆开讲清楚为什么不能走捷径、中间进制该怎么选、字符串模拟的每一步在做什么、以及那些只有真正踩过坑才知道的细节。适合读这篇内容的人包括正在准备蓝桥杯的同学、想复习进制转换底层原理的开发者以及任何对“大数处理”这个话题感兴趣的人。哪怕你之前没接触过蓝桥杯只要你会基本的 C 或 C 语法跟着思路走一遍也能把这道题吃透。2. 为什么不能一步到位十六进制直接转八进制的数学障碍2.1 进制转换的通用思路与它的局限先回顾一下进制转换的基本方法。把一个 r1 进制的数转成 r2 进制最通用的做法是先把它转成十进制再从十进制转成目标进制。转十进制的时候按位展开求和转目标进制的时候不断取余和整除。这个方法在数值不大的时候完全没问题但在这道题里行不通因为中间结果会大到无法存储。那有没有办法跳过十进制理论上如果两个进制的基数之间存在幂次关系比如十六进制16和二进制2因为 16 2^4所以每一位十六进制数恰好对应四位二进制数可以直接按位展开。同理八进制8和二进制之间因为 8 2^3每一位八进制数对应三位二进制数。但十六进制和八进制之间不存在这种直接的幂次关系。16 是 2 的 4 次方8 是 2 的 3 次方它们都是二的幂但 4 和 3 不相等所以没法像十六进制转二进制那样“一位对四位”地直接映射。这就是这道题被称为“复杂进制转换”的根本原因。2.2 二进制作为桥梁4 和 3 的最小公倍数思路既然十六进制和八进制都跟二进制有直接的幂次关系那二进制自然就成了最合适的中间桥梁。具体来说十六进制转二进制每一位十六进制数展开成四位二进制数二进制转八进制每三位二进制数合并成一位八进制数这个思路之所以可行是因为它完全避开了大数运算。整个过程都是在字符串层面做字符替换和分组不涉及任何数值计算所以无论输入多长都不会溢出。但这里有一个关键细节从十六进制展开成二进制之后二进制串的长度是 4 的倍数而转成八进制需要按 3 位一组来划分。4 和 3 的最小公倍数是 12也就是说为了让分组对齐我们可能需要在二进制串前面补零使得它的长度既是 4 的倍数这个天然满足又是 3 的倍数。提示补零只能在最高位前面补不能在末尾补否则会改变数值大小。这一点在后面讲具体实现时会反复强调。2.3 为什么不用十进制中转一个直观的对比为了让你更清楚地理解为什么二进制中转是最优解我做一个简单的对比。假设输入是一个 100000 位的十六进制数中转方式中间数据规模是否需要大数运算实现难度十进制中转约 120000 位十进制数需要高二进制中转约 400000 位二进制串不需要低直接映射不存在——用十进制中转的话你需要实现大数的乘法和加法代码量会翻好几倍而且容易出错。用二进制中转你只需要做字符到字符串的映射以及简单的分组处理代码量小、逻辑清晰、不容易出 bug。这也是绝大多数人在蓝桥杯赛场上会选择的做法。3. 字符串模拟的完整链路从读入到输出的每一步3.1 输入处理为什么必须用字符串读入第一步就有一个容易被忽略的点输入格式。题目通常会先给一个整数 n表示后面有 n 个十六进制数然后每行一个。这些十六进制数可能非常长所以必须用字符串来接收。在 C 里可以用std::string配合cin来读在 C 里需要开一个足够大的字符数组用scanf读入。这里有一个细节如果输入可能包含前导零用字符串读入可以原样保留而如果用数值读入就会丢失前导零的信息。虽然前导零不影响数值大小但在某些题目的输出要求里可能会影响格式判断所以用字符串读入是最稳妥的。另外输入的数量 n 可能也不小如果每个字符串都很长总体数据量会很大。这时候 I/O 效率就变得重要了。在 C 里可以加ios::sync_with_stdio(false)来加速在 C 里用scanf本身就比cin快。这个细节在数据量大的时候可能就是“通过”和“超时”的区别。3.2 十六进制到二进制的映射表一张表解决所有问题十六进制有 16 个字符0-9 和 A-F或者小写 a-f。每个字符对应一个四位二进制串。我们可以预先建一张映射表十六进制字符二进制串00000100012001030011401005010160110701118100091001A / a1010B / b1011C / c1100D / d1101E / e1110F / f1111有了这张表转换过程就变成了遍历输入字符串对每个字符查表把对应的四位二进制串拼接到结果字符串后面。这个过程是 O(n) 的n 是输入字符串的长度效率非常高。注意拼接的时候不要用字符串加法在循环里反复创建新字符串那样会导致 O(n²) 的时间复杂度。正确做法是预先分配好足够大的空间或者用std::string的append方法配合reserve预分配。3.3 二进制串的对齐处理补零的位置和数量得到二进制串之后下一步是把它按三位一组划分。但二进制串的长度是 4 的倍数不一定是 3 的倍数。所以需要先补零使得长度变成 3 的倍数。补零的数量怎么算假设二进制串长度为 len那么需要补的零的个数是(3 - len % 3) % 3。这个公式的意思是如果 len 已经是 3 的倍数就补 0 个否则补到下一个 3 的倍数。补零的位置是在二进制串的最前面。比如二进制串是1010长度为 4需要补 2 个零变成001010长度为 6然后分成001和010两组分别对应八进制的 1 和 2结果是12。这里有一个常见的错误有人会在二进制串后面补零这样会改变数值大小。比如1010后面补两个零变成101000分组后是101和000对应八进制的 5 和 0结果是50这显然是错的。3.4 三位一组转八进制分组与输出的细节补零之后二进制串的长度就是 3 的倍数了。接下来每三位一组计算对应的八进制数字。三位二进制数的范围是 000 到 111对应十进制 0 到 7正好就是八进制的一位数。计算方式很简单把三位二进制数当成一个整体第一位乘以 4第二位乘以 2第三位乘以 1然后相加。比如101 1×4 0×2 1×1 5。把所有组的结果拼接起来就是最终的八进制字符串。但这里还有一个细节前导零的处理。如果最高位的组计算结果是 0按照数值表示的习惯应该去掉这个前导零。比如二进制串000101分组后是000和101对应八进制的 0 和 5结果应该是5而不是05。但要注意如果整个数就是 0那输出应该是0不能去掉所有的零。这个边界条件在实现的时候需要特别处理。4. 那些只有踩过才知道的坑实现中的高频错误与排查4.1 前导零的取舍什么时候该去什么时候该留前导零的处理是这道题最容易出错的地方之一。我总结了几种情况如果最高位的八进制数字是 0且后面还有非零数字去掉这个 0如果所有位都是 0保留一个 0中间的零不能去掉比如105不能变成15实现的时候可以在输出前做一个判断找到第一个非零字符的位置从那里开始输出如果找不到非零字符就输出一个0。这个逻辑看起来简单但在字符串拼接的过程中很容易搞混。我建议的做法是先把所有八进制数字存到一个数组或字符串里最后统一处理前导零而不是在拼接的过程中边拼边判断。4.2 字符串拼接的性能陷阱为什么你的代码超时了前面提到过在循环里用字符串加法会导致 O(n²) 的时间复杂度。这个问题在数据量小的时候看不出来但在这道题里输入可能有十万位展开成二进制就是四十万位如果用字符串加法时间会爆炸。正确的做法有两种预先分配足够大的字符数组用下标直接赋值用std::string的reserve预分配空间然后用push_back或append追加在 C 里std::string的操作在容量足够的情况下是均摊 O(1) 的所以配合reserve使用是安全的。但如果不reserve当字符串增长超过当前容量时会触发重新分配和拷贝虽然均摊下来还是 O(n)但常数会大很多。提示如果你用 C 语言的字符数组记得把数组开得足够大。输入长度是 L 的话二进制串长度是 4L八进制串长度大约是 4L/3再加上补零的空间数组大小至少要是 4L 10。4.3 大小写敏感与非法字符输入健壮性的考量题目里的十六进制数可能用大写字母也可能用小写字母。如果你的映射表只处理了大写遇到小写就会出错。解决办法是在查表之前统一转成大写或者在映射表里同时包含大小写。另外虽然题目保证输入是合法的十六进制数但在实际调试的时候可能会遇到一些意外情况比如输入里混入了空格或换行符。用cin string或scanf(%s)读入的时候这些空白字符会被自动跳过所以一般不会有问题。但如果用getline读入就需要自己处理。4.4 多组输入的循环处理别忘了清空状态题目通常会有多组输入每组处理完之后用于存储中间结果的字符串或数组需要清空否则上一组的数据会污染下一组的结果。在 C 里如果用std::string每次重新声明一个局部变量就行如果用全局数组记得用memset或手动清零。这个坑在单组测试的时候不会暴露但一提交就会出错。我见过不少人在这上面栽跟头调试了半天才发现是没清空。5. 从能跑到跑得好优化思路与代码组织建议5.1 预计算映射表用空间换时间的经典操作前面提到的十六进制到二进制的映射表可以用一个字符串数组来存储const char* hexToBin[16] { 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 };查表的时候把十六进制字符转成对应的下标0-9 转 0-9A-F 转 10-15然后直接取字符串。这样比用switch或if-else链要快得多代码也更简洁。5.2 二进制转八进制的三种写法对比二进制转八进制这一步有三种常见的写法写法一逐位计算int val (bin[i] - 0) * 4 (bin[i1] - 0) * 2 (bin[i2] - 0);这种写法最直观每次处理三位计算量小适合初学者。写法二查表法预计算 8 个三位二进制串对应的八进制字符const char* binToOct[8] {0, 1, 2, 3, 4, 5, 6, 7};然后把三位二进制串转成下标000 转 0001 转 1...111 转 7直接查表。这种写法比逐位计算稍快但差别不大。写法三位运算int val ((bin[i] - 0) 2) | ((bin[i1] - 0) 1) | (bin[i2] - 0);用位运算代替乘法和加法理论上最快但可读性稍差。在实际比赛中三种写法的性能差异微乎其微选你写得最顺手的就行。5.3 代码结构把转换拆成独立的函数这道题的逻辑可以拆成三个独立的步骤十六进制转二进制、二进制转八进制、以及前导零处理。把每个步骤封装成独立的函数不仅代码更清晰调试的时候也更容易定位问题。比如std::string hexToBinary(const std::string hex); std::string binaryToOctal(const std::string bin); std::string removeLeadingZeros(const std::string oct);这样主函数就变成了三行调用逻辑一目了然。如果某一步出了问题你可以单独测试那个函数不用每次都跑完整流程。5.4 测试用例的设计从边界到极端设计测试用例的时候至少要覆盖以下几种情况测试类型输入示例预期输出考察点最小输入00零值处理单位数F17基本转换前导零0F17前导零去除长度非3倍数FF377补零对齐长度是3倍数FFF7777无需补零大数很长的十六进制串对应八进制性能与正确性我建议在本地测试的时候先用小数据验证逻辑正确性再用大数据测试性能。如果小数据都对不上那就别急着测大数据了先把逻辑理清楚。6. 这道题真正教会我的事进制转换之外的收获6.1 大数处理的通用思路字符串模拟这道题表面上考的是进制转换实际上考的是大数处理。当数值超出内置类型的表示范围时字符串模拟是通用的解决方案。这个思路不仅适用于进制转换还适用于大数加法、大数乘法、大数比较等场景。我在实际工作中遇到过类似的问题比如处理超长的订单号、超大的文件哈希值用的都是字符串模拟的思路。所以这道题的价值不仅仅在于学会一道题而在于掌握一种处理问题的思维方式。6.2 中间表示的选择为什么二进制是“万能桥梁”十六进制和八进制都跟二进制有直接的幂次关系所以二进制可以作为它们之间的桥梁。这个思路可以推广到其他进制只要两个进制的基数都是同一个数的幂就可以用那个数作为中间进制。比如四进制和八进制都可以用二进制作为桥梁因为 4 2²8 2³。九进制和二十七进制可以用三进制作为桥梁因为 9 3²27 3³。这个规律在进制转换的题目里非常有用。6.3 性能意识从“能跑”到“跑得好”的思维转变很多初学者写代码只求“能跑”不考虑性能。但在竞赛和实际工程中性能往往是决定成败的关键。这道题就是一个很好的例子同样的逻辑用字符串加法拼接和用预分配数组性能可能差几十倍。培养性能意识的方法很简单每次写完代码想一想“如果数据量放大一百倍这段代码还能跑吗”如果答案是否定的就去找瓶颈在哪里然后优化它。这个习惯一旦养成你的代码质量会有质的飞跃。6.4 边界条件的敏感性细节决定成败前导零、零值、长度对齐这些都是边界条件。在竞赛中很多题目不是难在核心逻辑而是难在边界条件的处理。一个边界条件没考虑到就可能从“通过”变成“错误”。我的经验是写完代码之后不要急着提交先自己构造几组边界数据跑一遍。比如输入是 0、输入只有一位、输入长度刚好是 3 的倍数、输入长度差一位就是 3 的倍数这些情况都要覆盖到。养成这个习惯之后你的通过率会明显提高。6.5 从这道题延伸出去还能练什么如果你已经把这道题吃透了可以尝试以下几个延伸练习把十六进制转八进制改成任意进制转任意进制要求支持大数实现大数的加减乘除同样用字符串模拟研究不同进制之间的快速转换算法比如用分治法处理超长数据把这套逻辑移植到其他语言比如 Python 或 Java对比不同语言的实现差异这些练习不仅能巩固你对进制转换的理解还能提升你处理大数问题的能力。在算法竞赛和实际工程中这些技能都是非常实用的。最后分享一个我在调试这类题目时的小技巧把中间结果打印出来。比如十六进制转二进制之后把二进制串打印出来看看对不对补零之后再打印一次看看长度是不是 3 的倍数。这样一步步验证比盯着代码空想效率高得多。很多时候问题就出在某个中间步骤上打印出来一眼就能看出来。