Объясните, как работает взаимная проверка

Question

Каждый раз я использую метод Евклида для проверки, если два числа взаимно просты. Но есть одно решение, которое использовало этот код для проверки совместимости, и время, затрачиваемое на это, было намного быстрее, чем метод Евклида: ( источник)

private static boolean isCoprime(long u, long v) {
    if (((u | v) & 1) == 0)
        return false;

    while ((u & 1) == 0)
        u >>= 1;
    if (u == 1)
        return true;

    do {
        while ((v & 1) == 0)
            v >>= 1;
        if (v == 1)
            return true;

        if (u > v) {
            long t = v;
            v = u;
            u = t;
        }
        v -= u;
    } while (v != 0);

    return false;
}

Я не могу понять, как это работает. (Я понимаю побитовые операции.) Например, что означают эти строки...

if (((u | v) & 1) == 0)
    return false;

Почему просто вернуть ложь? Также есть другие строки, которые я не могу понять, что происходит. Если кто-нибудь из вас мог бы просто дать мне немного прохождения, это очень поможет.

Answer 1

Размещенный вами код является модификацией двоичного алгоритма GCD. Вот мой аннотированный комментарий:

private static boolean isCoprime(long u, long v) {
    // If both numbers are even, then they are not coprime.
    if (((u | v) & 1) == 0) return false;

    // Now at least one number is odd. Eliminate all the factors of 2 from u.
    while ((u & 1) == 0) u >>= 1;

    // One is coprime with everything else by definition.
    if (u == 1) return true;

    do {
        // Eliminate all the factors of 2 from v, because we know that u and v do not have any 2's in common.
        while ((v & 1) == 0) v >>= 1;

        // One is coprime with everything else by definition.
        if (v == 1) return true;

        // Swap if necessary to ensure that v >= u.
        if (u > v) {
            long t = v;
            v = u;
            u = t;
        }

        // We know that GCD(u, v) = GCD(u, v - u).
        v -= u;
    } while (v != 0);

    // When we reach here, we have v = 0 and GCD(u, v) = current value of u, which is greater than 1.
    return false;
}