Euclid_bin

//Указание: НОД(a,b)=2НОД(a/2,b/2),если a и b – четные, НОД(a,b)=НОД(a/2,b), если а -
//четное, b – нечетное, НОД(a,b)=НОД(a-b,b),если a и b – нечетные
int binary_gcd(int u, int v)
{
  int shl = 0;

  while ( u && v && u!=v ) {
    bool eu = !(u & 1);
    bool ev = !(v & 1);

    if ( eu && ev ) {
      ++shl;
      u >>= 1;
      v >>= 1;
    }
    else if ( eu && !ev ) u >>= 1;
    else if ( !eu && ev ) v >>= 1;
    else if ( u>=v ) u = (u-v)>>1;
    else {
      int tmp = u;
      u = (v-u)>>1;
      v = tmp;
    }
  }

  return !u? v<<shl : u<<shl;
}