[알고리즘]XOR 이용한 교체 알고리즘(swap)

주로 Swap을 하게되면 다음과 같은 방법으로 하게됩니다.

< 임시변수를 두고 교체하는 알고리즘 >

void swapB(int &x, int &y)
{	
	int temp = x;
	x = y;
	y = temp;
}

그러나 임시변수를 두지 않고, XOR(비트연산)을 이용하는 방법도 있습니다.

XOR 연산은 두 값의 각 자리수를 비교해, 값이 다르면 1로, 그렇지 않으면 0으로 계산합니다.

< 5와 3의 XOR 예 >

또한 XOR 연산은 다음과 같은 성질을 갖습니다. (출처 : 위키)

• L1. 교환법칙: 
• L2. 결합법칙: 
• L3. 항등원의 존재: 어떤 에 대하여서도, 가 되는 값 이 존재한다.
• L4. 각 원소에 대해 유일한 역원의 존재: 각 에 대하여, 가 되는 가 존재한다.
• L4a. 각 원소의 역원은 사실 자기 자신임: 

C++에서 XOR는 ^ 로 표현합니다.

< XOR을 이용한 교체 알고리즘 >

void swapA(int *x, int *y)
{
	if (x != y)
	{
		*x ^= *y;
		*y ^= *x;
		*x ^= *y;
	}
}

간단히 확인해 보기 위하여 1과 2 교체를 해보도록 하겠습니다.

< 전체 코드 >

#include 
using namespace std;

void swapA(int *x, int *y)
{
	if (x != y)
	{
		*x ^= *y;
		*y ^= *x;
		*x ^= *y;
	}
}

void swapB(int &x, int &y)
{	
	int temp = x;
	x = y;
	y = temp;
}

int main()
{
	int x = 1, y = 2;
	cout << "SwapA" << endl;
	cout << "Initial value : x = " << x << ", y = " << y << endl;
	swapA(&x, &y);
	cout << "swap value : x = " << x << ", y = " << y << endl << endl;
	cout << "SwapB" << endl;
	cout << "Initial value : x = " << x << ", y = " << y << endl;
	swapB(x, y);
	cout << "swap value : x = " << x << ", y = " << y << endl;
}

< 결과 >

실제 XOR을 이용한 방법은 요즘 프로세서에서 임시변수를 두고 사용하는게 더 빠르다고 합니다.(자세한건 위키로)

이런 방법도 있다는것만 알면 될듯 하네요. 

도움되셨길 바랍니다.