⼆进制最⼤公约数算法
求最⼤公约数的需要⽤到⼤量的取模运算，这在⼤多数计算机上是⼀项复杂的⼯作，相⽐之下减法运算、测试数的奇偶性、折半运算的执⾏速度都要更快些。
⼆进制最⼤公约数算法避免了的取余数过程。
⼆进制最⼤公约数基于下述事实：
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语⾔版）：
int gcd(int a,int b){
int c=1;
while(a-b){
if(a&1){
if(b&1){
数学二进制的算法if(a>b)a=(a-b)>>1;else b=(b-a)>>1;
}
else b>>=1;
}
else{
if(b&1)a>>=1;else c<<=1,a>>=1,b>>=1;
}
}
return c*a;
}
或者
int gcd(int u,int v){
int k=1,t;
while(~u&1 && ~v&1)k<<=1,u>>=1,v>>=1;
t=(u&1)?-v:u>>1;
do{
while(~t&1)t>>=1;
if(t>0)u=t;else v=-t;
}while(t=u-v);
return u*k;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。