解释互质检查的工作原理

Question

每次我用Euclid方法检查两个数是否互质。但是有一个解决方案使用此代码来检查互素性，并且所花费的时间比欧几里得方法快得多：(source)

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;

为什么只是 return 错误？还有其他几行我无法理解正在发生的事情。如果你们中的任何一个能给我一些演练，这将有很大帮助。

Answer 1

您发布的代码是对 binary GCD algorithm 的修改。这是我的注释评论：

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;
}

解释互质检查的工作原理

Explain how coprime check works

java

performance

greatest-common-divisor