이진-최대공약수 알고리즘.

최대공약수를 구하는 알고리즘에는 대표적으로 유클리드 호제법이 있다.
유클리드 호제법을 간단히 설명하면 다음과 같다.

1. 두 수 a,b를 입력받는다.
2. a가 b보다 크면 a를 b로 나눈 나머지를 구한다. b가 a보다 크면 그 반대로 한다.
3. 나누어서 얻는 나머지를 새로운 a, 원래 a,b중 작은값을 b로 하고 2번으로 돌아간다.
4. 만약 a나 b가 0이 되었다면 이 때의 나머지 b나 a의 값이 최대공약수이다.

이 알고리즘은 a와 b의 최대공약수나 a-b와의 최대공약수나 같다는 사실을 이용해서 쉽게 증명할수 있다.

int gcd(int a,int b)
{
	if(b==0)return a;
	return gcd(a,a%b);
}

위 코드는 유클리드 호제법을 간단하게 c코드로 짜본것이다. (단 a>=b일때만 작동한다.) 그러나 이 방법은 재귀호출로 자원을 좀 낭비할 가능성이 있다. 그래서 반복문으로 바꿔써보면 다음과 같다.

int gcd(int a,int b)
{
	int t;
	while(b)
	{
		t=a;
		a=b;
		b=t%b
	}
	return a;
}

좀 코드가 길어졌지만, 처음것보다 더 효율적이다.

이제 본론으로 들어가서 이진-최대공약수 알고리즘은 위 알고리즘에서 등장하는 나누기 연산을 없애고, 쉬프트 연산과 빼기 연산만을 활용하여 최대공약수를 구하는 방법이다.
한국어위키백과-이진 최대공약수 알고리즘

1. 두 수 a,b를 입력받는다.
2. 최대공약수의 인수 2의 개수 s를 0으로 초기화한ㄷ다.
3. a,b의 값에 따라 다음과 같이 분기한다.

ㄱ. a,b 모두 짝수인 경우
a,b를 2로 나누고 그 결과를 다시 a,b에 넣는다. s를 1증가시킨다.

(설명: a,b 모두 인수 2를 하나 이상 가지고 있으므로 최대공약수 역시 인수 2를 하나 이상 가진다. 따라서 a,b의 최대공약수는 (a,b를 각각 2로 나눈것의 최대공약수)*2 이다.)

ㄴ. a,b 중 하나만 짝수인 경우
a,b중 짝수인것을 2로 나누고 그 결과를 다시 a,b에 넣는다.
(설명: a,b중 하나만 인수 2를 가지므로, 2는 최대공약수의 인수에 포함되지 않는다. 따라서 a,b의 최대공약수는 (a,b중 짝수인 것을 2로 나눈것의 최대공약수)와 같다.)

ㄷ. a,b 모두 홀수인 경우
(a와 b의 차)/2를 a라 하고, b는 (a,b)중 작은것으로 한다.
(설명: a,b의 최대공약수는 a-b와의 최대공약수와 같다.(단, a>=b일때) 그러므로 a,b의 최대공약수는 (a와 b의 차와 a,b중 하나의 최대공약수)와 같은데, a,b가 모두 홀수이므로 a와 b의 차는 짝수가 된다. ㄴ(하나만 짝수인 경우)을 적용하면 a,b의 최대공약수는 ((a와 b의 차)/2와 a,b중 작은것의 최대공약수)와 같다.)

4. a,b중 하나가 0이 될때까지 3번으로 돌아가 반복한다. a,b중 어느 하나가 0이 되었을때 나머지 하나의 값에 2^s를 곱한것이 최대공약수다.

int binary_gcd(int a,int b) 
{
	if(a==0)return b;
	if(b==0)return a;
	if((a&1)==0 && (b&1)==0) //if both a and b are even
		return binary_gcd(a>>1,b>>1)<<1;
	else if((a&1)==1 && (b&1)==1) //if both a and b are odd
		return binary_gcd(abs(a-b)>>1,min(a,b)) ;
	else if((a&1)==0) //if only a is even
		return binary_gcd(a>>1,b);
	else //if only b is even
		return binary_gcd(a,b>>1);
}

일단 재귀를 써서 짜보았다. 유클리드 호제법보다 느려보이기까지 한다. 반복문으로 고쳐본다.

int binary_gcd(int a,int b)
{
	int s;
	if(a==0)return b;
	if(b==0)return a;
	for(s= 0;((a|b)&1)==0;++s)
		//a,b모두 짝수면 2로 계속해서 나눠줌
	{
		a >>= 1;
		b >>= 1;
	}
	while((a&1)==0)
		//a만 짝수면 a를 계속해서 2로 나눔
		a>>=1;
	do 
	{
		while((b&1)==0)
			//b만 짝수면 b를 계속해서 2로 나눔
			b>>=1;
		if(a<b) //a<b일때 a=(a,b)중 작은값, b=(a,b)의 차
		{
			b-=a;
		}
		else //a>b일때 a=(a,b)중 작은값, b=(a,b)의 차
		{
			int diff=a-b;
			a=b;
			b=diff;
		}
		b>>=1;
	}
	while(b!=0);
	return a << s; //나온 결과에 2^s(2의 s제곱)를 곱해줌
}

반복문으로 고치며 약간의 테크닉으로 더 최적화했다. 이 방법은 유클리드 호제법과 비교하여서 나눗셈 연산은 한번도 쓰지 않고, 빠른 뺄셈과 쉬프트 연산만 사용했으므로, 성능향상이 꽤 있다.