解答例

[ryuhei-mori]

unsigned int binary_gcd_rec(unsigned int x, unsigned int y){
  if(x == 0 || y == 0) return x ^ y;
  if(x%2 == 0 && y%2 == 0) return 2* binary_gcd_rec(x/2, y/2);
  if(x%2 == 0) return binary_gcd_rec(x/2, y);
  if(y%2 == 0) return binary_gcd_rec(x, y/2);
  if(y >= x) return binary_gcd_rec(x, (y-x)/2);
  return binary_gcd_rec(y, (x-y)/2);
}

unsigned int binary_gcd_itr(unsigned int x, unsigned int y){
  unsigned int tx, ty, s;
  if(x==0 || y==0) return x^y;

  tx = __builtin_ctz(x);
  ty = __builtin_ctz(y);
  s = tx <= ty ? tx : ty;
  x >>= tx;
  y >>= ty;

  while(x != y){
    if(x < y){
      y -= x;
      y >>= __builtin_ctz(y);
    }
    else {
      x -= y;
      x >>= __builtin_ctz(x);
    }
  }

  return x << s;
}

[ryuhei-mori]

@alg2018/students
もしくは

unsigned int binary_gcd_itr(unsigned int x, unsigned int y){
  unsigned int s;
  if(x==0 || y == 0) return x^y;

  s  = __builtin_ctz(x|y);
  x >>= __builtin_ctz(x);

  do {
    y >>= __builtin_ctz(y);
    if(y < x){
      int z = x;
      x = y;
      y = z;
    }
    y -= x;
  } while(y != 0);

  return x << s;
}

試したところこれが一番速いです。これよりも速くできた人は教えてください。