[C++] XOR 연산 이용 swap

여태 쓰던 형태의 swap

#include <iostream>

using namespace std;

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

int main() {
    int a = 4;
    int b = 3;

    cout << a << ", " << b << '\n';
    swap(&a, &b);
    cout << a << ", " << b << '\n';

    return 0;
}

위처럼 swap()안에 temp변수를 새로 만들어서 swap한다.

 

---

XOR연산 이용한 swap

#include <iostream>

using namespace std;

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

int main() {
    int a = 4;
    int b = 3;

    cout << a << ", " << b << '\n';
    swap(&a, &b);
    cout << a << ", " << b << '\n';

    return 0;
}

위처럼 XOR연산(^)을 사용하면 된다.

 

---

설명

복합연산자로 써서 복잡해 보이지만, 풀어서 보면 간단하다.

 

뒤에서부터 풀어보면 결국 swap()내부는 아래와 같다.

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

a값은 현재 4로 2진법으로는 (0100)

b값은 현재 3으로 2진법으로는 (0011)

 

XOR연산은 두 비트가 서로 다를 때 1, 같을 때 0이 된다.

 

먼저 첫째줄부터 a(0100)와 b(0011)를 XOR연산 하면 (0111)로, 해당 값이 a에 들어간다.

둘째줄은 다시 b(0011)와 a(0111)를 XOR연산 한다. (0100)값이 b에 들어간다.

셋째줄은 a(0111)와 b(0100)를 XOR연산 한다. (0011)값이 a에 들어간다.

 

2진수를 다시 10진수로 바꾸면 

a(0011)에는 3, b(0100)에는 4가 들어가있는 것과 같다.

 

swap이 완료되었다.

 

두 값을 XOR연산 한 결과를 각각의 원래 값에 다시 XOR해서 서로의 값으로 바뀌게 한 것이다.

 

---

예시

#include <iostream>

using namespace std;

// 숫자 배열, 크기, 오름차순'A', 내림차순'D'
void sort_func(int *arr, int size, char check) {
    // 버블정렬
    for(int i = 0; i < size; i++) {
        for(int j = 0; j < size - 1 - i; j++) {
            if(check == 'A') {
                if(arr[j] > arr[j + 1]) {
                    arr[j] ^= arr[j + 1] ^= arr[j] ^= arr[j + 1];
                }
            }
            else if(check == 'D') {
                if(arr[j] < arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

void print_func(int *arr, int size) {
    for(int i = 0; i < size; i++) {
        cout << arr[i] << ' ';
    }
    cout << '\n';
}

int main() {
    int arr[5] = { 10, 8, 3, 9, 6};

    sort_func(arr, 5, 'A');
    print_func(arr, 5);
    sort_func(arr, 5, 'D');
    print_func(arr, 5);

    return 0;
}

swap을 사용하기 위해 간단하게 버블정렬을 사용했다.

이해하는데 큰 문제는 없을 것이다.

 

오름차순 정렬은 XOR을 사용한 방법,

내림차순 정렬은 변수를 선언한 방법이다.

 

---

주의사항

 

1. 위 방법은 현대적 프로세서에서 사용할 때, 새로운 변수를 하나 만들어서 스왑하는 것보다 속도가 느리다고 한다. 하지만 메모리를 아낄수는 있다.

 

2. 만약 해당 방법으로 swap할 두 변수가 같은 메모리 위치를 가리키고 있다면(같은 변수 참조) 0으로 값이 바뀌어 버린다.

이 상황이라면 원치않는 값으로 바뀌었으니 매우 치명적인 단점이지만, 두 값을 비교하는 조건을 선행시킨다면 괜찮다.

 

예를 들어 

#include <iostream>

using namespace std;

void print_(int *arr, int size) {
    for(int i = 0; i < size; i++) {
        cout << arr[i] << ' ';
    }
    cout << '\n';
}

int main() {
    int arr[3] = { 3, 4, 5 };

    print_(arr, 3);

	// 인덱스 0과 1 스왑
    arr[0] ^= arr[1] ^= arr[0] ^= arr[1];
    print_(arr, 3);

	// 인덱스 1로 스왑
    arr[1] ^= arr[1] ^= arr[1] ^= arr[1];
    print_(arr, 3);

    return 0;
}

출력 두번째 줄의 인덱스 0, 1은 바뀌었지만, 세번째 줄의 인덱스 1의 값이 0이 되어버렸다.

이중for문을 돌면서 조건이 겹치면 충분히 발생할 수 있는 조건이다.