Dlaczego zamień nie używaj operacji Xor w C++

Question

Nauczyłem się, że operacja Xor może być używana do implementacji efektywnej funkcji wymiany. tak:

template<class T> 
void swap(T& a, T& b) 
{ 
    a = a^b; 
    b = a^b; 
    a = a^b; 
} 

Ale realizacja zamiany wszystko, co mogę znaleźć w internecie jest w zasadzie tak:

template<class T> 
void swap(T& a, T& b) 
{ 
    T temp(a); 
    a = b; 
    b = temp; 
} 

Wydaje się, że kompilator nie wygeneruje ten sam kod dla dwóch postaci powyżej, ponieważ przetestowałem go na VC++ 2010, a pierwszy jest wykonywany szybciej (i jest szybszy niż std :: swap). Czy jest jakiś przenośny lub inny problem z pierwszym? Możesz poprawić mój błąd, ponieważ nie jestem Anglikiem i nie jestem dobry w C++.

Answer 1

Nauczyłem się, że operacji XOR może być wykorzystane do wdrożenia skutecznych swap

Nauczyłeś się źle, ja się boję. XOR swap jest nieaktualny: jeśli kiedykolwiek był niezawodnie szybszy niż tymczasowy, to nie powinien być na nowoczesnych kompilatorach i procesorach (gdzie przez "nowoczesny" mam na myśli mniej więcej ostatnie 20 lat lub więcej). Mówisz, że było to dla ciebie szybsze, prawdopodobnie powinieneś pokazać swój kod testu porównawczego i sprawdzić, czy inni osiągają takie same wyniki.

Oprócz faktu, że twój kod działa w ogóle na typach całkowitych, ma on podstawowy błąd. Spróbuj tego z twoją wersją programu wymiany:

int a = 1; 
swap(a,a); 
std::cout << a << '\n'; 

Answer 2

Oczywiście, ponieważ sztuczka xor działa dla typów POD.

Jeśli chcesz zamienić dwa zdefiniowane przez użytkownika typy złożone, xor nie będzie działać. Potrzebujesz głębokiej kopii, a nie bezpośredniej kopii surowej pamięci, która jest czymś, co robi.

EDIT:

Testowałem go na VC++ 2010 i pierwsza szybciej odbywa pracę (i to szybciej niż std :: zamiany).

Naprawdę? Czy skompilowałeś się w trybie debugowania? Jakie są twoje wyniki?

Answer 3

Myślę, że najbardziej oczywistym powodem jest to, że operator XOR ma sens tylko w przypadku typów integralnych.

Answer 4

Po pierwsze, operator XOR jest zdefiniowany tylko dla typów integralnych.

Po drugie, można użyć sztuczek odlewniczych, aby wprowadzić typy nie integralne do postaci integralnej.

Ale po trzecie, dla wszystkich, ale typów POD to powoduje zachowanie niezdefiniowane,

i czwarte dla typów, które nie mają dobrze obsługiwany rozmiar/wyrównanie dla operacji XOR, bardziej skręcenie byłaby wymagana (pętle bycia najmniejsze zło).

Możesz przeciążyć operator^, ale to by znaczyło, że każda specjalizacja swap() musi zapewnić, że istnieje, lub zdefiniować jedną, a to może spowodować więcej zamieszania po wyszukiwaniu nazw niż to, co byłoby tego warte. I oczywiście, jeśli taki operator już istnieje, niekoniecznie zachowuje się prawidłowo i może się okazać, że jest gorzej, ponieważ takie przeciążenie niekoniecznie musi być zgodne z inline lub constexpr.

Answer 5

Skuteczność zależy od tego, gdzie z niego korzystasz.

W normalnej cpu, normalna zamiana na dwa zmiennej całkowitej wygląda

$1 <- a 
$2 <- b 
a <- $2 
b <- $1 

4 OPS 2 obciążeniach 2 sklepach, a najdłuższy z zależnościami wynosi 2

na drodze xor:

$1 <- a 
$2 <- b 
$3 <- $1^$2 
$4 <- $3^$2 
$5 <- $3^$4 
a <- $5 
b <- $4 

7 ops, 2 obciążenia, 2, 3 sklepy logiki i najdłuższy zależność jest 4

Tak co najmniej normalnie zamienia się z XOR jest wolniejszy, nawet jeśli dotyczy.