1. 最大公约数
1.1. 方法一：辗转相除法——欧几里德算法
正整数a,b(a>b)，a除以b的余数c，其最大公约数在c-b之间
/**
* 辗转相除
*
* @param a
* @param b
* @return
*/
private int gcd1(int a, int b) {
int c = a % b;
return c == 0 ? b : gcd1(b, c);
}
缺点：计算机中%运算符比较慢，性能有点影响。
1.2. 方法二：相减损术——《九章算术》
正整数a,b(a>b)，c=a-b, 其最大公约数在c-b之间
/**
* 相减损术
*
* @param a
* @param b
* @return
*/
private int gcd2(int a, int b) {
if (a == b) return b;
if (a > b) {
return gcd2(a - b, b);
} else {
return gcd2(b - a, a);
}
}
缺点：减法虽然在运算效率上要优于%运算，但是这个方法，有又更多的相减操作。即会递归很多次。效率可能还没有辗转相除法高。
1.3. 方法三：两者结合
- 当a,b(a>b)都是偶数时，满足
2*gcd(a/2,b/2) - 当a为偶数，b为奇数时，满足
gcd(a/2,b) - 当a为奇数，b为偶数时，满足
gcd(a,b/2) - 当a为奇数，b为奇数时，满足
gcd(a-b,b)
/**
* 辗转相除与
* 相减损术结合
* <p>
* 疑问：为什么一个数字 &1 为0就是偶数 为1就是奇数？
* <p>
* 为什么a与b中只有一个偶数时，可以偶数直接除以二
*
* @param a
* @param b
* @return
*/
private int gcd3(int a, int b) {
if (a == b) return b;
if (b > a) {
return gcd3(b, a);
}
if ((a & 1) == 0 && (b & 1) == 0) {
//偶数
return gcd3(a >> 1, b >> 1) << 1;
} else if ((a & 1) != 0 && (b & 1) == 0) {
//a奇数 b偶数
return gcd3(a, b >> 1);
} else if ((a & 1) == 0 && (b & 1) != 0) {
//a偶数 b奇数
return gcd3(a >> 1, b);
} else {
//a奇数 b奇数
return gcd3(b, a - b);
}
}
1.3.1. 为什么判断奇偶可以使用n&1来判断？
原因：二进制表示中，所有奇数最后一位都为1。所有偶数的最后一位都为0。
其实与n%2判断的效率并没有太大的差距，编译器会将%2的运算优化。
