学步园

二进制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算法需要用除法，这在某些嵌入式系统中可能排上用场。

本例实现参考了<<计算机编程的艺术>>第二卷中介绍的算法。

/**<br /> *<br /> * @author ljs 2011-5-18<br /> *<br /> * solve gcd using binary method<br /> * @see also "The Art of Computer Programming, Vol2"<br /> *<br /> */<br /> public class GCD_Binary {<br /> /**<br /> * solve gcd using binary method<br /> * @param u<br /> * @param v<br /> * @return gcd(u,v)<br /> */<br /> public static int gcdBinary(int u,int v){<br /> u=(u<0)?-u:u;<br /> v=(v<0)?-v:v;</p> <p> if(u==0)<br /> return v;<br /> if(v==0)<br /> return u;</p> <p> int k=0;<br /> while((u & 0x01)==0 && (v & 0x01) == 0){<br /> u>>=1; //divide by 2<br /> v>>=1;<br /> k++;<br /> }<br /> //at this time, there is at least one number is odd between m and n<br /> int t=-v; //set it negative for later comparison of (t>0)<br /> if((v & 0x01)==1){<br /> //v is odd<br /> t = u;<br /> }<br /> //process t as a possible even number<br /> while(t != 0){<br /> while((t & 0x01)==0){<br /> //do until t is not even<br /> t>>=1;<br /> }<br /> if(t>0) //u > v (the max is replaced by |t|)<br /> u=t;<br /> else //u<v (the max is replaced by |t|)<br /> v=-t;<br /> //now u and v are all odd, then u-v is even<br /> t = u-v;<br /> }<br /> return u*(1<<k);<br /> }</p> <p> public static void print(int m,int n,int gcd){<br /> m = (m<0)?-m:m;<br /> n = (n<0)?-n:n;<br /> System.out.format("gcd of %d and %d is: %d%n",m,n,gcd);<br /> }</p> <p> public static void main(String[] args) {<br /> int m = -18;<br /> int n= 12;<br /> print(m,n,gcdBinary(m,n));</p> <p> //co-prime<br /> m = 15;<br /> n= 28;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 6;<br /> n= 3;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 6;<br /> n= 3;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 6;<br /> n= 0;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 0;<br /> n= 6;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 0;<br /> n= 0;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 1;<br /> n= 1;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 3;<br /> n= 3;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 2;<br /> n= 2;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 1;<br /> n= 4;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 4;<br /> n= 1;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 10;<br /> n= 14;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 14;<br /> n= 10;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 10;<br /> n= 4;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 273;<br /> n= 24;<br /> print(m,n,gcdBinary(m,n));</p> <p> m = 120;<br /> n= 23;<br /> print(m,n,gcdBinary(m,n)); </p> <p> }<br /> }<br />