Välistavat võid kasutav vahetusalgoritm

Allikas: Vikipeedia

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 | redigeeri 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 | redigeeri 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 | redigeeri 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 | redigeeri lähteteksti]