二进制GCD算法基本原理是:
先用移位的方式对两个数除2,直到两个数不同时为偶数。然后将剩下的偶数(如果有的话)做同样的操作,这样做的原因是如果u和v中u为偶数,v为奇数,则有gcd(u,v)=gcd(u/2,v)。到这时,两个数都是奇数,将两个数相减(因为gcd(u,v) = gcd(u-v,v)),得到的是偶数t,对t也移位直到t为奇数。每次将最大的数用t替换。
二进制GCD算法优点是只需用减法和二进制移位运算,不像Euclid’s算法需要用除法,这在某些嵌入式系统中可能排上用场。
本例实现参考了<<计算机编程的艺术>>第二卷中介绍的算法。
public class GCD_Binary {
/**
* solve gcd using binary method
* @param u
* @param v
* @return gcd(u,v)
*/
public static int gcdBinary(int u,int v){
u=(u<)?-u:u;
v=(v<)?-v:v; if(u==)
return v;
if(v==)
return u; int k=;
while((u & 0x01)== && (v & 0x01) == ){
u>>=; //divide by 2
v>>=;
k++;
}
//at this time, there is at least one number is odd between m and n
int t=-v; //set it negative for later comparison of (t>0)
if((v & 0x01)==){
//v is odd
t = u;
}
//process t as a possible even number
while(t != ){
while((t & 0x01)==){
//do until t is not even
t>>=;
}
if(t>) //u > v (the max is replaced by |t|)
u=t;
else //u<v (the max is replaced by |t|)
v=-t;
//now u and v are all odd, then u-v is even
t = u-v;
}
return u*(<<k);
} public static void print(int m,int n,int gcd){
m = (m<)?-m:m;
n = (n<)?-n:n;
System.out.format("gcd of %d and %d is: %d%n",m,n,gcd);
} public static void main(String[] args) {
int m = -;
int n= ;
print(m,n,gcdBinary(m,n)); //co-prime
m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); m = ;
n= ;
print(m,n,gcdBinary(m,n)); }
}