Välistavat võid kasutav vahetusalgoritm

Programmeerimises on XOR vahetusalgoritm, mis kasutab bitikaupa XOR (välistav või) operaatoreid kahe samatüübilise muutuja väärtuste vahetamiseks ilma ajutise lisamuutujata.

Algoritm

Standardne vahetusalgoritm vajab muutuja vahepealseks salvestamiseks vahemuutujat. XOR-vahetuse kasutamisel vahemuutjat vaja ei lähe, selle standardalgoritm on järgmine (Lambda keeles):

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

Siiski on reaalne oht väärtuste nullimiseks olukorras, kus X ja Y on sünonüümid.

Koodinäited

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 pseudonüümi poolt põhjustatava võimaliku probleemi.

C

XOR-vahetusalgoritmi teostav C funktsioon:

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

Vaata ka

• Algoritmide loend