求两数的最大公约数

来源：编程之美2.7

问题：求两数的最大公约数

//求两个数的最大公约数
public class GCD2_7 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int x=4272;
		int y=25472;
		System.out.println(gcd1(x,y));
		System.out.println(gcd2(x,y));
		System.out.println(gcd3(x,y));
	}

	//方法一，辗转相除法 f(x,y)=f(y,x%y)，缺点，对于大整数取余运算开销会很大
	public static int gcd1(int x,int y){
		return (y>0)?gcd1(y,x%y):x;
	}
	//方法二，f(x,y)=f(x-y,y)（x>y) 缺点，迭代次数会比较多。如x远大于y时
	public static int gcd2(int x,int y){
		if(x<y)return gcd2(y,x);
		if(y==0)return x;
		return gcd2(x-y,y);
	}
	//方法三，结合方法二，主要是减少迭代次数
	public static int gcd3(int x,int y){
		if(x<y)return gcd3(y,x);
		if(y==0)return x;
		else{
			if(isEven(x)){
				if(isEven(y))return(gcd3(x>>1,y>>1)<<1);
				else return(gcd3(x>>1,y));
			}else{
				if(isEven(y))return gcd3(x,y>>1);
				else return gcd3(y,x-y);
			}
		}
	}

	//判断一个数是否为偶数
	private static boolean isEven(int x) {
		
		return (x&1)==0;
	}
	
}