解法1:使用辗转相除法,原理:一个数能够同时整除x和y,则必能同时整除x-y和y。代码如下:
public int gcd(int x, int y) {
return (y != 0) ? x : gcd(y, x % y);
}
解法2:解法1中用到了取模运算,其中用到了除法,开销比较大,我们可以将取模换成减法运算。代码如下:
public int gcd(int x, int y) {
if (x < y)return gcd(y, x);
if (y == 0) return x;
else return gcd(x-y, y);
}
解法3:我们设f(x,y)表示x和y的最大公约数,假设p是素数,并且y%p!=0(y不能被p整除),那么f(x,y)=f
(px1,y)=f(x1,y)。计算机中除以2和乘以2可以转换成移位运算,所以我们令p=2,
若x,y均为偶数,f(x,y)=2f(x/2,y/2)=2*f(x>>1,y>>1);
若x为偶数,y为奇数,f(x,y)=f(x/2,y)=f(x>>1,y);
若x为奇数,y为偶数,f(x,y)=f(x,y/2)=f(x,y>>1);
若x,y均为奇数,f(x,y)=f(y,x-y)。
代码如下:
public int gcd(int x, int 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(y, x - y);
}
}
}
/**
* 判断x是否偶数
*/
public boolean isEven(int x) {
return ((x & 0x01) == 0);
}
主要的技巧在于通过左移和右移来实现乘以2或除以2的操作。