XOR Swap jest złe! | Robert Olechowski blog

Trick XOR swap

Kilka słów o pewnym triku, który jest bardzo zły!

Mamy napisać funkcję, która zamienia miejscami dwie zmienne (funkcje swap). Nic prostszego:

auto tmp = x;
x = y;
y = tmp;

A teraz załóżmy, że mamy dodatkowe wymaganie, aby nie korzystać ze zmiennej tymczasowej, czyli swap w miejscu. Jako przykład rozwiązania takiego problemu podaje się poniższy kod:

x = x xor y;
y = x xor y;
x = x xor y;

Podany wyżej kod pojawia się w wielu sytuacjach: jako ciekawostka, jako trik oraz w pytaniach rekrutacyjnych. I niby wszystko funkcjonuje poprawnie. Podstawiamy dwie liczby i działa:

#include <iostream>

using namespace std;
int main() {
    int x=10, y=50;

    x = x xor y;
    y = x xor y;
    x = x xor y;

    cout << "x = " << x <<endl;
    cout << "y = " << y <<endl;
}

Wynik:

x = 50
y = 10

Dlaczego xor swap jest złe

Co wiec jest złego z xor_swap? A czy dwie podane niżej funkcje działają identycznie?

template<typename T>
void Xor_Swap( T& x, T& y ) noexcept
{
    x = x xor y;
    y = x xor y;
    x = x xor y;
}

template<typename T>
void TempSwap( T& x, T& y ) noexcept
{
    auto tmp = x;
    x = y;
    y = tmp;
}

Problem jest taki, że gdy przekazane referencje będą odnosić się do tego samego obszaru pamięci, wówczas funkcja xor_swap nam ten obszar pamięci wyzeruje! Podane powyżej dwie implementacje nie są tożsame. Dla typów wartościowych faktycznie ich działanie jest identyczne, ale dla typów wskaźnikowych istnieje przypadek szczególny.

int main() {
    vector<int> data1 = {1,2,3};
    vector<int> data2 = {1,2,3};

    TempSwap(data1[0],data1[2]);
    Xor_Swap(data2[0],data2[2]);  //Działa poprawnie

    cout << "data1: " << data1[0] << ",  " << data1[1] << ",  " << data1[2] << endl;
    cout << "data2: " << data2[0] << ",  " << data2[1] << ",  " << data2[2] << endl;

    cout << "======== "  << endl;

    TempSwap(data1[0],data1[0]);
    Xor_Swap(data2[0],data2[0]);  //Tu jest problem

    cout << "data1: " << data1[0] << ",  " << data1[1] << ",  " << data1[2] << endl;
    cout << "data2: " << data2[0] << ",  " << data2[1] << ",  " << data2[2] << endl;
}

data1: 3,  2,  1
data2: 3,  2,  1
========
data1: 3,  2,  1
data2: 0,  2,  1