[Algorithm] XOR 교체 알고리즘을 통해 임시 변수 없이 값 교체하기
임시 변수를 사용하지 않고 값을 교체할 수 있는 XOR 교체 알고리즘에 대해 알아보자
환경
- XOR
- 논리 회로
- 부울 대수
XOR 연산
XOR
XOR:XOR연산이란bit단위에서는 아래의 예시처럼 서로의 비트가 다르면1같으면0의 결과를 나타내는 연산자입니다.
1^1 = 0
1^0 = 1
0^1 = 1
0^0 = 0
// Example in binary
10010101
XOR
10111100
==> 00101001
// Example in decimal
149
XOR
188
==> 41
XOR 교체 알고리즘
XOR 교체 알고리즘이란?
XOR 교체 알고리즘이란 임시 변수를 사용하지 않고 서로 다른 두 개의 변수를 XOR 비트 연산을 이용해 값을 교체하는 알고리즘이다.
XOR 교체 알고리즘 코드 및 예시
예시
의사코드
X := X XOR Y
Y := Y XOR X
X := X XOR Y
C++ 코드
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
int x = 1;
int y = 2;
printf("x: %d y: %d\n", x, y);
if (x != y){
x = x^y;
y = y^x;
x = x^y;
}
printf("x: %d y: %d\n", x, y);
return 0;
}
증명
사용되는 법칙
- 교환법칙: A ⊕ B = B ⊕ A
- 결합법칙: (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
증명
- 아래의 식을 사용
1. X := X XOR Y
2. Y := Y XOR X
3. X := X XOR Y
R1, R2 are registers
0. R1 = X, R2 = Y
1. R1 <- R1 ⊕ R2 = X ⊕ Y
=> R1 = X ⊕ Y, R2 = Y
2. R2 <- R2 ⊕ R1 = Y ⊕ (X ⊕ Y) = Y ⊕ (Y ⊕ X) = (Y ⊕ Y) ⊕ X = 0 ⊕ X = X
=> R1 = X ⊕ Y, R2 = X
3. R1 <- R1 ⊕ R2 = X ⊕ Y ⊕ X = Y ⊕ X ⊕ X = Y ⊕ (X ⊕ X) = Y ⊕ 0 = Y
=> R1 = Y, R2 = X
사용 사례 및 범위
- RAM이 매우 한정적인 임베디드 환경
- Register pressure가 높은 곳
사용하지 않는 이유
- 컴파일러 수준에서 최적화가 진행되기 때문에 임시 변수를 사용하는 방법이 더 빠르다.
- 사용법을 모르는 사람에게는 모호하다.
- 최신 컴퓨터 아키텍처는 명령어 파이프라인에 의해 명령어 수준의 병렬처리가 가능해서 임시 변수를 이용한 교체가 더 빠르다. XOR 교체 알고리즘은 반드시 순서대로 진행되어야 하기에 병렬처리가 어렵다.