/** * The binary GCD algorithm, also known as Stein's algorithm, is an algorithm * that computes the greatest common divisor of two nonnegative integers. * * @author Atom * @see Binary GCD algorithm * @see Stein’s Algorithm for finding GCD */ public class BinaryGCD { /** * Stein's algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm, * replaces division with arithmetic shifts, comparisons, and subtraction * * @param a * @param b * @return */ public static int gcd(int a, int b) { // gcd(0,b) == b; gcd(a,0) == a, gcd(0,0) == 0 if (a == 0) { return b; } if (b == 0) { return a; } // find the greatest power of 2 dividing both 'a' and 'b' int shift; for (shift = 0; ((a | b) & 1) == 0; shift++) { a >>>= 1; b >>>= 1; } // divide 'a' by 2 until 'a' becomes odd while ((a & 1) == 0) { a >>>= 1; } // from here on, 'a' is always odd while (b != 0) { // remove all factor of 2 in 'b' while ((b & 1) == 0) { b >>>= 1; } // Now 'a' and 'b' are both odd. If 'a' > 'b' swap, substract 'a' from 'b' if (a > b) { int tmp = a; a = b; b = tmp; } b -= a; } // restore common factors of 2 return a << shift; } public static void main(String[] args) { System.out.println(gcd(10, 5)); System.out.println(gcd(5, 10)); System.out.println(gcd(10, 8)); System.out.println(gcd(8, 2)); System.out.println(gcd(7000, 2000)); System.out.println(gcd(2000, 7000)); System.out.println(gcd(10, 11)); System.out.println(gcd(11, 7)); System.out.println(gcd(239, 293)); } }