[Cpp]XOR 스왑

🤔XOR 스왑

🔑비트 연산 XOR 사용

임시 변수를 사용하지 않고 두 변수를 교환하는 방법이다.

예를 들어 a = 3, b = 4라고 하고 이 두 변수를 교환한다고 가정해보자.

\[\begin{gather} a = 3_{(10)} = 011_{(2)} \\ b = 4_{(10)} = 100_{(2)} \end{gather}\]

이 두 수에 세 개의 XOR 연산을 사용하여 서로 교환할 수 있다. (XOR 연산은 두 비트가 서로 같으면 0, 다르면 1이 결과가 되는 연산이다.)

\[\begin{gather} a = a \oplus b = 011_{(2)} \oplus 100_{(2)} = 111_{(2)} \\ b = a \oplus b = 111_{(2)} \oplus 100_{(2)} = 011_{(2)} = 3 \\ a = a \oplus b = 111_{(2)} \oplus 011_{(2)} = 100_{(2)} = 4 \end{gather}\]

#include <iostream>

void XORSwap(int* a, int* b)
{
	*a = *a ^ *b;
	*b = *a ^ *b;
	*a = *a ^ *b;
}

int main()
{
    int a = 5;
    int b = 10;

    XORSwap(a, b);
    std::cout << a << " " << b << std::endl;
}

🔑문제점

위의 XOR 스왑을 그대로 사용하기에 문제가 있다.

XORSwap() 함수에 같은 주소를 가리키는 변수(예를 들어, a와 a)를 넘겨준다고 했을 때, a의 값이 0이 되어버린다.

XORSwap의 매개변수 a와 b는 같은 주소를 가리키고 있어서 a가 0이 되면 b도 0이 된다. 그렇게 a의 값이 0으로 바뀌어 버리는 문제가 생긴다.

\[\begin{gather} a = a \oplus b = 011_{(2)} \oplus 011_{(2)} = 000_{(2)} \\ b = a \oplus b = 000_{(2)} \oplus 000_{(2)} = 000_{(2)} \\ a = a \oplus b = 000_{(2)} \oplus 000_{(2)} = 000_{(2)} \end{gather}\]

반면에 값은 같지만 서로 다른 주소를 가리키는 두 변수를 교환하는 것은 문제가 되지 않는다. a가 0이 되더라도 b는 0이 되지 않으므로 a가 다시 원래 값으로 되돌아간다.

\[\begin{gather} a = a \oplus b = 011_{(2)} \oplus 011_{(2)} = 000_{(2)} \\ b = a \oplus b = 000_{(2)} \oplus 011_{(2)} = 011_{(2)} \\ a = a \oplus b = 000_{(2)} \oplus 011_{(2)} = 011_{(2)} \end{gather}\]

따라서 교환할 숫자가 0이 되지 않기 위해 XORSwap()에 주소가 같은 인자가 들어가지 않도록 예외를 처리해줘야 한다.

void XORSwap(int* a, int* b)
{
	if (a != b)
	{
		*a = *a ^ *b;
		*b = *a ^ *b;
		*a = *a ^ *b;
	}
}