int gcd1(int x,int y) {//欧几里得辗转相除法 return (!y)?x:gcd1(y,x % y); } int gcd2(int x,int y) {//能除的尽x,y的数,也能除的尽x-y,y if( x < y) return gcd2(y,x); if( y == 0 ) return x; else return gcd2(x - y,y); } int IsEven(int x) {//判断x是否偶数 return !(x & 0x1); } int gcd3(int x,int y) {//利用移位和减法降低除法开销,具体讲解见《编程之美》2.7 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); } } } }