Giải thích cách kiểm tra đồng thời hoạt động

Question

Mỗi lần tôi sử dụng phương pháp Euclid để kiểm tra xem hai số có đồng nguyên tố hay không. Nhưng có một giải pháp mà đã sử dụng mã này để kiểm tra đồng primeness, và thời gian thực hiện của thành viên này là nhanh hơn nhiều so với phương pháp 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; 
} 

Tôi không thể hiểu được thế nào là này đang làm việc. (Tôi hiểu các hoạt động bitwise.) Ví dụ: những dòng này có nghĩa là gì ...

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

Tại sao chỉ cần trả về false? Ngoài ra còn có những dòng khác mà tôi không thể hiểu những gì đang xảy ra. Nếu bất kỳ một trong các bạn có thể bạn chỉ cần cho tôi một số hướng dẫn nó sẽ được giúp đỡ nhiều.

Answer 1

Mã bạn đã đăng là sửa đổi của binary GCD algorithm. Đây là bình luận có chú thích của tôi:

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