我求最大公约数的方法

自从接触算法时起，第一个让我惊叹的算法就是求最大公约数的辗转相除法，记得当时书上代码为：

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    while(a%b != 0) {
        int temp = a%b;
           a = b;
           b = temp;
    }
    cout<<b<<endl;
    return 0;
}

当时想了半天才弄懂其表达的意思，然后觉得相当经典，就死记下来了。后来发现，一不小心会忘记，就努力的回忆，今天突然想到一套属于我自己的方法，相比起来，理解容易得多。

思想就一点：不停地去做一个动作，用较大的数去减较小的数，剔除较大的数，直到出现零，就停止。反复相减使用取余(%)来实现。代码如下：

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    while(a && b) {
        a > b ? a %= b : b %= a;
    }
    cout<<"==>"<<a+b<<endl;
    return 0;
}

总体感觉代码和思想都要简单好多，哈哈！

某开源项目中有一实现更为简单，不过考虑到函数递归调用可能影响效率，个人并不特别推崇：

uint32_t gcd(uint32_t x, uint32_t y) {
    return (x % y) == 0 ? y :  gcd(y,x % y);
}

上面的代码有一个问题，就是受限于int的大小，如果要对两个非常大的数进行求最大公约数，就有点麻烦了，方法之一是使用python语言来解决，因为python里直接支持大整数，例如：

def gcd(a,b):
    return gcd(b, a%b) if a%b else b

实验一把：

In [19]: gcd(148834788141915391936174, 14882018829572998524574)
Out[19]: 34L

但如果要使用C/C++语言呢，那就使用stein求最大公约数算法，基本使用位运算完成，运行效率很高，我的实现版本贴在下面了，能支持非常大的整型。 stein算法的核心思想就是一分支判断，然后反复循环：

• 如果a和b都是偶数，说明2是一个公因子，那么a和b都除2，即右移一位
• 如果a和b是一奇一偶，说明2一定不是公因子，那么将偶数的除2，即右移一位
• 如果a和b都为奇数，再借用辗转取余的思想，假设a > b，则a = (a - b) / 2，b = min(a, b)

我的stein算法实现代码：

#include <iostream>
#include <string>
#include <bitset>
using namespace std;

bool operator > (const bitset<256> &a, const bitset<256> &b)
{
    for (int i=255; i>=0; --i) {
        if (a[i] > b[i]) {
            return true;
        } else if (a[i] < b[i]) {
            return false;
        }
    }
    return false;
}

bitset<256> operator + (const bitset<256> &a, const bitset<256> &b)
{
    int t = 0;
    bitset<256> ret(0);
    for (int i=0; i<256; ++i) {
        t += a[i] + b[i];
        ret[i] = t & 1;
        t >>= 1;
    }
    return ret;
}

bitset<256> operator - (const bitset<256> &a, const bitset<256> &b)
{
    return a + (~b + bitset<256>(1));
}

int main()
{
    //148834788141915391936174
    bitset<256> one(string("111111000010001011001100110"
         "11101101101001000101111011110100000100011010101110"));
    //14882018829572998524574
    bitset<256> two(string("1100100110110000010111111111"
         "0111010010111001111101001000010110111010011110"));
    bitset<256> div = 1;

    int shiftn = 0;
    while (true) {
        if (one.test(0) == 0 && two.test(0) == 0) {
            one >>= 1;
            two >>= 1;
            ++shiftn;
        } else if (one.test(0) == 0) {
            one >>= 1;
        } else if (two.test(0) == 0) {
            two >>= 1;
        } else {
            if (one == two) {
                div = one << shiftn;
                break;
            } else if (one > two) {
                one = (one - two) >> 1;//需要实现减法操作
            } else {
                two = (two - one) >> 1;
            }
        }
    }
    //34
    cout<<div<<endl;
    return 0;
}