Binary Greatest Common Divisor Finder

While studying for coding interviews, I came up with a very neat example that I want to share with everyone. The question is to code a program that finds the greatest common divisor given two positive integers without invoking multiplication, division, and modulus operators.

The easiest way perhaps is to use Euclidean algorithm but that is just too slow. So, the following is a bit faster algorithm called binary GCD:

	int binaryGCD(int a, int b) {
	if (a==b)
	return a;
	if (a==0)
	return b;
	if (b==0)
	return a;
	// divide a and b by 2 until they become both odd numbers
	int p2a, p2b;
	p2a = p2b = 0;
	while ((a&1) == 0) {
	p2a++;
	a >>= 1;
	}
	while ((b&1) == 0) {
	p2b++;
	b >>= 1;
	}
	int minpower = p2a < p2b ? p2a : p2b;
	if (a>b)
	return binaryGCD((a-b)>>1, b) << minpower;
	else
	return binaryGCD((b-a)>>1, a) << minpower;
	}

view raw binaryGCD.c hosted with ❤ by GitHub

int binaryGCD(int a, int b) {
  if (a==b)
    return a;
  if (a==0)
    return b;
  if (b==0)
    return a;

  // divide a and b by 2 until they become both odd numbers
  int p2a, p2b;
  p2a = p2b = 0;
  while ((a&1) == 0) {
    p2a++;
    a >>= 1;
  }
  while ((b&1) == 0) {
    p2b++;
    b >>= 1;
  }
  int minpower = p2a < p2b ? p2a : p2b;

  if (a>b)
    return binaryGCD((a-b)>>1, b) << minpower;
  else
    return binaryGCD((b-a)>>1, a) << minpower;
}

The code above is my variant of binary gcd found in here. It is a bit harder to read but perhaps a bit faster though.