Steins GCD Algorithm

Algorithm to find GCD using Stein’s algorithm gcd(a,b)

1. If both and b are 0, gcd is zero gcd(0, 0) = 0.
2. gcd(a, 0) = a and gcd(0, b) = b because everything divides 0.
3. If a and b are both even, gcd(a, b) = 2*gcd(a/2, b/2) because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.
4. If a is even and b is odd, gcd(a, b) = gcd(a/2, b). Similarly, if a is odd and b is even, then
   gcd(a, b) = gcd(a, b/2). It is because 2 is not a common divisor.
5. If both a and b are odd, then gcd(a, b) = gcd(|a-b|/2, b). Note that difference of two odd numbers is even
6. Repeat steps 3–5 until a = b, or until a = 0. In either case, the GCD is power(2, k) * b, where power(2, k) is 2 raise to the power of k and k is the number of common factors of 2 found in step 2.

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int steinsGCD(int a,int b)
{
	int k=0;
	while((a|b)&1==0)
	{
		a >>= 1;
		b >>= 1;
		k+=1;
	}
	
	while((a&1)==0)
		a >>= 1;
		
	while(b)
	{
		while((b&1)==0)
			b >>= 1;
		if(a>b)
		{
			a=a+b;
			b=a-b;
			a=a-b;
		}
		b=b-a;
	}
	return a<<k;
}
int main()
{
	int a,b;
	while(cin>>a)
	{
		cin>>b;
		cout<<steinsGCD(a,b)<<"\n";
	}
	return 0;
}