首页 > 代码库 > 二进制最大公约数算法

二进制最大公约数算法

2024-07-24 18:44:06   219人阅读

求最大公约数的Euclid算法需要用到大量的取模运算，这在大多数计算机上是一项复杂的工作，相比之下减法运算、测试数的奇偶性、折半运算的执行速度都要更快些。

二进制最大公约数算法避免了Euclid算法的取余数过程。

二进制最大公约数基于下述事实：

  1. 若a、b都是偶数，则gcd(a,b)=2*gcd(a/2,b/2)
  2. 若a是奇数、b是偶数，则gcd(a,b)=gcd(a/2,b/2)
  3. 若a、b都是奇数，则gcd(a,b)=gcd((a-b)/2,b)

因此可写出二进制最大公约数算法如下（C语言版）：

[cpp] view plaincopy
  1. int gcd(int a,int b){  
  2.     int c=1;  
  3.     while(a-b){  
  4.         if(a&1){  
  5.             if(b&1){  
  6.                 if(a>b)a=(a-b)>>1;else b=(b-a)>>1;  
  7.             }  
  8.             else b>>=1;  
  9.         }  
  10.         else{  
  11.             if(b&1)a>>=1;else c<<=1,a>>=1,b>>=1;  
  12.         }  
  13.     }  
  14.     return c*a;  
  15. }  

或者

[cpp] view plaincopy
    1. int gcd(int u,int v){  
    2.     int k=1,t;  
    3.     while(~u&1 && ~v&1)k<<=1,u>>=1,v>>=1;  
    4.     t=(u&1)?-v:u>>1;  
    5.     do{  
    6.         while(~t&1)t>>=1;  
    7.         if(t>0)u=t;else v=-t;  
    8.     }while(t=u-v);  
    9.     return u*k;  
    10. } 

二进制最大公约数算法


联系
我们