Наибольшим общим делителем (НОД) для двух целых чисел называется наибольший из их общих делителей. Например: для чисел 8 и 12 наибольший общий делитель равен 4. Ранее мы уже рассматривали нахождение НОД с помощью Алгоритма Евклида:

long gcd(long a,long b){
	return b == 0 ? a : gcd(b,a % b);		
}

Сейчас рассмотрим Бинарный алгоритм Евклида, который быстрее обычного алгоритма Евклида. Бинарный алгоритм основан на следующих свойствах НОД:

НОД(2m, 2n) = 2 НОД(m, n),
НОД(2m, 2n+1) = НОД(m, 2n+1),
НОД(-m, n) = НОД(m, n)

Теперь реализуем этот алгоритм на Java:

static int gcd(int m, int n){
    if(m == 0) return n;
    if(n == 0) return m;
    if(n == m) return n;
    if(m == 1) return 1;
    if(n == 1) return 1;
    boolean em = (m & 1) == 0;
    boolean en = (n & 1) == 0;
    if(em && en) return gcd(m >> 1, n >> 1) << 1;
    if(em) return gcd(m >> 1, n);
    if(en) return gcd(m, n >> 1);
    if(n > m) return gcd((n - m) >> 1, m);
    return gcd((m - n) >> 1, n);
}

Для ускорения деления на два используется сдвиг битов на позицию вправо(>> 1), для умножения на два используется сдвиг на позицию влево (<< 1). Проверка четности числа осуществляется проверкой последнего бита числа (m & 1), если выражение равно 0, то число четно, иначе нечетно.