XOR 교체 알고리즘

1 개요

XOR swap algorithm

XOR 교체 알고리즘, XOR 스왑 알고리즘

• 임시 변수를 두지 않고, 두 변수를 배타적 논리합(XOR) 비트 연산을 이용하여 교체하는 알고리즘
• 추가 메모리 공간이 필요없다는 장점이 있다.
• 그렇지만 특별한 상황이 아니라면 권장되지 않는다.

2 잘 안쓰는 이유

• (성능) 모던 CPU 아키텍처에서 임시변수를 사용하는 방법보다 느리다.

XOR 기법은 CPU 인스트럭션간 강한 의존성(순서)가 있어 병렬처리 효율을 떨어뜨린다.

• (역사) 컴퓨터 그래픽 한정이기 하나, 미국특허(US4197590)로 등록이 된 바 있다.

3 같이 보기

• 함수 swap()
• 함수 xor_swap() - XOR 교체 알고리즘 구현
• XOR

4 참고

• 영어 위키백과 "XOR swap algorithm"