Наибольшим общим делителем (НОД) для двух целых чисел называется наибольший из их общих делителей.
Например: для чисел 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, то число четно, иначе нечетно.