# XOR 스왑 알고리즘

### 위키백과 ― 우리 모두의 백과사전.

XOR 스왑 알고리즘은 임시 변수를 두지 않고, 두 개의 변수를 XOR 빗와이즈 오퍼레이션(bitwise operation)을 이용하여 스왑하는 알고리즘이다. 컴퓨터 프로그래밍 분야에서 나온 말이다.

## [편집] 알고리즘

보통의 스왑 알고리즘은 임시 변수를 이용한다. XOR 스왑 알고리즘을 이용하면 임시 변수가 필요없다. 알고리즘은 다음과 같다:

    X := X XOR Y
    Y := X XOR Y
    X := X XOR Y

보통 이 알고리즘은 세 개의 기계어 인스트럭션에 해당한다. IBM System/370에서의 어셈블리 코드는 다음과 같다:

    XR    R1,R2
    XR    R2,R1
    XR    R1,R2

여기서 R1, R2는 레지스터이고 XR은 XOR 명령이다. XR 명령은 그 첫번째와 두번째 오퍼레이터를 XOR해서 그 결과값을 첫번째 레지스터에 저장한다.

만약, X와 Y가 같은 기억장소일 때는 문제가 된다. 처음 XOR 동작에서 0값이 나오니까, 그 기억장소에는 결국 0값이 저장된다; "스스로 스왑"은 불가능하다.

## [편집] 증명

비트 스트링에 대한 XOR 이항 연산은 다음과 같은 성질을 갖는다 (는 XOR을 뜻한다):

- L1. 교환 법칙:
- L2. 결합 법칙:
- L3. 항등원 존재: 어떤 A에 대하여서도, 가 되는 값 Z = 0이 존재한다.
- L4. 각 엘레먼트는 한 개의 역원을 갖는다: 각 A에 대하여, 가 되는 가 존재한다.
  - L4a. 사실, 각 엘레먼트는 그 엘레먼트에 대한 역원이다: .

L1부터 L4까지의 성질은 아벨군(ablian group)의 정의이다. L4a는 XOR 의 구조적 성질에 해당하는 것이며, 아벨 군이나 다른 군에 꼭 있는 성질은 아니다.

`R1`과 `R2`라는 두 개의 레지스터가 있다고 가정하자. 아래 테이블을 보라. 각각 처음에는 값 A와 B를 갖는다. 아래와 같이 순서대로 오퍼레이션을 수행하고, 상기 성질 L1-L4을 이용하여 그 결과를 정리하면 다음과 같다.

Step | Operation | Register 1 | Register 2 | Reduction
--- | --- | --- | --- | ---
1 | Initial value | A | B | --
2 | `R1 := R1 ^ R2` | A^B | B | --
3 | `R2 := R1 ^ R2` | A^B = B^A | (A^B)^B = A^(B^B) = A^0 = A | L1, L2, L4, L3
4 | `R1 := R1 ^ R2` | (B^A)^A = B^(A^A) = B^0 = B | A | L2, L3, L4

## [편집] 코드 예제

## [편집] 실제로 잘 사용하는 이유

## [편집] 실제로 잘 사용하지 않는 이유

## [편집] 변종

## [편집] 함께 보기

| 이 문서는 전산학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.

원본 주소 ‘http://ko.wikipedia.org../../../x/o/r/XOR_%EC%8A%A4%EC%99%91_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_07d4.html’

분류: 전산학 토막글 | 컴퓨터 프로그래밍

##### Views

- 문서
- 토론
- 현재 버전

##### 찾기

##### 다른 언어

- English
- עברית
- 日本語
- Português
- Русский