求最大公约数（GCD）听起来像教科书角落里的例题，但 Algorithmica 最近做了一件很工程化的事：把这个老问题重新拿到现代 CPU 上审了一遍，结果发现，基于“二进制 GCD”的实现可以跑到约 91ns，而 C++17 的 std::gcd 在文中测试里约为 198ns。差距接近 2 倍。

这件事的新闻价值不在于“标准库不行”，而在于它把一个常被忽略的现实摆到了台面上：很多程序的瓶颈，早就不是大 O 复杂度，而是你到底触发了哪条硬件指令。欧几里得算法和二进制 GCD 都是对数时间，但一个重度依赖整数除法 idiv，另一个主要用移位、减法和比较。对现代处理器来说，这不是细节，是两种成本模型。

标准算法没错，慢在硬件脾气

原文先复盘了最熟悉的欧几里得算法：不断做 a % b，直到余数为 0。这套方法在数学上很漂亮，在 C++ 里也很自然，std::gcd 自 C++17 起就是标准库的一部分。问题在于，编译器最后还是会把 % 落到整数除法指令上，而作者用 perf 观察到，程序大约 90% 的时间都耗在 idiv 上。

这就是这篇文章真正有价值的地方：它不是在发明新算法，而是在提醒开发者，标准库的“通用正确”并不自动等于“在你的机器上最划算”。类似情况并不少见。字符串处理里，memcpy 往往比手写循环快；哈希表里，布局和分支预测常常比理论复杂度更影响吞吐；密码学和压缩库更是长期围着 CPU 指令特性打磨。GCD 只是一个足够小、足够典型的样本。

二进制 GCD赢的不是数学，是避开除法

二进制 GCD 并不新。原文提到，它可以追溯到中国古代，1967 年又被 Josef Stein 为计算机重新整理。它的核心思路很朴素：既然偶数可以不断右移，两个奇数的差一定是偶数，那就尽量把问题改写成移位和减法，而不是做通用除法。

文章里最关键的一步，不是把欧几里得算法“翻译”成二进制版本，而是继续做了适合现代 CPU 的微优化：用 __builtin_ctz 一次性数出末尾有多少个 0，等于批量完成多次“除以 2”；再通过减少分支、缩短指令依赖链，把性能从 116ns 继续压到 91ns。这里有一个读者单看原始结论不一定会意识到的限制：这个收益高度依赖具体硬件、编译器和输入分布。文中假设的是现代 CPU、随机大整数，换成别的架构、不同数据集，结果可能缩小，甚至逆转。

同样是 O(log n)，在处理器眼里，idiv 和 shift 根本不是一个价位。

这也是为什么很多高性能库宁可多写几行难懂代码，也要绕开除法、分支和内存访问热点。数学课上的“步骤数”衡量，到了工程现场，得让位给流水线、延迟和吞吐。

对开发者的意义，和对普通用户的边界

如果你是普通用户，这个优化几乎不会直接改变你的电脑体验。没有哪个人会因为 GCD 从 198ns 降到 91ns，就明显感觉系统更快。真正会受影响的是下面几类人：

对象现实影响是否值得改
竞赛/高性能开发者热路径里会省掉大量除法开销值得，尤其是批量计算
标准库维护者要权衡可读性、可移植性和收益不一定，需看平台覆盖
普通业务开发者单点收益有限，维护成本可能更高通常不值得
密码学/数论库作者底层原语提速会累积成真实收益值得认真评估

这里有个横向对比很重要：std::gcd 的优势是可靠、通用、可读，适合绝大多数工程；二进制 GCD 的优势是更贴合硬件，适合对纳秒敏感的场景。两者不是谁“先进”谁“落后”，而是服务不同目标。标准库要照顾 ABI、平台一致性、边界条件、编译器行为，不能像单篇优化文章一样把可读性和可维护性押到后排。

更具体一点，如果你在做大整数库、分数化简、椭圆曲线密码、计算几何，或者一段数论代码一天要调用上亿次 GCD，那这不是纸上谈兵；如果你只是写个后端服务，GCD 只在请求里偶尔跑几次，先去查数据库、锁竞争和网络延迟，收益会大得多。

这类“快一倍”的文章，最容易被误读的地方

技术圈很爱“快 2 倍”这种标题，但这类结果最常见的问题，是它常常成立于精心挑选的测试环境。原文已经相当诚实：它分析的是特定汇编、特定依赖链，并把优化目标锁定在现代 CPU 的执行特性上。可一旦离开这个边界，结论就没那么硬了。

几个现实约束不能跳过：

  • __builtin_ctz(0) 是未定义行为，代码必须严密避开零值路径
  • 不同 CPU 上 tzcnt、条件移动和分支预测收益并不一致
  • 编译器版本会影响最终汇编，GCC、Clang、MSVC 结果可能不同
  • 可读性显著下降，团队代码审查成本会上升

这也是我的判断：这篇文章最适合被当成“性能思维案例”，而不是“所有人都该替换 std::gcd 的行动指南”。它告诉我们，算法优化还远没结束，只是今天的优化，越来越像硬件协商。会写对，已经不够；知道 CPU 喜欢什么，才有机会把那最后一倍性能拿到手。