以下使用按位运算查找两个数的 GCD 的函数如何工作？

Question

我在网上搜索问题的解决方案时发现了这个功能。我测试了它，它似乎工作正常。我只需要知道这是如何工作的。这比寻找 GCD 的常用方法更有效吗？这是函数：

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

Answer 1

此代码仅实现 Euclid's algorithm 以查找最大公分母 (GCD)。我会说它是非常标准的，因为它自公元前 300 年以来就广为人知和使用。当您说 "the common way of finding GCD" 时，我不确定您将它与其他什么算法进行比较，但欧几里得算法是众所周知的高效算法。

这段代码唯一奇怪的是它被严重混淆了。有人认为他们将所有代码压缩到一行是聪明的做法，但除非您根据删除的代码行数获得奖金，否则这样做毫无意义。它不会改变编译器生成的目标代码；它只会让您的来源更难阅读和理解。

实际上，这里进行的混淆将严重错误引入代码，假设这是 C 或 C++。 a 和 b 上的操作是 undefined because of a lack of sequence points.

此代码使用的另一种 "clever" 技术是按位 XOR 来交换值而不使用临时变量。这是一个非常的老把戏，老到"optimization"多年不值一提了。事实上，它很可能比仅仅使用一个临时变量要慢。有lots of descriptions of how it works online个。看起来很复杂，其实很简单，所以很多人都在写博客。

Ungolfed，您的代码如下：

int gcd(int a,int b) {
    while(b)              // while b is non-zero
    {
       int temp = b;      // cache current value of b
       b = (a % b);       // set b equal to (a modulo b)
       a = temp;          // set a equal to the original value of b
    }
    return a;             // once b is zero, return a
}

注意代码也可以递归写：

int gcd(int a,int b) {
    if (b)
        return gcd(b, a % b);
    else
        return a;
}

Answer 2

您的代码只是实现欧几里德算法的另一种方式。按位异或只是为了交换，为了比较，执行速度会更快，交换速度更快，库函数通常是最佳可用实现，所以下面给出的代码会更快，

int gcd(int a, int b){

     while (a){
                 b %= a;
                 std::swap(a,b);
     }
  return b;
}

如果两个值相同，则使用按位异或交换也不是一个好主意

以下使用按位运算查找两个数的 GCD 的函数如何工作？

How the following function of finding GCD of two numbers using bitwise operation works?

greatest-common-divisor