Välistavat võid kasutav vahetusalgoritm

Allikas: Vikipeedia
(Ümber suunatud leheküljelt XOR vahetus algoritm)

Programmeerimises on XOR vahetus algoritm, mis kasutab bitikaupa XOR (välistav või) operaatoreid, et vahetada kahe muutuja väärtused, ilma ajutise lisamuutujata (muutujad peavad omama sama andmetüüpi).

Algoritm[muuda | muuda lähteteksti]

Standardne vahetus algoritm vajab vahemuutujat, kuhu salvestada korraks muutujad salvestada. Kasutades XOR vahetust aga vahemuutjat vaja ei lähe: standard algoritm on järgmine (Lambda keeles):

X := X XOR Y
Y := X XOR Y
X := X XOR Y

Siiski, eksisteerib reaalne oht, kui X ja Y on sünonüümid, siis sellega nullitakse väärtused.

Koodi näited[muuda | muuda lähteteksti]

Tähelepanu, et argumentidena saadud täisarve ei vahetata kohe, vaid esmalt kontrollitakse, kas nende asukohad mälus on erinevad (kas tegemist on sama väärtusega, mis ka omab sama mälu viita). See eemaldab probleemi, mille võib põhjustada pseudonüüm.

C[muuda | muuda lähteteksti]

C funktsioon, mis implementeerib XOR vahetuse algoritmi:

void xorVahetus (int *x, int *y)
{
  if (x != y) {
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
  }
}

Vaata ka[muuda | muuda lähteteksti]