最大公约数问题是经典的数学问题，本文分析下最大公约数问题的计算优化思路。

分析：

1、求x，y的最大公约数，用辗转相除法

设k = x / y，b = x % y，则x = ky + b，
因此( x, y ) = ( ky +b, y ) = (y, b)，
因此( x, y ) = ( y, x % y )，并且( 0, x) = x。

关键就是将两个较大的数的公约数转化为两个较小数的公约数。

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

2、进一步，由于取模运算是比较慢的，考虑到(x, y) = ( x - y, y ) 假设x > y，因此可以加速。

int gcd( int x, int y )
{// x >= y
    if ( x < y )
       return gcd(y, x);
 
    return (y==0) ? x : gcd(x-y, y);
}

3、更进一步，虽然减法加速了，但是递进的速度不够快，考虑极端的情况( 1000000000, 1 )，这样用方法2将非常郁闷。还是需要想办法，尽量结合上面两种优势：向目标递进速度与每次运算效率。

注意到：

若x = k * x1, y = k * y1，则(x, y) = (x1, y1)，
另外，对于素数p，若x = p * x1，且y % p != 0，那么(x, y) = (p*x1, y) = (x1, y)

这个素数p的最优选择就是2，因为除以2可以用移位操作简单的代替：

若x, y均为偶数： ( x, y ) = 2*( x>>1, y>>1 )
若x奇，y偶：     ( x, y ) = (x, y>>1)
若x偶，y奇：     ( x, y ) = (x>>1, y)
若x,y均为奇数：  ( x, y ) = (x, x-y)，由于x-y为偶，下一步会除以2

bool IsEven( int n )
{
    return !(n & 0x01);
}
 
int gcd( int x, int y )
{// x >= y
    if ( x < y )
       return gcd(y, x);
 
    if ( y == 0 )
    {
       return x;
    }
    else
    {
       if ( IsEven(x) )
       {
           if ( IsEven(y) )
              return (gcd(x>>1, y>>1) << 1);
           else
              return gcd(x>>1, y);
       }
       else
       {
           if ( IsEven(y) )
              return gcd(x, y>>1);
           else
              return gcd(x-y, y);
       }
    }
}