추가 변수(혹은 임시 변수) 없이 SWAP 구현하기

이미지 출처 : Pixabay

일반적으로 배열 등에 있는 두 변수를 교환할때는 call by reference로 두 변수의 메모리 주소를 함수로 넘긴 다음, 다음과 같이 임시변수를 사용하여 값을 교환합니다.

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

다음은 third variable인 tmp변수 선언 없이 두 값을 교환하는 방법들입니다.

Reference : https://www.geeksforgeeks.org/swap-two-numbers-without-using-temporary-variable/

How to swap two numbers without using a temporary variable? - GeeksforGeeks

(위 Reference와 본 포스트 내용을 보지 않고 먼저 구현해보는 것을 추천합니다.)

 

첫 번째 방법은 사칙연산을 사용하는 방법입니다.

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

위 소스코드를 풀어보면 다음과 같습니다.

A = A + B

B = (A + B) - B = A

A = (A + B) - A = B

void swap(int *a, int *b) {
    *a = *a * *b;
    *b = *a / *b;
    *b = *a / *b;
}

위 소스코드를 풀어보면 다음과 같습니다.

A = A * B

B = (A * B) / B = A

A = (A * B) / A = B

 

하지만 이 방법들은 오버플로우가 발생할 수 있다는 치명적인 단점이 있습니다.

또한 곱연산, 나누기 연산을 사용한 경우 두 변수 중 하나가 0인 경우 동작하지 않습니다.

 

두 번째 방법은 bitwise XOR 연산을 사용하는 방법입니다.

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

이는 XOR 연산의 특성 상 교환, 결합 법칙이 성립하고 항등원, 역원이 존재하기에 가능합니다.

위 소스코드를 논리식으로 풀어보면 다음과 같습니다.

A = A ⊕ B

B = B ⊕ (A ⊕ B) = A ⊕ (B ⊕ B) = A ⊕ 0 = A

A = (A ⊕ B) ⊕ A = (A ⊕ A) ⊕ B = 0 ⊕ B = B

 

Reference : https://en.wikipedia.org/wiki/XOR_swap_algorithm

XOR swap algorithm - Wikipedia

위 알고리즘들에는 치명적인 단점이 하나 있는데, 두 포인터가 같은 메모리 공간을 참조하는 경우 올바른 동작을 기대할 수 없다는 것입니다.

(정렬 알고리즘 실행 시 두 포인터가 같은 공간을 참조하게 되는 상황이 발생할 수 있습니다.)

두 포인터가 같은 메모리 공간을 참조하고 있을 때, 덧셈을 활용한 경우 다음과 같이 동작하고,

A = A + B = A + A = 2A

B (= A) = 2A - 2A = 0

A = 0 - 0 = 0

곱연산, 나눗셈 연산을 활용한 경우는 다음과 같이 동작하며,

A = A * B = A * A = A^2

B (= A) = A^2 / A^2 = 1

A = 1 / 1 = 1

XOR 교체 알고리즘은 다음과 같이 동작하게 됩니다.

A = A ⊕ B = A ⊕ A = 0

B (= A) = 0 ⊕ 0 = 0

A = 0 ⊕ 0 = 0

이러한 경우를 막기 위하여 위 알고리즘들을 실제로 사용할 시 두 포인터가 같은 공간을 참조하고 있는지 꼭 확인해야 합니다.

 

일반적인 상황에서는 위에 나열한 알고리즘들보다 임시 변수를 선언하는 것이 더 적절합니다.

위 알고리즘들은 세 줄의 연산 과정이 모두 데이터 의존성을 만들기 때문에 오히려 속도를 저하시키는 결과를 가져올 수 있습니다.