最大公约数

一、简述

求两个数间的最大公约数，要求传递两个正整形参数，返回值就是他们的最大公约数，需要尽可能的保证性能。

二、方法1：暴力枚举法

试图寻找合适的整数i,看看这个数能否被两个整形参数numberA和numberB同时整除。如果较小数字不为较大数字的的公约数，这个整数i可以从2开始循环累加，一直累加到numberA和numberB中较小参数的一半为止。循环结束后，上一次寻找到的能被两个数同时整除的最大值i,就是两个数的最大公约数。

//暴力破解法
    public int gcd1(int numberA,int numberB){
        int result=0;
        int smallNumber = numberA < numberB ? numberA : numberB;
        int bigNumber = numberA >= numberB ? numberA : numberB;
        if (bigNumber%smallNumber == 0)
            return smallNumber;
        else {
            for (int i = 2; i <= smallNumber / 2; i++) {
                if ((smallNumber%i)==0 && (bigNumber%i)==0){
                    result = i;
                }
            }
            return result;
        }
    }

但这种方法明显不行，效率过于低下，如10000与10001，这样就要计算10000/2-1=4999次。于是我们可以提及另一种方法，详见方法二。

三、方法2：辗转相除法

辗转相除法，又名欧几里得算法，目的就是求出两个正整数的最大公约数，这条算法的基于一个定理，两个正整数a和b(假设a>b)，他们的最大公约数等于a除以b的余数c和较小数b之间的最大公约数。比如10和25,25除以10商2余5，那么10和25的最大公约数等同于10和5的最大公约数。基础这条定理，求最大公约数我们就可以运用递归的方法把问题简化了。
首先，我们先计算出a除以b的余数c，把问题转化成求出b和c的最大公约数；然后计算出b除以c的余数d，把问题转化成求出c和d的最大公约数；再然后计算出c除以d的余数e，把问题转化成求出d和e的最大公约数。
以此类推，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到1为止。

//辗转相除法
public int gcd2(int numberA,int numberB){
    int result = 0;
    int smallNumber = numberA < numberB ? numberA : numberB;
    int bigNumber = numberA >= numberB ? numberA : numberB;
    if(bigNumber%smallNumber==0)
        return smallNumber;
    else {
        return gcd2( smallNumber,bigNumber%smallNumber);
    }
}

但是这样做，假如两个数很大，a%b这样的取模运算性能会比较低，因而又有了另一种方法。

四、方法3：更相减损数

更相减损术，出自于中国古代的《九章算术》，也是一种求最大公约数的算法。
他的原理更加简单：两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。比如10和25，25减去10的差是15,那么10和25的最大公约数，等同于10和15的最大公约数。
由此，我们同样可以通过递归来简化问题。首先，我们先计算出a和b的差值c（假设a>b），把问题转化成求出b和c的最大公约数；然后计算出c和b的差值d（假设c>b），把问题转化成求出b和d的最大公约数；再然后计算出b和d的差值e（假设b>d），把问题转化成求出d和e的最大公约数……
以此类推，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以相等为止，最大公约数就是最终相等的两个数。

public int gcd3(int numberA,int numberB){
       int result = 0;
       int smallNumber = numberA < numberB ? numberA : numberB;
       int bigNumber = numberA >= numberB ? numberA : numberB;
       if(bigNumber%smallNumber==0)
           return smallNumber;
       else {
           return gcd3( bigNumber-smallNumber,smallNumber );
       }
   }

虽然更相见孙淑的避免了大整数取模的性能问题，已经接近最优。但是更相减损数依靠两个数求差来进行递归，运算的次数肯定远大于辗转相除法的取模方式。如10000和1，就要递归9999次。
所以又涉及到了方法4，移位运算法。

五、方法4：移位运算法

众所周知，移位运算的性能非常快。对于给定的正整数a和b，不难得到如下的结论。其中gcb(a,b)的意思是a,b的最大公约数函数：
当a和b均为偶数，gcb(a,b) = 2gcb(a/2,b/2) = 2gcb(a>>1,b>>1)
当a为偶数，b为奇数，gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b)
当a为奇数，b为偶数，gcb(a,b) = gcb(a,b/2) = gcb(a,b>>1)
当a和b均为奇数，利用更相减损术运算一次，gcb(a,b) =gcb(b, a-b)，此时a-b必然是偶数，又可以继续进行移位运算。
比如计算10和25的最大公约数的步骤如下：

0.    整数10通过移位，可以转换成求5和25的最大公约数
0.    利用更相减损法，计算出25-5=20，转换成求5和20的最大公约数
0.    整数20通过移位，可以转换成求5和10的最大公约数
0.    整数10通过移位，可以转换成求5和5的最大公约数
0.    利用更相减损法，因为两数相等，所以最大公约数是5

在两数比较小的时候，暂时看不出计算次数的优势，当两数越大，计算次数的节省就越明显。

//移位运算法
    public int gcd4(int numberA,int numberB){
        int result = 0;
        int smallNumber = numberA < numberB ? numberA : numberB;
        int bigNumber = numberA >= numberB ? numberA : numberB;
        if(bigNumber%smallNumber==0)
            return smallNumber;
        else {
            if ((smallNumber&1)==0 && (bigNumber&1)==0)
                return gcd4( smallNumber>>1,bigNumber>>1 )<<1;
            else if ((smallNumber&1)==0 && (bigNumber&1)==1)
                return gcd4( smallNumber>>1,bigNumber );
            else if ((smallNumber&1)==1 && (bigNumber&1)==0)
                return gcd4( smallNumber,bigNumber>>1 );
            else
                //都为奇数时候更相减损
                return gcd4( smallNumber,bigNumber-smallNumber );
        }
    }