Välistavat võid kasutav vahetusalgoritm

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

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

Tähelepanu, et argumentidena saadud täisarve ei vahetata koheselt, 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

C funktsioon, mis implementeerib XOR vahetuse algoritmi:

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

Vaata ka

• Algoritmide loend