임시변수 없이 swap 하기

• 개요
• XOR
• 사칙연산으로 확장
• 일반화

임시변수 없이 swap을 하는 신박하지만 실제로 쓸모는 없는 방법을 소개한다.

개요

보통 두 변수를 바꾸는 swap 함수는 다음과 같이 구현한다.

void swap(int& a, int& b) {
	int t = a;
	a = b;
	b = t;
}

그러면, 임시변수 t를 사용하지 않고 swap을 구현하는 방법이 있을까?

XOR

결론부터 말하자면, xor 연산을 이용하여 다음과 같이 구현 가능하다.

void swap(int& a, int& b) {
	a ^= b;
	b ^= a;
	a ^= b;
}

이 과정을 수학적으로 써보면 다음과 같이 swap이 됨을 알 수 있다.

초기값: $a = x, b = y$

a ^= b: $a = x \oplus y$

b ^= a: $b = y \oplus (x \oplus y) = x$

a ^= b: $a = (x \oplus y) \oplus x = y$

사칙연산으로 확장

위의 xor을 이용한 방법을 잘 살펴보면, 결국 a에 $x, y$ 값을 쌓아두고, b에서는 $x, y$ 값에서 $y$값을 제외한 것을 가져가고, a에서는 $x, y$ 값에서 $x$값을 제외한 것을 가져감을 알 수 있다.

즉, 쌓아두고 뺄 수 있는 연산이면 모두 이런 식으로 구현 할 수 있다는 것인데, 사칙연산이 이에 해당한다.

덧셈을 이용

void swap(int& a, int& b) {
	a += b;
	b = a - b;
	a = a - b;
}

곱셈을 이용($b \neq 0$)

void swap(int& a, int& b) {
	assert(b != 0);
	a *= b;
	b = a / b;
	a = a / b;
}

단, 이 경우 overflow 문제가 발생 할 수 있으니, xor 연산을 사용하는게 더 안전하고 효율적이다.

일반화

위에서 연산의 쌓아두고 뺄 수 있는 특성을 이용했는데, 이 때 빼는 경우를 수학적으로 역원이라고 생각 할 수 있다.

역원이란 임의의 연산 $*$의 항등원 $e$가 존재 할 때, $a$에 대해 $a * b = b * a = e$ 인 $b$가 유일하게 존재할 때, $b$를 $a$의 역원이라고 한다.

즉, $b$의 역원 $rev(b)$가 존재한다는 것은 $a * b$ 상태에서 $a * b * rev(b) = a$, 즉 $b$를 제외 할 수 있다는 것이다.

이것을 이용하면 역원이 항상 존재하는 연산 $*$을 이용해 swap을 구현 할 수 있다는 것을 알 수 있다.

int oper(int, int); // 역원이 항상 존재하는 어떤 연산
int rev(int); // 위 연산의 역원을 구한다.
void swap(int& a, int& b) {
	a = oper(a, b);
	b = oper(a, rev(b));
	a = oper(a, rev(b));
}