XOR swap ( ing. Xor swap algorithm ) este un algoritm care utilizează operația XOR pe biți (excluzând „sau”) pentru a schimba valori între variabile care conțin date de același tip, fără a utiliza o variabilă suplimentară (temporară). Rezolvarea problemei este oferită datorită proprietății de autoreversibilitate XOR: A XOR A = 0 для всех A.
Algoritm în pseudocod :
X := X XOR Y Y := Y XOR X X := X XOR YAceasta corespunde de obicei la trei instrucțiuni din codul mașinii , cum ar fi codul de asamblare IBM System/370 :
XOR R1, R2 XOR R2, R1 XOR R1, R2unde R1și R2 sunt registre și operația XOR stochează rezultatul în primul argument.
Algoritmul este folosit mai ales în practica programării în asamblator datorită eficienței sale: alți algoritmi de schimb necesită fie utilizarea unui registru intermediar (o resursă suplimentară de stocare), fie (pentru tipurile numerice) operații aritmetice suplimentare (utilizarea unui calcul excesiv. resurse), care este deosebit de important atunci când programați microcontrolere și dispozitive simple similare care au cerințe stricte pentru consumul de memorie și ciclurile procesorului. Unele compilatoare de optimizare pot genera cod care utilizează acest algoritm.
Cu toate acestea, pe CPU -urile moderne de uz general , tehnica XOR poate fi mai lentă decât utilizarea unei variabile temporare pentru schimb datorită paralelizării execuției instrucțiunilor: în tehnica XOR, operanzii tuturor instrucțiunilor depind de rezultatele instrucțiunilor anterioare, astfel încât acestea trebuie executate în ordine strictă secvenţială. Adesea, detaliile algoritmului utilizat sunt ascunse în interiorul unei macro sau a unei funcții inline , iar unul sau altul algoritm de schimb este selectat în funcție de caracteristicile platformei de execuție.
La implementarea unui astfel de algoritm de schimb, există o serie de erori de capcană, în special, dacă funcția de schimb ia pointeri sau referințe și este apelată cu aceleași argumente, atunci datele nu vor fi schimbate, dar datele vor fi resetate. [unu]
Un număr de arhitecturi implementează schimbul XOR la nivel hardware, prima implementare eficientă este mașina Datacraft ( 1970 ), care a asigurat schimbul oricăror registre într-un singur ciclu de ceas. PDP-6 avea această capacitate încă din 1964 ; instrucțiunea sa EXCHar putea schimba conținutul oricărui registru cu conținutul oricărei locații de memorie sau alt registru. Procesoarele x86 au și instrucțiunea XCHG.