基于二进制计算最大公约数的算法。

程序来自维基百科。

#include 
    
     // Recursive version in Cunsigned int gcd(unsigned int u, unsigned int v){    // simple cases (termination)    if (u == v)        return u;    if (u == 0)        return v;    if (v == 0)        return u;    // look for factors of 2    if (~u & 1) // u is even    {        if (v & 1) // v is odd            return gcd(u >> 1, v);        else // both u and v are even            return gcd(u >> 1, v >> 1) << 1;    }    if (~v & 1) // u is odd, v is even        return gcd(u, v >> 1);    // reduce larger argument    if (u > v)        return gcd((u - v) >> 1, v);    return gcd((v - u) >> 1, u);}// Iterative version in Cunsigned int gcd2(unsigned int u, unsigned int v){  int shift;  /* GCD(0,v) == v; GCD(u,0) == u, GCD(0,0) == 0 */  if (u == 0) return v;  if (v == 0) return u;  /* Let shift := lg K, where K is the greatest power of 2        dividing both u and v. */  for (shift = 0; ((u | v) & 1) == 0; ++shift) {         u >>= 1;         v >>= 1;  }  while ((u & 1) == 0)    u >>= 1;  /* From here on, u is always odd. */  do {       /* remove all factors of 2 in v -- they are not common */       /*   note: v is not zero, so while will terminate */       while ((v & 1) == 0)  /* Loop X */           v >>= 1;       /* Now u and v are both odd. Swap if necessary so u <= v,          then set v = v - u (which is even). For bignums, the          swapping is just pointer movement, and the subtraction          can be done in-place. */       if (u > v) {         unsigned int t = v; v = u; u = t;}  // Swap u and v.       v = v - u;                       // Here v >= u.     } while (v != 0);  /* restore common factors of 2 */  return u << shift;}int main(void){    unsigned m = 140, n = 42;    printf("gcd1: %u %u result=%u\n", m, n, gcd(m, n));    printf("gcd2: %u %u result=%u\n", m, n, gcd2(m, n));    return 0;}