第一次在算法题单里看到“B进制星球”这个名字的时候我还以为是个星际探索模拟题点进去才发现是个高精度加法题给你一个进制 B再给两个 B 进制的大数字符串要你算出它们的和并且结果仍然用 B 进制输出。这名字起得确实很有迷惑性但题目本身是极其经典的进制模拟题。B进制的出镜率很高数组/字符串的高精度处理、字符与数字的映射、进位的边界判断全挤在这一道题里。对于刚学高精度或者看到“B进制”三个字就发怵的人来说这道题值得完整啃一遍。下面我就以实操的角度把这道题的完整思路、能直接提交的代码、以及我实际调试时踩过的几个坑写清楚希望能帮你少走一点弯路。1. 题目在问什么B进制、高精度、字符串三件事搅在一起1.1 名不副实的“星球题”一次被封面骗了的开题经历“B进制星球”这个题目表面上像是在描述某个外星文明使用的计数系统实际上它就是在考两件事一是你对“进制”这个概念是不是真懂二是你能不能手写一个高精度加法。题目一般是这样第一行给一个整数 B表示进制B 的范围通常在 2 到 36 之间。接下来给两个由字符构成的 B 进制大数可能长度能达到几百上千位。数字部分用0-9表示超过 9 的部分用大写字母A-Z表示。比如在 16 进制里A代表 10F代表 15在 36 进制里Z就代表 35。要求把两个数相加输出 B 进制的结果。很多人看到“进制”就条件反射地想去调用转换函数看到“大数”就想去开BigInteger这其实都不是这道题的正确打开方式。它的正确打开方式是你得理解高精度加法到底在模拟什么以及为什么 B 进制的进位规则和十进制没有本质区别。1.2 进制的本质从钟表的“逢60进一”说起进制这东西听起来很数学实际上你每天都在用。钟表就是“逢 60 进一”59 秒之后再加 1 秒秒位归 0分位进 1。十进制是“逢 10 进一”9 加 1 之后个位归 0十位进 1。二进制则是“逢 2 进一”1 加 1 之后本位归 0向高位进 1。那 B 进制就是“逢 B 进一”当某一位的数达到 B就向高一位进位。理解到这一步竖式加法就顺理成章了。你小学算十进制加法时个位相加超过 9就往十位进 1超过 19就进 2。这在本质上就是把“当前位的数字和”除以 10商是进位余数是留在本位的数字。B 进制一模一样只是把除数从 10 换成 B。还以钟表举例计算3小时58分 1小时17分你肯定不会先把所有时间换算成分钟算完再除 60 一次、取余一次。正常人会直接分钟位相加得到 75 分钟超过 60所以分钟位留 15小时位进 1最后得到5小时15分。这就是竖式思维。B 进制星球这道题本质就是让你把这种“逢 B 进一”的竖式思维用代码表达出来。1.3 数据范围就是解题风向标很多初学者卡在这道题不是因为不会写加法而是没读懂数据范围。题目给的两个数不是普通整数而是可能长达几千位的字符串。这在十进制下都不可能用一个long long存下更不用说在 36 进制下任意一位都可能代表 0 到 35 的值。就算用 64 位整数最大也就支持约 1.8×10^19而一个 2000 位的 36 进制数数值量级是 36^1999这是多少个零你可能都无法想象。所以这道题根本不可能用语言内置的整数类型直接完成。数据范围这样设计就是逼你往高精度方向想。所谓高精度就是不会算一种数字就用“数组的每一位存一个数位”的方式手动模拟人工计算的过程。把一串数字拆开逐位运算自己处理进位这就是高精度。它不是什么高深算法只是一种“因为内存放不下所以我用数组硬算”的思路。想通了这一点题目就开始往“模拟 B 进制竖式加法”的方向收敛了。2. 常见的错误路线先把B进制转十进制再转回去2.1 “先转十进制再算”到底哪里错了我第一次做这类题的时候脑子里闪过的第一个方案是能不能先把两个字符串按给出的进制转成十进制整数加完再转回 B 进制相信很多初学的人都有同样的冲动。这个思路在数值很小的时候确实能跑通但它有致命问题。第一数值根本放不下。B 进制字符串长度可能达到上千位就算你一位位地乘 B 累加结果也是一个天文数字int放不下long long放不下甚至连double都会因为精度丢失而出现错误。第二就算你用的是支持任意大整数的类库比如 Java 的BigInteger也会陷入二次转换的泥潭先要把两个大数分别转成十进制这意味着要做大数乘法和加法加完之后又要用“除 B 取余法”转回 B 进制这意味着要准备一套大数除法。难度直接翻倍而且完全没必要。数学上偷懒的代价是工程上更复杂的实现。2.2 高精度加法的本质用数组拼出一个人工大整数要避开上面那条弯路我们需要回到“竖式加法”这个朴素的模型。你手算两个多位数相加的时候第一步是数位对齐从个位开始逐位加第二步是超过当前进制的部分要进位。计算机用数组做高精度加法做的就是这件事。具体来说一个 B 进制大数可以看成一个数组数组每个位置存一位低位放在前面或者后面都可以但为了逐位相加方便我们通常把低位放在数组开头也就是反转字符串后操作。这样索引i就对应从低位往高位的第i位。相加时把相同索引位置的数字相加再加上进位然后用商和余数分别得到进位和当前位的结果。这里有一个值得说的点为什么这种方法不会溢出因为在 B 进制下每一位最大也就是B-1。两个数位相加再加上进位最大值是(B-1) (B-1) 1 2B - 1。除以 B 之后商最大是 1余数最大是B-1。所以进位永远只可能是 0 或 1更精确地说两个一位数相加进位最大就是 1根本不存在溢出风险。这也是高精度数组能够稳定工作的数学基础。2.3 为什么要坚持“直接在原进制下做竖式”有人可能会问进制本质上只是数的表示方式先转成十进制再算数学上不也一样吗是数学上一样但工程上差很多。直接在 B 进制下做竖式整个过程中你只需要处理两件事字符到数字的映射以及逢 B 进一。这比“转十进制再转回来”少了一整套高精度乘除法。更重要的是这种“在原进制下直接模拟”的思路可以扩展到很多场景。比如算 B 进制大数减法只需要把“进位”换成“借位”算 B 进制大数乘法只需要双循环逐位相乘再累加。所有逻辑都在同一个框架里清晰、可控、容易调试。相反那句“先转成十进制再说”往往只在题目数据很弱的时候能蒙混过关一旦数据范围变大就是白忙活。3. 实现细节逐段拆解从字符映射到进位处理3.1 字符和数字之间的双向转换B 进制里超过 9 的位用大写字母表示这给编码提出了一个要求你得会写字符转数字和数字转字符两个函数。字符转数字的规则是这样的int charToVal(char c) { if (c 0 c 9) { return c - 0; } return c - A 10; }这段代码里0到9直接减掉0得到 0 到 9A到Z减掉A再加 10得到 10 到 35。为什么是10因为A代表的数值是 10不是 0所以要做偏移。数字转字符则是反过来的char valToChar(int v) { if (v 10) { return 0 v; } return A v - 10; }注意细节如果v等于 10A v - 10正好是A如果v等于 35结果就是Z。这两个函数是整道题的基石后面所有运算都依赖它们。写的时候建议先单独测试一下charToVal(Z) 35和valToChar(10) A能省下后面不少调试时间。3.2 反转字符串让低位对齐这一步是很多新手最容易忽略的。两个字符串的长度可能不一样比如一个是 5 位一个是 8 位。如果直接从左往右逐位相加两个数的个位根本对不上结果必然错误。正确做法是把两个字符串都反转让低位跑到前面来int lenA a.size(); int lenB b.size(); for (int i 0; i lenA / 2; i) { swap(a[i], a[lenA - 1 - i]); } for (int i 0; i lenB / 2; i) { swap(b[i], b[lenB - 1 - i]); }在 C 里可以直接用reverse(a.begin(), a.end())非常省事。反转之后索引 0 就是个位索引 1 就是进制位依此类推。两个数位数不同也没关系短的数在越界位置直接视为 0 即可。这个“低位对齐”的思想和十进制竖式完全一致。你在纸上算 123 4567 的时候也不会从最左边开始加而是从个位 3 和 7 开始。反转字符串就是在代码里实现这个对齐动作。3.3 循环体里的三行核心计算本位、进位、拼接核心计算其实就是三句话拿一个变量记录进位然后逐位处理int carry 0; int len max(a.size(), b.size()); string res; for (int i 0; i len; i) { int da i (int)a.size() ? charToVal(a[i]) : 0; int db i (int)b.size() ? charToVal(b[i]) : 0; int sum da db carry; res.push_back(valToChar(sum % B)); carry sum / B; }这三行的意思da和db是当前位的数字sum是当前位数字加上进位的总和。sum % B是留在当前位的数字sum / B是向高位进的数。然后把当前位数字转回字符append 到结果串里。整个循环结束后所有没有被处理的位都已经算完只剩一个可能非 0 的最终进位。这里需要再强调一下“为什么进位用除法、本位用取余”。你可以把 B 进制的一位理解成一个容量为 B 的容器超过容器容量的部分就要往高一位倒。sum / B算的是“满了几次 B”sum % B算的是“倒完之后还剩多少”。这和十进制里17 / 10 1、17 % 10 7是一个道理。3.4 最高位进位与最后反转输出循环结束之后还有一个很容易忘的边界如果carry不是 0说明最高位还有进位需要额外补一位。比如十进制999 1循环只处理三位是不行的最后必须再输出一个1才能得到1000。B 进制也一样36 进制下Z 1得到的是10也就是35 1 36写成 36 进制是10。这个结果的产生靠的就是循环后的这个判断if (carry ! 0) { res.push_back(valToChar(carry)); }最后因为我们在循环里一直是从低位向高位往res末尾追加字符此时res里的顺序是反的。要得到正确的从左到右的输出顺序还需要再反转一次reverse(res.begin(), res.end()); cout res endl;反转这一步如果忘了像101 1这种输入会输出1011这种明显不对的结果。我见过太多人栽在这个地方包括当年的我。4. 完整可提交代码与样例验证4.1 C参考实现带注释把上面这些碎片拼起来就是一份可以提交的完整代码。我在这里给出一份 C 版本的实现注释写得比较详细方便你逐行对照理解。#include bits/stdc.h using namespace std; int charToVal(char c) { if (c 0 c 9) { return c - 0; } return c - A 10; } char valToChar(int v) { if (v 10) { return 0 v; } return A v - 10; } string addB(string a, string b, int B) { // 反转两个字符串让低位对齐 reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); string res; int carry 0; int len max(a.size(), b.size()); for (int i 0; i len; i) { int da i (int)a.size() ? charToVal(a[i]) : 0; int db i (int)b.size() ? charToVal(b[i]) : 0; int sum da db carry; res.push_back(valToChar(sum % B)); carry sum / B; } // 处理最高位进位 if (carry ! 0) { res.push_back(valToChar(carry)); } // 反转回来得到正确顺序 reverse(res.begin(), res.end()); return res; } int main() { int B; string a, b; cin B a b; cout addB(a, b, B) endl; return 0; }这份代码里cin会自动跳过换行和空格所以输入是36换行Z换行1还是一行里写36 Z 1都不影响读入。需要注意的只是题目要求读入顺序如果题意是先给两个数再给 B那就按题目调整一下顺序即可。4.2 手动验证三个典型样例有了代码之后一定不要直接交先在本地跑几个典型样例确认逻辑。我最常用的验证组合有三种普通十进制、二进制、最大进制 36 进制。第一个样例10 123 456输出应该是579。这个例子验证的是最基础的逐位加法能跑通说明大框架没有问题。第二个样例2 101 1101是二进制下的 5加 1 等于 6二进制写作110。输出应该是110。这个例子能验证“逢二进一”的进位逻辑毕竟 1 1 要进位这件事和十进制很不相同。第三个样例36 Z 1输出应该是10。Z是 35加 1 等于 3636 进制下写作10。这个例子是最高位进位和字母符号转换的综合测试。这三个样例跑过后面再出错大概率就是边界问题而不是主逻辑问题。我自己在本地测试时还会再加一个0 0 0的用例确保空串或者全零的情况没有被错误处理掉。4.3 边界用例检查0、1位、最大符号Z除了上面三个样例还有几个边界用例值得单独拿出来讲。第一个是结果为 0。输入两个 0反转后长度都是 1循环里算出来的sum是 0res会存一个0所以最终输出0这是正确的。但如果你把“res 为空”当成输出空串就会直接漏掉这个 0。好在我们从循环一开始就会向res里 push 字符所以每个位上都会生成结果不会出现空串问题。要格外注意的其实是另一种写法如果你先把每一位数字存进vectorint最后统一转字符那么全 0 的结果也要保证至少有一个0被输出。第二个是位数不对称。比如 36 进制下输入Z和ZZZZZ短的数在高位全是 0长的数有五位。反转后索引 0 都是个位其余位置短数取 0循环跑完正好得到六位结果。这个用例能测试补零逻辑是否写对。第三个是低位进位连续传导。比如十进制999 1个位 9 1 10本位 0进位 1十位 9 1 10本位 0进位 1百位同理。最后循环结束进位还是 1必须补一位变成1000。这种连续进位的情况最容易在“最高位进位”那里翻车测试时一定不要只测12 34这种温和用例。5. 我实际提交时踩过的坑与排查链路5.1 长度不一致导致的数组越界我第一次提交的时候犯过一个很蠢的错误我直接按a.size()作为循环次数然后把b[i]也取出来算。当a比b长的时候没问题但当b比a长循环还没跑完就已经越界了。本地测试时我用的是两个长度相同的数没暴露问题一提交直接 Runtime Error。排查的时候我还以为是reverse写错了回头一行行看才发现是循环边界用了短的字符串长度。这个问题也给我留下一个教训高精度题里“长度不一致”几乎是必考边界一定要用较长的长度作为循环次数短的数在越界处用 0 代替。现在我在代码里一律写da i (int)a.size() ? ... : 0从根上杜绝越界。5.2 结果全是0却被当成空串输出另一个坑和res的初始化方式有关。我最早写高精度时习惯用一个vectorint存数字位最后统一转字符。在处理0 0时循环只产生了一个0本来完全正常。但我后来为了省事把res字符串直接留空循环里只对非零数字才执行push_back结果就是输出一个空串。这个问题的排查过程其实很典型。我先是把样例从123 456一路试到0 0发现输出是空的时候第一反应是charToVal或者valToChar写错了。但打印出来之后发现数字全对最后才想到是“我以为每一位都会 push但实际上我只在特定条件下 push”。解决方案很简单不管当前位结果是什么都要把结果的字符写进去哪怕是0除非你有其他逻辑保证最终输出非空。5.3 大写字母处理与“漏判a-z”的教训题目说数字用0-9超过 9 的部分用大写字母A-Z表示这本身没有问题。但有些测试数据可能混入小写字母或者你从别的平台复制代码时前辈的代码里用了tolower这些都会造成字符转数字的错乱。我遇到过一道类似进制题数据里全是小写字母当时的charToVal只判断了A到Z结果所有小写字母都被当成非法字符处理程序直接崩。后来我把字符转换函数改成兼容大小写的版本int charToVal(char c) { if (c 0 c 9) { return c - 0; } if (c a c z) { return c - a 10; } return c - A 10; }虽然很多题并不需要这么写但在本地调试时我会故意构造小写输入来验证程序的鲁棒性。这种习惯救了我很多次。5.4 调试方法把进制改成10、2去对照验证如果你写的代码在某些测试用例上输出不对我最推荐的排错方式不是盯着代码干想而是把进制参数改成 10 或 2用最容易心算的数据去验证。举个例子把B固定为 10输入999和1你知道正确答案是1000那就直接用这个用例跑。如果输出不是1000问题大概率出现在进位的处理上如果输出是1000再把B改成 2输入101和1检验不同进制下的进位逻辑。进制一改很多隐藏的问题就会立刻暴露。我还有一个“土办法”在循环里打印i、da、db、sum、carry这些中间值。比如输入36 Z 1你会看到个位的中间值是35 1 36carry变成 1余数 0 被拼接。这个打印输出会直观地告诉你进位到底有没有生效。调试高精度题千万不要觉得打印中间值很笨它能帮你在五分钟内定位到任何细节错误。6. 从B进制星球延伸出去进制题背后的通用思维6.1 同一套竖式框架改造成减法与乘法B进制星球这道题学会之后很多类似题都会变得很简单。比如 B 进制大数减法核心代码还是那个循环只不过把“进位”换成“借位”当前位数字不够减时向高位借 1相当于本位加 B高位减 1。再比如 B 进制大数乘法用一个外层循环遍历第一个数的每一位内层循环遍历第二个数的每一位把乘积累加到对应的结果位上最后统一处理进位。你会发现所有这些操作的底子都是同一个竖式模拟框架。我在之后写某个“B 进制大数乘法”的题目时几乎没有重新思考直接沿用了这套代码结构反转字符串、字符转数字、逐位运算、处理进位、反转输出。只是把核心的sum da db carry改成了sum da * db carry再多加一层循环。理解了 B 进制加法等于拿到了整个高精度运算家族的钥匙。6.2 进制互转的深层逻辑从这道题还能延伸出另一个高频考点进制互转。B 进制字符串转十进制本质上是“从左到右逐位累乘 B 再加下一位”十进制转 B 进制本质上是“除 B 取余倒序输出”。这两个操作看起来完全不一样但如果你理解了“进制只是数的表示方式”这件事就会发现它们本质上就是同一个数学过程的两个方向。这里给新手一个忠告十进制转 B 进制时如果数字很大你写“除 B 取余”其实需要高精度除法因为你用来除以 B 的数字本身可能溢出。而 B 进制星球教会我们的做法是干脆不转来转去直接在目标进制下运算避开整套转换流程。所以下次遇到进制题先问自己我能不能在这个进制下直接计算如果答案是能就尽量别干“先转十进制再转回去”的傻事。6.3 做这类题最值钱的一个习惯回顾整个做题过程我最值钱的一个习惯是在写代码前先在纸上手推一个带有进位的样例把每一步的中间结果写出来再照着写代码。比如 36 进制下Z 1到底该得到什么为什么是10再比如 2 进制下101 1为什么是110。这种先在纸上推演的过程能帮你把“进位”“补零”“反转”这些脑内容易糊掉的细节提前变成清晰可见的步骤。我在实际做这类题时至少一半的时间花在纸上推演剩下的一半才交给键盘。听起来很慢但反而是最快的方式。另外提交前一定要跑至少三组用例普通加法、有连续进位的加法、位数不对称的加法。只要这三组能过剩下的问题基本都是小概率的边界情况。你可以把这道题里积累的这套流程直接套用到任何高精度练习上。