XOR swap trick에 대한 너무 많은 논의

XOR는 두 값이 다르면 1, 같으면 0이 되는 연산이고, 이를 이용하면 임시 변수 없이 두 값을 교환할 수 있다.

• a ^= b; b ^= a; a ^= b; 형태의 XOR swap은 수학적으로는 동작한다.
• 하지만 로컬 변수에서는 컴파일러가 이미 교환 의도를 파악해 더 단순한 코드로 최적화한다.
• clang -O2 기준으로 XOR swap과 temp 변수 swap은 실제로 같은 어셈블리로 귀결된다.

포인터를 통한 swap에서는 더 분명하다.

• swap_temp(&x, &x) 는 같은 주소를 두 번 써도 결과가 유지되지만,
• swap_xor(&x, &x) 는 첫 XOR에서 값이 0으로 파괴된다.
• 그래서 두 함수는 의미적으로 같지 않으며, 컴파일러는 XOR 연산을 그대로 내보낼 수밖에 없다.
• restrict 를 붙여 aliasing이 없음을 보장하면, 컴파일러는 다시 XOR를 없애고 temp swap과 같은 형태로 바꾼다.

addition/subtraction swap도 소개되지만 더 문제다.

• 정수에서는 signed overflow UB 위험이 있다.
• 부동소수점에서는 정밀도 손실로 값이 조용히 사라질 수 있다.
• 따라서 XOR 버전이 그나마 overflow UB는 피하지만, 실용성은 여전히 없다.

이 기법이 언급되는 이유는 대부분 인터뷰용 트릭이기 때문이다.

• 정말 의미가 있는 경우는 레지스터가 꽉 찬 저수준 어셈블리 정도다.
• 다만 대부분의 현대 환경에서는 mov 세 번이나 전용 교환 명령이 더 낫다.
• x86은 오래전부터 XCHG 를 제공했고, Z80처럼 XOR swap이 일반화되기 어려운 아키텍처도 있다.

마지막으로 XOR의 다른 용도도 짚는다.

• 리스트에서 한 값만 한 번 나오고 나머지는 두 번씩 나올 때, 전체를 XOR하면 유일한 값이 남는다.
• 이는 중복 값 상쇄라는 XOR의 성질을 이용한 대표적 응용이다.

결론은 명확하다. XOR swap은 대부분의 C 코드에서 필요 없고, 종종 더 나쁘며, 가끔은 위험하다.