[CS][Algorithm] XOR 교체 알고리즘

XOR 교체 알고리즘 그리고 속도에 대한 비교

임시 변수를 이용한 swap 기법과 XOR을 통한 교체 알고리즘에 대해 알아보고 비교합니다.

그동안 단순하게 비트연산 이기 때문에, 무조건적으로 XOR을 사용하는 것이, 일반 연산 대비 더 빠를 것이라고 생각을 했는데 오늘 아는분이 알려주신 것에 대해 검색 해보고 배운 것에 대해서 공유하려고 합니다.

임시변수를 통한 교체 알고리즘

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

이런식으로 임시 변수 temp를 통해 교체하는 알고리즘을 구현 할 수 있습니다.

XOR을 통한 교체 알고리즘

위에서 temp 임시 변수를 통한 교체를 했지만 따로 임시 변수를 두지 않고도 XOR(exclusive or) 연산을 통해서도 두 변수를 교체할수 있습니다.

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

위와 같은 식으로 간단하게 swap을 할 수 있습니다!

TIL 실제 XOR 교체 알고리즘 사용의 장단점

위키 의 나온 장 단점에 대한 글귀를 그대로 갖고왔습니다.

XOR 교체 알고리즘은 대부분의 현대적인 프로세서에서는 임시 변수를 사용하는 방법보다 더 느린데, 
그 이유 중 하나로는 임시 변수를 사용하는 방법은 여러 명령어를 동시에 실행할 수 있도록 
(명령어 수준 병렬성) 최적화하기가 더 쉽기 때문이다. 

XOR 교체 알고리즘은 3 연산 모두 데이터 의존성 (Read-After-Write)을 만들기에 반드시 순서대로만 실행해야한다. 
따라서 현대 비순차 프로세서나 VLIW 컴파일러가 XOR 교체 알고리즘을 최적화할 수 있는 방법은 거의 없다.

반면, XOR 교체 알고리즘은 속도가 그리 빠르지 않아도 되고 
메모리 (혹은 캐시) 사용을 최소화해야 하는 환경에서는 유용하게 사용될 수 있다. 
따라서 이 방식은 임베디드 개발 환경에서 많이 이용된다.

TIL

• 막연하게 비트연산이기 때문 임시변수를 활용한 교체 알고리즘이 더 느릴 것이라고 생각했습니다.
• 내가 정답이라고 당연하게 생각했던 것들은 정답이 아닐수 있다는 생각