/* Binary GCD algorithm in C Source: http://en.wikipedia.org/wiki/Binary_GCD_algorithm This code is licensed under the Creative Commons Attribution-ShareAlike License. It is from the Wikipedia article "Counting sort" dated 2010-01-17. */ /* The binary GCD algorithm, also known as Stein's algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers. It gains a measure of efficiency over the ancient Euclidean algorithm by replacing divisions and multiplications with shifts, which are cheaper when operating on the binary representation used by modern computers. */ /* Following is an implementation of the algorithm in C, taking two (non-negative) integer arguments u and v. It first removes all common factors of 2 using identity 2, then computes the GCD of the remaining numbers using identities 3 and 4, and combines these to form the final answer. */ typedef unsigned long long uint64; uint64 gcd(uint64 u, uint64 v) { int shift; /* GCD(0,x) := x */ if (u == 0 || v == 0) return u | v; /* Let shift := lg K, where K is the greatest power of 2 dividing both u and v. */ for (shift = 0; ((u | v) & 1) == 0; ++shift) { u >>= 1; v >>= 1; } while ((u & 1) == 0) u >>= 1; /* From here on, u is always odd. */ do { while ((v & 1) == 0) /* Loop X */ v >>= 1; /* Now u and v are both odd, so diff(u, v) is even. Let u = min(u, v), v = diff(u, v)/2. */ if (u < v) { v -= u; } else { uint64 diff = u - v; u = v; v = diff; } v >>= 1; } while (v != 0); return u << shift; }
Hide code	Visustin flow chart for C/C++