'스왑' 태그의 글 목록

2018. 3. 20. 02:30

xor을 이용한 스왑

변수와 변수의 값을 바꿀 때 보통은 아래와 같이 한다.

void swap(int& a, int& b)
{
	if (a != b)
	{
		int temp = a;
		a = b;
		b = temp;
	{
}

XOR 연산자를 이용해서 연산할 경우에는 temp 변수를 생성하지 않고 할 수 있다. 방법은 아래와 같다.

void swap(int& a, int& b)
{
	if(a != b)
	{
		a = a ^ b
		b = b ^ a
		a = a ^ b
	}
}

XOR 연산은 교환법칙과 결합법칙이 성립한다.

이 법칙들을 이용해서 계산 과정을 살펴보면 아래와 같다.

c = a ^ b

d = b ^ c = b ^ (a ^ b) = b ^ a ^ b = a ^ b ^ b = a ^ 0 = a

e = c ^ d = (a ^ b) ^ a = a ^ b ^ a = a ^ a ^ b = 0 ^ b = b

따라서 XOR 연산을 위와 같이 진행하면 두 값은 swap 된다.

Posted by 아야카