[스크랩] xor ^

교환

프로그래밍을 하다 보면 두 변수에 담긴 값을 교환 혹은 스왑(swap)할 일이 잦다. 이때 보통 쓰는 방법이 임시 변수를 이용하는 것이다.

간단히 비유를 들어보자. 양손에 각각 사과와 배가 들려 있고 이를 교환하려 한다. 먼저 왼손의 사과를 상에 올려놓고 오른손의 배를 왼손으로 옮긴다. 이제 오른손으로 상 위에 사과를 쥐면 교환은 끝난다.

코드로 나타내면 다음과 같다. 아래에서 변수 temp가 상의 역할을 한다.

temp := p
p := q
q := temp

이 방법도 아주 깔끔하지만 단지 한 번 사용하려고 새 변수를 선언해야 함이 조금 거슬린다. 이런 임시 변수 없이 교환할 방법은 없을까?


XOR 교환 알고리즘

사과와 배의 예로 돌아가자. 이때 상이 없다면 결국 어느 한순간에는 사과와 배 모두를 같은 손에 쥐어야 할 것이다. 즉, 먼저 왼손의 사과를 오른손에 옮겨 오른손에 사과와 배를 한꺼번에 쥔다. 이제 왼손으로 오른손에서 배만 빼오면 교환은 끝난다.

꼭 같진 않지만 이와 닮은 방법이 XOR 교환 알고리즘이다. 이를 코드로 나타내면 다음과 같다. XOR 연산은 ^ 기호로 표시한다.

p := p^q
q := p^q
p := p^q

XOR 연산

먼저 XOR 연산이 무엇인지 잠깐 보자.

논리에서 OR, 이접(離接) 혹은 '또는' 연산은 두 인수 중에 적어도 하나가 참일 때 결과값이 참인 연산이다. XOR 연산은 배타적 이접이라고도 하며 이와 조금 다르다. p, q를 XOR 연산한 결과값 p^q는 두 인수 중에 정확히 하나만 참일 때 참이 되고, p와 q가 모두 참이거나 모두 거짓일 때 거짓이 된다.

요약하면, XOR 연산의 정의는 다음과 같이 묘사된다. 아래에서 T는 참, F는 거짓을 나타낸다.

T^T = F
T^F = T
F^T = T
F^F = F

(사실 일상 언어에서는 '또는'이 배타적 이접을 나타내는 경우가 많다. 이런 표현은 어색하지 않은가? "후식으로 차 또는 커피를 드실 수 있지만, 둘 다는 안 됩니다.")

부울이 아닌 다른 변수형도 그것을 정해진 길이의 부울 문자열로 생각해주면, 그 변수형에서 각 자리별로 계산되는 XOR 연산을 정의할 수 있다.


XOR 교환 알고리즘의 정당성

주어진 변수형을 n 자리 부울 문자열로 생각하자. 이때 다음 성질이 성립함을 쉽게 안다.

교환 법칙: P^Q = Q^P
결합 법칙: (P^Q)^R = P^(Q^R)
항등원의 존재: E가 존재하여, 어떤 P에 대해서든 P^E = E^P = P 이다.
역원의 존재: 각 P에 대하여, P^IP = IP^P = E 인 IP가 존재한다.

(이 변수형의 변수가 가질 수 있는 모든 값들의 집합에 XOR 연산을 준 구조는 대수적으로 2차 군(群) n 개를 직접곱(直接-)한 것, 즉 Z2 × Z2 × … × Z2 과 동형이다.)

구체적으로 항등원 E는 T T … T, 즉 모든 자리가 참인 문자열이며 각 P에 대한 역원은 P 자신이다. 다시 말해, 모든 P에 대해 P^E = P, P^P = E 이다.

이제 위 성질을 이용해서 XOR 교환 알고리즘이 어떻게 작동하는지 단계별로 살펴보자. 아래에서 p, q는 변수이고 P, Q는 각각 두 변수가 처음에 담은 값이다.

0 단계

p ← P
q ← Q

1 단계

p := p^q ← P^Q
q ← Q

2 단계

p ← P^Q = Q^P
q := p^q ← (P^Q)^Q = P^(Q^Q) = P^E = P

3 단계

p := p^q ← (Q^P)^P = Q^(P^P) = Q^E = Q
q ← P

이로써 알고리즘이 정당함을 보였다.

(군론의 표기법에 따르면 다음과 같다. 아래에서 항등원은 e, x 의 역원은 x' 로 적는다.
0 단계

p ← g
q ← h

1 단계

p := p*q' ← g*h'
q ← h

2 단계

p ← g*h'
q := p*q ← (g*h')*h = g*(h'*h) = g*e = g

3 단계

p := p'*q ← (g*h')'*g = (h*g')*g = h*(g'*g) = h*e = h
q ← g)

맺음말

마지막으로 ―내가 잘 모르고, 관심도 없는― 실용성에 대해 덧붙이자면, XOR 교환 알고리즘이 임시 변수를 이용한 것보다 일반적으로 좋은 것은 아니다. 컴파일러나 인터프리터 그리고 프로세서에 따라 차이가 있지만, 요즘은 도리어 더 느린 경우가 많다고 한다. 다만, 메모리를 되도록 아껴야 하는 임베디드 개발 환경에서는 이 방식이 많이 이용된다.

요즘의 프로세서는 대부분 교환을 처리하기 위한 명령어를 지원한다. 굳이 비유하자면 사과와 배를 동시에 공중에 던져서 재빨리 바꿔 잡는 것이 되겠다. 일부 컴파일러나 인터프리터는 임시 변수를 사용한 교환과 같이 자주 사용되는 코드를 자동으로 감지해 적절한 기계어로 변환해 주기도 한다.
--------------------------------------------------------------------------------
원래 글 주소
http://intothereign.tistory.com/35

보통 swap() 함수를 구현할 때는 temp 변수를 이용하곤 합니다. 대단한 팁은 아니지만 XOR을 이용하여 swap() 함수를 구현하는 방법입니다.

1	void swap(int *x, int *y)

2

{

3	*x = *x ^ *y;

4	*y = *x ^ *y;

5	*x = *x ^ *y;

6

}

어떻게 swap이 되는지 이해가 가시나요? 식을 풀어써 보면 쉽게 이해가 갑니다. XOR 연산은 같으면 0, 다르면 1이라는 것을 명심하구요.

1. *x = *x ^ *y
2. *y = *x ^ *y ^ *y
3. *x = *x ^ *y ^ *x

식 2의 계산 과정을 풀어쓰면…

1	*y = *x ^ 0; // *y ^ *y == 0

 

2	*y = *x; // *x ^ 0 == *x

식 3의 계산 과정을 풀어쓰면…

1	*x = 0 ^ *y; // *x ^ *x == 0

2	*x = *y; // 0 ^ *y == *y

원문 주소 http://nayabin.maru.net/?p=1964