求最大公约数（二进制优化GCD)

我们平常求两个数的最大公约数，用到就是欧几里得算法，也就是辗转相除法，也就是递归方法，如果数据大的话，复杂度也不小。

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

但是我们是可以对这个进行优化的；
我们用不断除以2来对这个进行一点小优化（可以提高gcd效率）。
我们判断这么几种情况：
1.
x=y，那么gcd(x,y）=x;
2.
x,y都是偶数，那么gcd(x,y)=2*gcd(x/2,y/2);
3.
x为偶数，y为奇数，那么gcd(x,y)=gcd(x/2,y);
4.
x为奇数，y为偶数，那么gcd(x,y)=gcd(x,y/2);
5.
x,y都是奇数，(假设x>y)，那么gcd(x,y)=gcd(x-y,y);
代码：

int gcd(int x,int y)
{
    int i,j;
    if(x==0)return y;
    if(y==0)return x;
    for( i=0;(x&1)==0;i++)
        x>>=1;
    for( j=0;(y&1)==0;j++)
        y>>=1;
        if(i<j)
        {
            j=i;
        }
        while(1)
        {
            if(x<y)
            {
                int tem;
                tem=x;
                x=y;
                y=tem;
            }
            if(x==y)
            {
                return y<<i;
            }
            else
            {
                x=x-y;
                while((x&1)==0)
                {
                    x>>=1;
                }
            }
        }
}