Keskustelu: Koodit: C++: XOR swap

Vaihtaa kahden luvun arvot käyttämättä tilapäismuuttujaa.

// funktio vaihtaa annettujen lukujen arvot
// käyttämättä tilapäismuuttujaa
void XorSwap(int& a, int& b)
{
  a ^= b;
  b ^= a;
  a ^= b;
}

a = 5
b = 8

silloin a on binaarina: 0101
ja b on binaarina: 1000

a = a xor b
b = b xor a
a = a xor b

0101
1000
----------
1101

1000
1101
----------
0101

1101
0101
----------
1000

Nyt ne on siis swapattu.

Aika jännä.

No pakko sanoa tähän, että WANHA!
Kätevähän tämä on. Jossei muuta, niin pääsee pätemään c-kielen tunnilla kuten allekirjoittanut :P

Kätevää, ja mitään tilapäismuuttujaa ei näin siis todellakaan tarvita.

Kätevä, mutta wanha.

Tällaset on kyl aika turhia. :|

Tämä swap on hieman monikäyttöisempi

template<typename T>
inline void
swap( T *t1, T *t2 ) {
    t1 ^= t2;
    t2 ^= t1;
    t1 ^= t2;
}

Kunhan muistetaan, että tilapäismuuttujan käyttö on useimmiten nopeampaa. Nykyajan prosessorit nimittäin pyrkivät tekemään mahdollisimman paljon asioita yhtä aikaa. Eli jos meillä on vaikka:

int temp = a;
a = b;
b = temp;

Ensimmäiset (vai toiset? en ole täysin varma) kaksi lauseketta voidaan ajaa samanaikaisesti. Mutta XOR-swapissa kaikkien lausekkeiden arvot riippuvat edellisen arvosta, joten ne täytyy ajaa peräjälkeen, eikä samaan aikaan.

Niin, ja sitten yksi aika tärkeä juttu on jäänyt huomaamatta, ku xor:ia käytetään arvojen swappaamiseen.

Jos a ja b ovat saman muuttujan aliaksia, tai pointtereita, niin silloin ensimmäinen xor-operaatio lykkää molemmat muuttujat nolliksi.

Sitten xor:lla swapattaessa pitää muistaa, ettei samoja aliaksia tai samoissa pointtereissa olevia arvoja rupea xooraamaan.

Eikä tää musta mikään kovin vanha juttu oo. Päinvastoin, moni koodaaja törmää tähän vasta pitkän pitkän ajan perästä. Eiköhän se oo paremminkin niin päin, että ku jos o sitä mieltä, että tää on vanha juttu, niin sitte päinvastoin itellä ei vielä kauheasti oo kokokemusta koodaamisesta, ja sittenhän on hirmu tärkeää päteä, että toi, toi ja toi on vanhaa.

qsortinkin voi ajaa niin silmittömän tehokkaasti, että oksat pois. Varmaa, ku joku sitte sen optimoinnin joskus näissä tosi hyvissä koodivinkeissä esittää, niin heti ensimmäiset näsäviisaat o sanomas, että toihan o vanha juttu, vaikka ei tajua asiasta höläykse pölyä.

__asm ("movl  %0, %%eax\n"
       "xchgl %%eax, %1\n"
       "movl  %%eax, %0\n": : "m"(dwValue1), "m"(dwValue2) : "%eax");

:)