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。

普通循环：

template<class T>
T gcd_euclid(T a, T b)
{
    while (b != 0) {
        T r = a % b;
        a = b;
        b = r;
    }
    return a;
}

异或交换：

template<class T>
T gcd_xor(T a, T b)
{
    while (b != 0) {
        a %= b;
        b ^= a;
        a ^= b;
        b ^= a;
    }
    return a;
}

异或版本先计算余数，再用三次异或交换 a、b。若一轮开始时的值为 A、B，两种实现结束后都得到 (B, A % B)。两者的取余次数和算法步骤相同，差别在变量更新方式。

这里将异或拆成独立语句，是为了让它在 C++14 下也具有明确的执行顺序，便于比较合法实现的性能。

同样的过程也可以压缩成连写表达式：

// 内置非负整数类型；要求 C++17 或更高版本。
template<class T>
T gcd_xor_compact(T a, T b)
{
    if (b == 0) {
        return a;
    }
    while (b ^= a ^= b ^= a %= b) {
    }
    return a;
}

连写版本依赖 C++17 的复合赋值求值顺序保证；在 C++11/C++14 下，这条表达式存在未定义行为。另外，进入连写循环前的 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 只计时普通循环和分步异或，未运行 C++14 下缺乏顺序保证的连写版本。

还测试了 0…32767 的 int 和 0…LLONG_MAX 的 long long。完整输入范围、最小与最大耗时、源码及汇编证据见文末的实验记录。

优化级别和编译器版本的影响

以下均为每 1,000,000 对 0…INT_MAX 输入的中位耗时，单位毫秒。表中“异或交换”采用前面的分步实现，同一类写法只保留一个代表。

GCC 对照

编译器与标准模式	优化选项	普通循环	异或交换
GCC 4.9.2，C++14	`-O0`	100.25	136.26
GCC 4.9.2，C++14	`-O2`	70.07	84.36
GCC 15.2.0，C++14	`-O0`	101.33	138.32
GCC 15.2.0，C++14	`-O2`	70.28	70.71
GCC 15.2.0，C++17	`-O0`	101.17	141.29
GCC 15.2.0，C++17	`-O2`	69.62	70.50

未优化时，异或版本有明显额外开销。GCC 4.9.2 开启 -O2 后，两种实现都变快了，但异或交换仍多耗时约 20%。 开启优化并不意味着编译器一定能消除这种写法带来的额外计算。

GCC 15.2.0 开启 -O2 后，两种实现的耗时接近，对应函数的指令序列相同。

MSVC 对照

MSVC 使用 /Od 关闭优化、/O2 进行速度优化。这些选项与 GCC 的优化级别具有相近的用途，但不是完全相同的一组优化过程。参见 MSVC 官方优化选项文档。

编译器与标准模式	优化选项	普通循环	异或交换
MSVC 19.44.35222，C++14	`/Od`	98.46	137.51
MSVC 19.44.35222，C++14	`/O2`	71.00	69.57
MSVC 19.44.35222，C++17	`/Od`	98.65	134.99
MSVC 19.44.35222，C++17	`/O2`	64.80	65.21

MSVC 关闭优化时，分步异或同样有明显额外耗时；开启 /O2 后，两种实现生成相同的函数指令，耗时接近。C++14 与 C++17 的对应函数指令分别相同，表中的测量差异不构成标准切换带来加速的证据。

本表采用 2026-10-02 关闭其他主要应用后重新运行的结果，GCC 与 MSVC 的构建交替测试。CPU 频率和系统负载没有锁定，小幅耗时差异不应理解为稳定排名；本实验也不足以评价编译器的整体性能。

另外两个输入范围，以及允许内联的对照，也呈现类似现象：GCC 4.9.2 下异或版本仍有额外耗时，GCC 15.2.0 和 MSVC 开启速度优化后则接近普通写法。这些结论限定在本次实现、工具链和目标平台上。

汇编里发生了什么？

本节的汇编提取、对照和解释在 AI 协助下完成；所用汇编由本机编译器实际生成。

在 GCC 4.9.2 / C++14 / -O2 下，异或版本的循环主体如下，跳转标签已简化：

loop:
    cdq
    idiv r8d
    xor r8d, edx
    mov eax, edx
    xor eax, r8d
    xor r8d, eax
    jne loop

idiv 计算出余数后，编译器仍然执行三次异或。它们的结果相互依赖，下一轮除法又需要交换后的操作数。这些运算处于循环的依赖链中，构成了实际额外计算。

不开优化时，生成代码中还保留了更多对内存中变量的读写。开启 -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 下，将 C++14 改为 C++17，本次两种分步实现的函数指令并没有变化：对应的 -O0 版本分别相同，-O2 版本也分别相同。MSVC 19.44.35222 在 /Od、/O2 下也得到相同的标准模式对照结果。表中的耗时波动不构成 C++17 带来加速的证据。

对于前面介绍的异或连写表达式，语言标准版本会影响正确性。

C++17 规定赋值和复合赋值的右操作数先于左操作数求值；C++11/C++14 没有这一保证，这条表达式对同一变量存在未排序的修改与读取，属于未定义行为。运算符从右向左结合，只说明表达式怎样分组，不能据此推出求值顺序。参见 C++17 赋值规则与 C++14 程序执行规则。

本次也观察了连写版本的生成代码。旧 GCC / -O2 将它与分步异或版本编译成相同的函数指令，新 GCC / -O2 则将它们都化简为普通循环。主表采用在 C++14 下执行顺序明确的分步版本，性能判断不需要依赖未定义行为。

此外，连写条件会直接执行 a %= b，因此初始 b == 0 必须在进入它之前处理。对零取余的行为未定义，见 C++ 取余规则。前面的分步实现通过 while (b != 0) 避免这个问题，连写实现则在循环前单独判断。

对实际使用 GCD 有什么启示？

需要自己实现时，普通的取余循环容易检查边界条件，也能被编译器有效优化。如果 GCD 位于程序的性能热点，应当使用实际部署的编译器、优化选项和输入分布进行测量，并检查生成代码。

C++17 及以后，也可以直接使用 <numeric> 中的标准接口：

#include <numeric>

int main()
{
    const int g = std::gcd(48, 18);  // 6
    return g == 6 ? 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 复测；所有计时构建均通过结果校验。正确性检查仍用于发现实现错误，不能替代对算法及语言规则的分析。

先区分算法和写法#

实验怎么做？#

优化级别和编译器版本的影响#

GCC 对照#

MSVC 对照#

汇编里发生了什么？#

C++ 标准版本影响了什么？#

对实际使用 GCD 有什么启示？#

实验资料#