GCD

In mathematics, the greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4. The greatest common divisor is also known as the greatest common factor (gcf),highest common factor (hcf), greatest common measure (gcm), or highest common divisor.

Euclidean algorithm

int gcd(int a, int b){
    while(b!=0){
        int tmp=b;
        b=a%b;
        a=tmp;
    }
    return a;
}

Binary GCD algorithm(Stein's algorithm)

1. gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. 
Similarly, gcd(u, 0) = u. gcd(0, 0) is not typically defined, but it is convenient to set gcd(0, 0) = 0.

2. If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.

3. If u is even and v is odd, then gcd(u, v) = gcd(u/2, v), because 2 is not a common divisor. 
Similarly, if u is odd and v is even, then gcd(u, v) = gcd(u, v/2).

4. If u and v are both odd, and u ≥ v, then gcd(u, v) = gcd((u − v)/2, v). If both are odd and u < v, then gcd(u, v) = gcd((v − u)/2, u). 
These are combinations of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of step 3 above. 
The division by 2 results in an integer because the difference of two odd numbers is even.

int gcd(int num1, int num2) {
        if (num1 == 0) {
            return num2;
        }
        if (num2 == 0) {
            return num1;
        }
        if ((num1&1) == 0 && (num2&1) == 0) {
            return 2*gcd(num1 >>1, num2 >> 1);
        } else if ((num1&1) == 0) {
            return gcd(num1 >> 1, num2);
        } else if ((num2&1) == 0) {
            return gcd(num1 ,num2 >> 1);
        } else {
            return gcd(Math.abs(num1 - num2), Math.min(num1,num2));
        }
    }