C++ 最大公约数（GCD）算法的三种实现方式

在算法竞赛和底层开发中，求最大公约数（Greatest Common Divisor, GCD）是高频场景。最经典的解法基于欧几里得算法，核心思想简单却高效。下面整理了几种常见的 C++ 实现写法，从标准迭代到位运算优化，各有适用场景。

这是教科书式的写法，逻辑清晰，不易出错。利用取模运算不断缩小数值范围，直到余数为零。

int gcd(int a, int b) {
    int r;
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

实际工程中推荐优先使用这种，编译器优化后性能足够好，且阅读成本最低。

如果你熟悉函数调用栈，递归版本能极大缩短代码行数。它本质上和迭代法逻辑一致，只是用栈帧代替了循环变量。

int gcd(int a, int b) {
    return (b > 0) ? gcd(b, a % b) : a;
}

注意参数较大的情况，过深的递归可能导致栈溢出。对于普通整数类型通常没问题，但处理大数时需留意。

这段代码利用了异或交换和取模的特性，试图减少指令周期。虽然看起来非常'硬核'，但在现代编译器面前，优势往往不明显，反而牺牲了可读性。

int gcd(int a, int b) {
    while (b ^= a ^= b ^= a %= b);
    return a;
}

除非是在极度受限的嵌入式环境或有特殊性能瓶颈，否则不建议在生产代码中使用这种写法。保持代码的可维护性比微秒级的提升更重要。

选择哪种实现取决于具体需求。日常开发请坚持迭代法，追求代码优雅可选递归，位运算更多是作为一种技术探索存在。理解原理比背诵代码更有价值。

更多推荐文章