辗转相除法（又叫欧几里得算法）是什么鬼？

辗转相除法， 又名欧几里得算法（Euclidean algorithm），目的是求出两个正整数的最大公约数。

这条算法基于一个定理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。 比如10和25，25除以10商2余5，那么10和25的最大公约数，等同于10和5的最大公约数。

更相减损术， 出自于中国古代的《九章算术》，也是一种求最大公约数的算法。

他的原理更加简单：两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。比如10和25，25减去10的差是15,那么10和25的最大公约数，等同于10和15的最大公约数。

package com.zheting.it.test04;

public class Test {

    public static void main(String[] args) {

    }

    //枚举法
    public static int getGreatestCommonDivisor(int numberA, int numberB) {
        int smallNumber = numberA < numberB ? numberA : numberB;
        int bigNumber = numberA >= numberB ? numberA : numberB;
        if (bigNumber % smallNumber == 0) {
            return smallNumber;
        }
        int gereatestCommonDiveisor = 1;

        for (int i = 2; i < smallNumber / 2; i++) {
            if (numberA % i == 0 && numberB % i == 0) {
                gereatestCommonDiveisor = i;
            }
        }
        return gereatestCommonDiveisor;
    }

    //欧几里得算法 两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
    public static int getGreatestCommonDivisor2(int numberA, int numberB) {
        int result = 1;
        if (numberA > numberB) {
            result = gcd2(numberA, numberB);
        } else {
            result = gcd2(numberB, numberA);
        }
        return result;
    }

    private static int gcd2(int a, int b) {
        if (a % b == 0) {
            return b;
        } else {
            return gcd2(b, a % b);
        }
    }

    //更相减损术 两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数
    public static int getGreatestCommonDivisor3(int numberA, int numberB) {
       if(numberA == numberB){
           return  numberA;
       }
        if (numberA < numberB) {
            return  getGreatestCommonDivisor3(numberB - numberA, numberA);
        } else {
            return  getGreatestCommonDivisor3(numberA - numberB, numberB);
        }
    }

    //更相减损术与移位结合
    public static int getGreatestCommonDivisor4(int numberA, int numberB) {
        if(numberA == numberB){
            return  numberA;
        }
        if (numberA < numberB) {
            return  getGreatestCommonDivisor4(numberB, numberA);
        } else {
            boolean bA = (numberA & 1) == 1;
            boolean bB = (numberB & 1) == 1;
            if(!bA && !bB){
                return getGreatestCommonDivisor4(numberA>>1, numberB>>1) <<1;
            }else if(!bA && bB){
               return getGreatestCommonDivisor4(numberA>>1, numberB) ;
            }else if(bA && !bB){
               return getGreatestCommonDivisor4(numberA, numberB>>1);
            }else {
                return getGreatestCommonDivisor4(numberA, numberA - numberB);
            }
        }
    }

}

最后总结一下上述所有解法的时间复杂度：

1.暴力枚举法：时间复杂度是O(min(a, b)))

2.辗转相除法：时间复杂度不太好计算，可以近似为O(log(min(a, b)))，但是取模运算性能较差。

3.更相减损术：避免了取模运算，但是算法性能不稳定，最坏时间复杂度为O(max(a, b)))

4.更相减损术与移位结合：不但避免了取模运算，而且算法性能稳定，时间复杂度为O(log(max(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必然是偶数，又可以继续进行移位运算。