这个最大公约数算法如何工作？

Question

我刚刚在网上找到了这段代码,它可以计算2个数字的最大公约数.它是如何工作的？

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

Answer 1

首先,我不认为这实际上是正确的C,因为相同的变量在单个语句中被多次更新而没有插入序列点.一个更简单的例子是:

a += ++a;

无论是a在外作业的左侧拿起原始或修改a是不确定的(有声明中没有顺序点).

话虽如此,循环体的意图似乎是:

a %= b;
b ^= a;
a ^= b;
b ^= a;

这相当于:

a %= b;
t = b;
b = a;
a = t;

换句话说,它设置a为a % b,然后交换a和b.

与该交换^运算符的工作原理是先设置b到a ^ b,然后异或a与该值来获得原始b,那么异或新的b(这是a ^ b)与原b获得原a.这只是换一个令人费解的方式a和b不使用临时变量.

算法本身只是从另一个中减去尽可能多的一个,然后切换两个数字,一直持续到其中一个为零,此时另一个将包含GCD(这是基于欧几里德算法).

您可以通过展开循环来完全避免交换:

for (;;) {
    if (b == 0) return a;
    a %= b;
    if (a == 0) return b;
    b %= a;
}