GCD 写法的性能编译器版本与优化选项的影响求最大公约数可以写成普通的取余循环也可以用异或交换变量把代码压缩成很短的表达式。同样的算法换一种写法运行速度会有区别吗开启优化后这些区别还会保留吗我用 GCC 4.9.2、GCC 15.2.0 和 MSVC 19.44.35222分别测试了不同优化选项和 C 标准模式。结果显示写法带来的开销会受到编译器版本和优化选项的共同影响。旧 GCC 开启-O2后仍保留异或交换的额外计算新版 GCC 和本次测试的 MSVC 则能将它消除。先区分算法和写法循环、递归、三目运算符、短路表达式、异或交换经常被列成 GCD 的几种“求法”。但只要核心步骤还是反复将(a, b)更新为(b, a % b)它们就都属于欧几里得算法也叫辗转相除法。纯相减法、Stein 算法二进制 GCD和枚举法才是在计算步骤上有所不同的算法。Stein 算法利用奇偶性、移位和减法异或交换只改变变量更新的写法仍然需要取余。本文聚焦辗转相除法把重复写法合并为两类代表普通赋值更新和异或交换更新。不再把同一算法的不同排版或表达式逐项列成独立算法。下面的实现用于非负int或long long输入。它们都支持零输入并约定gcd(0, 0) 0。普通循环templateclassTTgcd_euclid(T a,T b){while(b!0){T ra%b;ab;br;}returna;}异或交换templateclassTTgcd_xor(T a,T b){while(b!0){a%b;b^a;a^b;b^a;}returna;}异或版本先计算余数再用三次异或交换a、b。若一轮开始时的值为A、B两种实现结束后都得到(B, A % B)。两者的取余次数和算法步骤相同差别在变量更新方式。这里将异或拆成独立语句是为了让它在 C14 下也具有明确的执行顺序便于比较合法实现的性能。同样的过程也可以压缩成连写表达式// 内置非负整数类型要求 C17 或更高版本。templateclassTTgcd_xor_compact(T a,T b){if(b0){returna;}while(b^a^b^a%b){}returna;}连写版本依赖 C17 的复合赋值求值顺序保证在 C11/C14 下这条表达式存在未定义行为。另外进入连写循环前的b 0判断不能省略否则会对零取余。分步写法和连写写法属于同一类异或交换主表采用分步版本语言规则的细节见后文。实验怎么做实验在同一台 Windows x86-64、Intel Core Ultra 9 275HX 机器上进行使用 GCC 4.9.2、GCC 15.2.0 和 MSVC 19.44.35222。其中GCC 4.9.2 来自Dev-C 5.11 自带的 TDM-GCC 工具链并非 Dev-C 自身实现的编译器。Dev-C 5.11 的带编译器安装包明确标为 TDM-GCC 4.9.2。MSVC 来自本机 Visual Studio Community 2022 17.14.24使用 x64 工具链。主表使用 1,000,000 对0…INT_MAX的非负int。预先用固定种子的std::mt19937_64生成输入两种写法复用同一批数据。随机数生成、正确性检查和输出均不计入耗时。每种实现先预热再计时 7 轮轮换测试顺序取中位数。计算结果会累加并在计时后核对避免结果未被使用而导致计算被删除。主对照禁止 GCD 函数内联以便直接比较函数指令另外进行了允许内联的对照。MSVC 只计时普通循环和分步异或未运行 C14 下缺乏顺序保证的连写版本。还测试了0…32767的int和0…LLONG_MAX的long long。完整输入范围、最小与最大耗时、源码及汇编证据见文末的实验记录。优化级别和编译器版本的影响以下均为每 1,000,000 对0…INT_MAX输入的中位耗时单位毫秒。表中“异或交换”采用前面的分步实现同一类写法只保留一个代表。GCC 对照编译器与标准模式优化选项普通循环异或交换GCC 4.9.2C14-O0100.25136.26GCC 4.9.2C14-O270.0784.36GCC 15.2.0C14-O0101.33138.32GCC 15.2.0C14-O270.2870.71GCC 15.2.0C17-O0101.17141.29GCC 15.2.0C17-O269.6270.50未优化时异或版本有明显额外开销。GCC 4.9.2 开启-O2后两种实现都变快了但异或交换仍多耗时约 20%。开启优化并不意味着编译器一定能消除这种写法带来的额外计算。GCC 15.2.0 开启-O2后两种实现的耗时接近对应函数的指令序列相同。MSVC 对照MSVC 使用/Od关闭优化、/O2进行速度优化。这些选项与 GCC 的优化级别具有相近的用途但不是完全相同的一组优化过程。参见 MSVC 官方优化选项文档。编译器与标准模式优化选项普通循环异或交换MSVC 19.44.35222C14/Od98.46137.51MSVC 19.44.35222C14/O271.0069.57MSVC 19.44.35222C17/Od98.65134.99MSVC 19.44.35222C17/O264.8065.21MSVC 关闭优化时分步异或同样有明显额外耗时开启/O2后两种实现生成相同的函数指令耗时接近。C14 与 C17 的对应函数指令分别相同表中的测量差异不构成标准切换带来加速的证据。本表采用2026-10-02 关闭其他主要应用后重新运行的结果GCC 与 MSVC 的构建交替测试。CPU 频率和系统负载没有锁定小幅耗时差异不应理解为稳定排名本实验也不足以评价编译器的整体性能。另外两个输入范围以及允许内联的对照也呈现类似现象GCC 4.9.2 下异或版本仍有额外耗时GCC 15.2.0 和 MSVC 开启速度优化后则接近普通写法。这些结论限定在本次实现、工具链和目标平台上。汇编里发生了什么本节的汇编提取、对照和解释在 AI 协助下完成所用汇编由本机编译器实际生成。在 GCC 4.9.2 / C14 /-O2下异或版本的循环主体如下跳转标签已简化loop: cdq idiv r8d xor r8d, edx mov eax, edx xor eax, r8d xor r8d, eax jne loopidiv计算出余数后编译器仍然执行三次异或。它们的结果相互依赖下一轮除法又需要交换后的操作数。这些运算处于循环的依赖链中构成了实际额外计算。不开优化时生成代码中还保留了更多对内存中变量的读写。开启-O2能改善这些代码但旧编译器仍然保留异或交换。额外检查发现这套 GCC 4.9.2 即使使用-O3也没有消除这三个异或操作。GCC 15.2.0 则能识别交换前后的等价关系开启-O2后普通循环和异或版本生成相同的函数指令序列三次异或交换消失。此次检查中-O1就已能完成这种化简。MSVC 19.44.35222 的表现与新版 GCC 类似/Od下保留三次异或/O2下将普通循环与分步异或编译成相同的函数指令序列。int和long long的对应函数都完成了对照。所以优化级别和编译器版本都需要纳入比较。源代码中的临时变量、赋值语句或运算符数量不能直接当作运行速度的指标。C 标准版本影响了什么在同一套 GCC 15.2.0 下将 C14 改为 C17本次两种分步实现的函数指令并没有变化对应的-O0版本分别相同-O2版本也分别相同。MSVC 19.44.35222 在/Od、/O2下也得到相同的标准模式对照结果。表中的耗时波动不构成 C17 带来加速的证据。对于前面介绍的异或连写表达式语言标准版本会影响正确性。C17 规定赋值和复合赋值的右操作数先于左操作数求值C11/C14 没有这一保证这条表达式对同一变量存在未排序的修改与读取属于未定义行为。运算符从右向左结合只说明表达式怎样分组不能据此推出求值顺序。参见 C17 赋值规则与 C14 程序执行规则。本次也观察了连写版本的生成代码。旧 GCC /-O2将它与分步异或版本编译成相同的函数指令新 GCC /-O2则将它们都化简为普通循环。主表采用在 C14 下执行顺序明确的分步版本性能判断不需要依赖未定义行为。此外连写条件会直接执行a % b因此初始b 0必须在进入它之前处理。对零取余的行为未定义见 C 取余规则。前面的分步实现通过while (b ! 0)避免这个问题连写实现则在循环前单独判断。对实际使用 GCD 有什么启示需要自己实现时普通的取余循环容易检查边界条件也能被编译器有效优化。如果 GCD 位于程序的性能热点应当使用实际部署的编译器、优化选项和输入分布进行测量并检查生成代码。C17 及以后也可以直接使用numeric中的标准接口#includenumericintmain(){constintgstd::gcd(48,18);// 6returng6?0:1;}std::gcd是一个接口其内部算法由标准库实现决定。例如本次使用的 libstdc 15.2.0 采用了 Stein 算法。因此不能将所有库函数都归为普通辗转相除法也不能将本文对两种交换写法的耗时排序直接推广到std::gcd。std::gcd支持零输入并按参数的绝对值求 GCD但两个绝对值必须能由参数的公共类型表示。例如参数均为int时std::gcd(INT_MIN, 0)不满足前置条件。见 标准草案中std::gcd的要求。这次比较说明同一种 GCD 算法源代码写法的差异可能被优化器保留也可能被消除。选择实现时应同时考虑正确性、可读性和目标环境中的实际性能。实验资料完整实验记录与复现命令实验源码完整计时数据汇编证据独立正确性检查程序优化选项的含义可参考 GCC 4.9.2 官方文档。GCC 与 MSVC 的计时均于 2026-10-02 复测所有计时构建均通过结果校验。正确性检查仍用于发现实现错误不能替代对算法及语言规则的分析。