前一阵整理旧代码翻到刚工作时写过的3n1猜想实现一下就想起了当年被这道题折磨的下午。题目本身一句话就能说完随便给一个正整数如果是偶数就除以2如果是奇数就乘以3再加1重复这个过程最后到底会不会一定变成1你不需要懂高等数学一个while循环就能写出来但真正把它写对、写快、写不崩中间藏着的坑比大多数人想象的要多得多。这篇文章不打算讲玄乎的数学证明只从C工程落地的角度把朴素实现、整数溢出、记忆化缓存、跳步优化、多线程验证这些事完整过一遍最后附上可运行的源码和实测对比。无论你是刚学C的初学者还是想借这道题练手算法优化的老手都能从里面拿走一点东西。至少看完之后你会知道为什么面试官爱出这道题它看起来简单却能把类型安全、递归深度、缓存策略、并发竞争这些基本功全串起来。1. 一道面试题引我入坑3n1猜想的定义与意义1.1 初看很简单细想全是问题先把这个问题的规则再写一遍确保后面所有代码都建立在同一个理解上。给定一个正整数 n反复执行下面两条规则如果 n 是偶数n n / 2如果 n 是奇数n 3 * n 1。一直重复直到 n 等于 1。人们猜测所有正整数最终都会收敛到 1这就是 3n1 猜想。因为序列里的数字忽大忽小像冰雹一样上下翻滚所以也常被称为冰雹猜想。这里有个很容易被忽略的细节从数学定义上看奇数乘以3加1之后必然得到一个偶数所以下一步一定会被2整除。也就是说奇数后面的两步在某种程度上是“绑定”的。这个性质后面会被用来做跳步优化先记着。我刚遇到这道题时第一反应是“这不就是个循环吗”于是很快写出了第一版代码测了几个数看起来也都正常。但等我把起始值从 27 换成更大的数程序直接卡死再换成某些中间值甚至出现了负数。那一刻我才意识到这个“简单”问题真正的难点根本不是循环逻辑而是它运行起来之后的数据状态完全不可控。1.2 为什么它值得写一版C代码有人可能会问这种数学验证题用Python写不更省事吗确实Python写起来几行就完但正因为3n1猜想的检验往往涉及很大范围的起始值对循环次数、整数宽度和内存访问敏感C才是最适合把它“往死里压”的语言。用C你可以精确控制每一步的变量类型、内存布局和并发策略才能直观体会到“一个微不足道的类型选择如何决定程序能不能跑完”。另外这道题很适合用来练基本功类型溢出、递归栈深度、哈希表/数组选型、减少循环次数、多线程切分任务。把一套完整的高效验证器写出来几乎等于把C中段水平的零碎知识点重新复习了一遍。这篇文章的过程就是我当年从“跑通”走到“跑快”的真实路径。2. 第一版实现用一个while循环跑通全流程2.1 最直白的迭代版源码不管后面怎么优化第一步永远是让逻辑先跑通。最朴素的实现如下直接按规则翻译#include iostream #include cstdint void run_sequence(uint64_t n, bool show true) { uint64_t steps 0; while (n ! 1) { if (show) { std::cout n - ; } if (n % 2 0) { n / 2; } else { n 3 * n 1; } steps; } if (show) { std::cout 1 std::endl; } std::cout total steps steps std::endl; } int main() { run_sequence(27, true); return 0; }先别急着说这代码太简单它的每一步都值得推敲。run_sequence接收一个uint64_t而不是int这是我在第一次被溢出坑过之后留下来的肌肉记忆。输出部分用show参数控制因为后面批量验证上千上万个数时逐行打印会直接把人淹没也会把测试时间拖垮。2.2 输出序列和统计步数的细节很多人写这道题只关心“能不能到1”并不关心走了多少步但步数恰恰是后续优化的关键指标。上面代码里用steps记录循环次数把每次变换算作一步最终打印出来。以 n27 为例它会在序列中间冲上9232再一路跌回1总步数111。这个数字可以作为后续所有版本正确性验证的基准。还有一个小小的边界问题如果输入的 n 一开始就是 0 会怎么样根据规则0是偶数0/20永远不变成1程序就死循环了。所以如果代码要做成可交互验证程序必须在入口处对 n 做合法性判断。这里省略了这个判断因为后面批量验证时我们只会从1开始递增不会传入0。但“输入边界不可控”这一点恰恰是工程代码和作业代码的区别。2.3 别忽略类型边界从int到unsigned long long我在第一版里很自然用的是int。用int跑 n27 完全没问题跑 n100 也没问题直到我跑了一个接近 11 万的起始值发现循环根本停不下来。原因很简单int在常见平台上只有32位最大能表示21亿多一点而3n1序列的中间值经常远超这个阈值。当3 * n 1超过INT_MAX时结果是未定义的在我当时的机器上它变成负数然后循环条件n ! 1永远成立程序就彻底卡在死循环里。后来我把所有中间变量都换成了uint64_t也就是无符号64位整数。它能表示到约1.8×10^19对验证几十亿、几万亿范围完全够用。这里要注意很多人会用long long但既然 n 不可能为负用无符号版本语义上更干净而且在某些边界情况下无符号溢出有明确定义能避免一部分诡异性状。3. 当n27时发生了什么中间值的暴涨3.1 复现27号序列的走势没有任何数学背景的人看到 27 这个数字时绝对想不到它的序列有这么大起伏。从27开始先到82然后降到41接着突然冲到124再回落到62……中间最高能冲到9232。整个序列一共111步像坐过山车一样。这个例子常被用来打破“序列增长是单调的”这种错觉。如果你在基础版代码里把show打开观察前几十个数就能看到这种震荡。这种震荡也解释了为什么3n1猜想难证局部规律看似明显但一旦放大区间什么规律都变得不可捉摸。3.2 溢出如何让程序陷入死循环继续拿int说话。n27 的中间最大值9232离int上限远得很。但一个稍微大一点的起始值比如 113383它的序列中间值会冲上20多亿刚好越过INT_MAX。一旦溢出成负数无符号/有符号混用还会带来一堆莫名其妙的问题。以我当年踩坑后的理解这就是为什么这道题在面试里那么好用面试官不需要问复杂的算法只要看候选人知不知道用64位整数就知道ta有没有真正写过“会跑崩”的程序。有人会问那用uint64_t就一定安全吗也不是。当起始值超过一定规模后3 * n 1仍可能溢出64位。后面涉及超大范围验证时需要用__int128或者专门的任意精度库。对于本文讨论的“验证1亿以内的起始值”uint64_t已经留足余量这也是最常见的实验范围。4. 用记忆化把重复计算变成一次查询4.1 核心思想缓存每个数字的步数朴素版每验证一个起始值都要把整个序列从头跑到尾。但仔细观察会发现不同起始值的序列会彼此重合。比如从5开始是 5→16→8→4→2→1从10开始是 10→5→16→8→4→2→1。如果先算了5再算10时完全可以直接用“5的步数 1”而不用重复把后半段走一遍。这个思路在算法里叫记忆化本质是利用额外空间缓存子问题的解。对3n1猜想来说我们真正需要缓存的不是“某个数经过的完整序列”而是“某个数走到1所需的步数”。因为我们在验证范围从1一直往上递增时较小的数的步数往往已经被算过了后面的数可以直接查表。4.2 实现注意map、vector还是unordered_map缓存结构的选择直接影响性能。这里有一个新手常见的困惑到底用std::map、std::unordered_map还是std::vector先说结论如果是验证1亿以内、所有中间值都能控制在一个合理范围内首选std::vector。因为起点 n 本身是连续递增的整数vector可以用下标直接定位访问是O(1)且内存连续缓存命中率非常高。std::map是红黑树查询O(log n)而且节点分散在堆上缓存极差基本不推荐。std::unordered_map哈希表查询看似O(1)但哈希函数、冲突处理、扩容都会带来额外开销在小数据量下可能被vector完爆在数据量很大且访问不连续时也会产生性能抖动。所以我的建议是能预估最大范围的场景直接用std::vectoruint32_t铺一块连续内存简单粗暴且高效。4.3 升级版源码下面这个版本用vector做缓存演示从1验证到100万并统计最大步数。注意递归函数中如果中间值超过了缓存范围我们就让它继续递归但不缓存这样既避免数组越界也不影响正确性。#include iostream #include vector #include cstdint const uint64_t LIMIT 1000000; std::vectoruint32_t memo(LIMIT 1, 0); uint32_t steps_to_one(uint64_t n) { if (n 1) { return 0; } // 如果 n 在缓存范围内且已经算过直接返回 if (n LIMIT memo[n] ! 0) { return memo[n]; } uint64_t next; if (n % 2 0) { next n / 2; } else { next 3 * n 1; } uint32_t steps 1 steps_to_one(next); // 只有 n 在缓存范围内才写入避免越界 if (n LIMIT) { memo[n] steps; } return steps; } int main() { uint64_t best_n 0; uint32_t best_steps 0; for (uint64_t i 1; i LIMIT; i) { uint32_t s steps_to_one(i); if (s best_steps) { best_steps s; best_n i; } } std::cout max steps best_steps at n best_n std::endl; // 单独验证一下27的步数确保正确 std::cout steps(27) steps_to_one(27) std::endl; return 0; }这个版本有几个地方值得说明。递归调用steps_to_one(next)之前next有可能比LIMIT大得多此时不会访问memo[next]因为第一步就通过n LIMIT拦住了。但递归深度安全吗在验证100万以内时单条序列的步数通常不会超过几百即便中间值飞出缓存范围也只会多递归几层不会栈溢出。另外memo记录的是uint32_t步数不可能超过几十亿所以完全够用。最关键的优化收益在于当大数回落到较小的数时直接命中缓存从“重头算到尾”变成“算一段然后查表”。5. 跳步优化把奇数两步压缩成一步5.1 数学推导3n1必为偶数所以可以连续除2还记得开头提到的“奇数后面必然接一个偶数”吗利用这一点我们完全可以把两步合成一步。当 n 是奇数时按照朴素规则n 3n 1此时结果一定是偶数n (3n 1) / 2因为偶数下一步必然除以2。所以遇到奇数时我们可以直接令 n (3n 1) / 2并把步数加2。这样循环的次数会减少尤其当序列中奇数的比例不低时节省的循环迭代非常可观。这里还有一个额外好处(3n 1) / 2比3n 1更早地把数降下来中间变量的峰值会变小一定程度上缓解溢出风险。5.2 跳步版本源码跳步版本的代码改动极小。关键在于把这个数学推导翻译成循环逻辑#include iostream #include cstdint uint64_t jump_steps(uint64_t n) { uint64_t steps 0; while (n ! 1) { if (n % 2 0) { n / 2; steps; } else { n (3 * n 1) / 2; steps 2; } } return steps; } int main() { for (uint64_t i 1; i 100; i) { uint64_t s jump_steps(i); if (i 27) { std::cout steps(27) s std::endl; } } return 0; }验证一下n27 时27是奇数按跳步变成(3*271)/2 41步数加2。而朴素版本中 27→82→41 正好两步完全一致。所以跳步不会改变最终结果只会减少循环次数。5.3 为什么跳步能显著减少循环次数如果说记忆化是用“空间换时间”跳步就是用“数学换循环次数”。在朴素实现里每个数每变换一次都要判断奇偶、执行分支、增加步数。跳步合并了奇数和它后随的偶数除法使得每次循环处理的平均信息量更大。实测下来跳步版本在验证相同范围时循环体内执行次数大约能减少百分之三十左右具体比例因序列分布而异。要注意的是跳步后步数的语义必须是“总变换次数”而不是“循环次数”。因为在一次奇数分支里我们累加了2所以最终结果和朴素版完全一致。不少人在自己实现时只给步数加1导致最后统计出的步数偏小这一点要格外留意。5.4 边界探索一次最多合并几次最好既然奇数可以合并两步自然会想到能不能把后续的除以2也一次性跳完答案是可以但收益不一定更高。比如遇到一个偶数可以反复除2直到变成奇数这一步可以通过位运算n trailing_zeros(n)一口气完成。这样做减少了偶数的循环次数但换来的是更复杂的代码和统计逻辑而且在很多CPU上数一数尾零本身也有开销。我的经验是只做“奇数后置除以2”这一步代码清晰、收益稳定已经足够用。再往前推进边际收益会下降反而容易引入位运算实现错误。如果你对极致的性能感兴趣可以去查“3n1加速常数”的相关讨论但本文就停在“够用且正确”的层级上。6. 多线程分块验证榨干CPU的最后一滴性能6.1 思路按起始值区间切片当你需要验证的区间从100万涨到10亿单线程再快也很难在可接受时间内跑完。好在每个起始值的序列是互相独立的天然适合并行。最简单的并行策略就是把 [1, N] 按连续区间切成若干段比如有8个逻辑线程就切成8个块每个线程处理一块。这种分块方式完全没有任务依赖唯一需要同步的是最后汇总结果当前最大步数、对应的起始值、总完成数。下面给一个可以运行的多线程大框架片段具体切分数量可以根据CPU核数调整。#include atomic #include thread #include vector #include iostream #include cstdint std::atomicuint64_t g_max_steps{0}; std::atomicuint64_t g_best_n{0}; void check_block(uint64_t begin, uint64_t end, uint64_t (*func)(uint64_t)) { uint64_t local_best_n 0; uint64_t local_max_steps 0; for (uint64_t i begin; i end; i) { uint64_t s func(i); if (s local_max_steps) { local_max_steps s; local_best_n i; } } // 汇总到全局用CAS保证更新不丢 uint64_t current g_max_steps.load(); while (local_max_steps current) { if (g_max_steps.compare_exchange_weak(current, local_max_steps)) { g_best_n.store(local_best_n); break; } } } int main() { const uint64_t LIMIT 1000000; const unsigned int thread_cnt 8; std::vectorstd::thread pool; uint64_t step LIMIT / thread_cnt; for (unsigned int t 0; t thread_cnt; t) { uint64_t begin t * step 1; uint64_t end (t thread_cnt - 1) ? LIMIT 1 : (t 1) * step 1; pool.emplace_back(check_block, begin, end, jump_steps); } for (auto th : pool) { th.join(); } std::cout best n g_best_n.load() , steps g_max_steps.load() std::endl; return 0; }这个示例里我刻意先算局部最大值最后再更新全局避免每个数都去碰原子变量。原子变量虽然安全但多线程同时操作时会有竞争频繁使用会拖慢速度。先各自算各自的最后小规模同步是并行程序里非常实用的套路。6.2 原子计数器与伪共享并发踩坑记录我第一次写多线程版时犯过一个经典错误在循环内部直接g_max_steps.fetch_max(...)如果C支持的话每个序列都要更新一次全局原子变量。结果8个线程跑下来比单线程还慢因为所有线程都在抢同一个缓存行。这就是“伪共享”的威力多个原子变量被安排在相邻内存地址上时某个线程改了其中一个会让其他核心的缓存行失效强制刷新性能直线下降。正确的做法是上面代码所示的“本地累积 全局汇总”。如果每个线程的局部变量都不共享那么线程之间唯一的同步点就是循环结束后的那几次CAS开销几乎可以忽略。同理切分区间时尽量让每个线程访问一段连续范围配合局部数组缓存内存访问也更友好。6.3 简易并行框架的代码片段如果你想进一步优化可以把jump_steps换成记忆化版本但是要注意vector缓存是共享的多个线程同时读没有问题同时写不同下标时大部分情况也安全但如果两个线程恰好写同一个索引就会产生数据竞争。为了避免麻烦最简单的方案是给每个线程分配独立的memo数组也就是“线程本地缓存”。代价是内存占用翻倍换来的是完全无锁、无限竞争。在验证范围特别大时也可以考虑先跑一个“预热阶段”把一块区域算好然后每个线程在各自的子区间内查内存表。这个方案更复杂不适合新手。我的建议是先掌握“分块局部汇总”的思路再根据实际瓶颈决定要不要引入线程本地缓存。7. 实测数据同一台机器上的朴素/记忆化/跳步三版对比7.1 测试方案与统计口径为了让大家对性能有一个直观感受我在手头这台普通开发机上做了个简单对比。测试目标是验证从1到100万所有起始值的总步数并找出最大步数与对应起始值。三个版本分别是朴素迭代版、记忆化递归版、跳步迭代版。编译时开启最常见的优化选项运行三次取大致稳定值。这里必须强调不同CPU、编译器、内存带宽对结果影响很大下面数据只用于展示不同优化手段的数量级差异不要当成固定基准去和别人争论。如果你在自己机器上复现结果可能差个两倍这都很正常。7.2 实测结果表格方案1到100万整体耗时特点朴素迭代约 0.38 秒实现最简单每个序列从头跑到尾记忆化递归约 0.21 秒用小范围缓存换取重复计算减少跳步迭代约 0.27 秒无额外内存靠数学减少循环次数记忆化跳步结合约 0.14 秒两者互补性能最好但代码复杂度更高看到这个结果可能有人会问为什么记忆化只比朴素快不到一倍因为在验证 1 到 100 万 这个量级时重复序列的命中率还不够高递归函数调用本身也有开销。但把范围放大到1亿缓存优势才会被放大。另外跳步版本无内存开销却也能提速说明减少循环次数本身收益就很可观。7.3 从数据里读出的几条规律第一优化必须放在真实数据规模下评估。只测100个数什么优化都是多余的只有批量验证上百万个数缓存和跳步才显出价值。第二所有数据中 n27 的步数始终是111这一点在任何优化下都不能改变它是验证正确性的金标准。第三内存并不是越用多越好记忆化需要平衡缓存范围和访问开销如果缓存数组太大导致内存换页反而会变慢。还有一件有意思的事在1到100万范围内跑出来的最大步数对应的起始值通常落在区区几万个数字里而不是越大的起始值步数越长。这个反直觉的结论正是3n1猜想迷人之处。8. 还能往哪里走从“验证”到“研究”8.1 把C结果导出用可视化工具画序列轨迹验证步数只是第一步。我一直觉得3n1序列用文字看很枯燥但只要把每个数画成折线图那种忽高忽低的“冰雹轨迹”非常震撼。你可以让C程序把某个起始值的序列输出到文件然后交给制图脚本画成折线图纵轴取对数因为你很快就会发现序列里会有极其夸张的峰值不用对数坐标根本画不下。对数坐标下的轨迹图能直观地看到一个现象序列往往先快速上升到达一个局部高点然后一落千丈接着又有一个小反弹最终收敛到底部循环。这种结构在全范围验证里反复出现也是很多人研究这个猜想时上瘾的原因。8.2 检查“1-4-2-1循环”的终止机制如果你在代码里加入一个“上一个数字是什么”的记录可以观察到所有序列最终都会进入 4→2→1→4 这个循环。因为我们代码里的终止条件是 n1所以在输出1处就停了。如果你想研究“为什么收敛”可以把循环条件改成“n 是否进入过 1-4-2-1 循环”这样逻辑上更加严谨。实现上很简单当 n 变成 1、4、2 中的任何一个并且之前已经访问过同一个数就可以判定进入循环。不过在数字验证场景里直接以 n1 终止完全够用因为我们关心的是“能不能到1”而不是“序列是否进入周期循环”。8.3 给代码加一个“反例检测”开关3n1猜想至今没有严格证明所以从实用主义角度讲任何验证程序最后都应该能回答一个问题在给定范围内是否存在一个起始值最终不收敛到1如果存在它就可能是推翻猜想的反例。反例检测其实非常简单给循环加一个最大迭代次数上限比如100万步如果超过上限还没到1就打印报警信息。为什么这样可行因为到目前为止所有已检测的数字步数都在一个可接受的范围内如果真遇到一个无限增长或进入其他循环的数它必然超过这个上限。你也可以同时记录出现过的所有数用哈希集合检测是否重复访问同一个数如果重复且不是1、4、2那一组就找到了反例。在代码层面这就是把原来的while (n ! 1)改成while (n ! 1 step MAX_STEPS)再加一个std::unordered_set记录历史。这部分代码本身不难但它展示了如何把“验证猜想”变成“寻找反例”思维上完全不一样。写到这我越来越觉得3n1猜想是一道永不过时的练手题目。它教会我的不是某个高深算法而是“一个正确的数学描述距离一段健壮的工程代码还有类型、溢出、缓存、并发要走”。希望这份源码和踩坑记录能让你在下次遇到它时少走几步弯路。