BinaryEuclideanAlgorithm

/// <summary>
/// Находит НОД с помощью Бинарного алгоритма Евклида.
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static long GcdBinaryEuclideanAlgorithm(long a, long b)
{
    if (a == 0 || b == 0 || a == b)
        return a > 0 ? a : b;
    if ((a & 1) == 0 && (b & 1) == 0)
        return 2 * GcdBinaryEuclideanAlgorithm(a >> 1, b >> 1);
    if ((a & 1) == 0)
        return GcdBinaryEuclideanAlgorithm(a >> 1, b);
    if ((b & 1) == 0)
        return GcdBinaryEuclideanAlgorithm(a, b >> 1);
    if (a > b)
        return GcdBinaryEuclideanAlgorithm((a - b) >> 1, b);
    return GcdBinaryEuclideanAlgorithm(a, (b - a) >> 1);
}