如何使用按位運算來查找兩個數字的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年以來它已被廣爲人知和使用。我不確定當你說「尋找GCD的常見方式」時，你將其與什麼其他算法進行比較，但是Euclid的算法被認爲是一種有效的算法。

這段代碼唯一不可思議的是它已經被嚴重混淆了。有人認爲，通過將所有代碼壓縮到一行上，他們很聰明，但除非您根據刪除的代碼行數獲得獎金，否則沒有必要執行此操作。它不會更改編譯器生成的目標代碼;它只會讓你的源代碼更難閱讀和理解。

實際上，這裏完成的模糊處理將嚴重錯誤引入代碼，假設這是C或C++。 a和b的操作爲undefined because of a lack of sequence points。

此代碼使用的另一個「巧妙」技巧是在不使用臨時值的情況下交換值的按位異或。這是一個古老的絕招，很古老，以至於它在很多年裏都不值得「優化」。事實上，這很可能比僅使用臨時變量慢。有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; 
}