XOR-vaihto ( eng. Xor swap algorithm ) on algoritmi , joka käyttää bittikohtaista XOR -toimintoa (pois lukien "tai") vaihtaakseen arvoja samantyyppistä dataa sisältävien muuttujien välillä ilman ylimääräistä (väliaikaista) muuttujaa. Ongelman ratkaisu saadaan itsepalautettavuuden XOR ominaisuudesta johtuen: A XOR A = 0 для всех A.
Algoritmi pseudokoodissa :
X := X XOR Y Y := Y XOR X X := X XOR YTämä vastaa yleensä kolmea ohjetta konekoodissa , kuten IBM System/370 assembler -koodissa :
XOR R1, R2 XOR R2, R1 XOR R1, R2missä R1ja R2 ovat rekistereitä ja XOR-toiminto tallentaa tuloksen ensimmäiseen argumenttiin.
Algoritmia käytetään erityisen usein ohjelmointikäytännössä assemblerissä sen tehokkuuden vuoksi: muut vaihtoalgoritmit vaativat joko välirekisterin käyttöä (lisämuistiresurssi) tai (numeerisille tyypeille) lisäaritmeettisia operaatioita (liian laskentaa). resurssit), mikä on erityisen tärkeää ohjelmoitaessa mikro -ohjaimia ja vastaavia yksinkertaisia laitteita, joilla on tiukat vaatimukset muistinkulutukselle ja prosessorijaksoille. Jotkut optimoivat kääntäjät voivat luoda koodia, joka käyttää tätä algoritmia.
Nykyaikaisissa yleisprosessoreissa XOR-tekniikka voi kuitenkin olla hitaampaa kuin väliaikaisen muuttujan käyttö käskyjen suorittamisen rinnakkaisuuden vuoksi: XOR-tekniikassa kaikkien käskyjen operandit riippuvat aikaisempien käskyjen tuloksista, joten ne on suoritettava tiukasti peräkkäisessä järjestyksessä. Usein käytetyn algoritmin yksityiskohdat piilotetaan makron tai rivifunktion sisään ja yksi tai toinen vaihtoalgoritmi valitaan suoritusalustan ominaisuuksien mukaan.
Tällaista vaihtoalgoritmia toteutettaessa esiintyy useita trap-virheitä, erityisesti jos vaihtotoiminto ottaa osoittimia tai viittauksia ja sitä kutsutaan samoilla argumenteilla, tietoja ei vaihdeta, vaan tiedot nollataan. [yksi]
Useat arkkitehtuurit toteuttavat XOR-vaihdon laitteistotasolla, ensimmäinen tehokas toteutus on Datacraft-kone ( 1970 ), joka tarjosi minkä tahansa rekisterin vaihdon yhdessä kellojaksossa. PDP-6 :lla oli tämä ominaisuus jo vuonna 1964 ; sen käsky EXCHvoisi vaihtaa minkä tahansa rekisterin sisällön minkä tahansa muistipaikan tai muun rekisterin sisällön kanssa. x86-prosessoreissa on myös XCHG-käsky.