XOR swap ( eng. Xor swap algorithm ) är en algoritm som använder den bitvisa XOR- operationen (exklusive "eller") för att utbyta värden mellan variabler som innehåller data av samma typ, utan att använda en extra (temporär) variabel. Lösningen av problemet tillhandahålls på grund av egenskapen självreversibilitet XOR: A XOR A = 0 для всех A.
Algoritm i pseudokod :
X := X XELLER Y Y := Y XELLER X X := X XELLER YDetta motsvarar vanligtvis tre instruktioner i maskinkoden , till exempel i IBM System/370 assemblerkod :
XOR R1, R2 XOR R2, R1 XOR R1, R2där R1och R2 är register och XOR-operationen lagrar resultatet i det första argumentet.
Algoritmen används särskilt ofta i praktiken av programmering i assembler på grund av dess effektivitet: andra utbytesalgoritmer kräver antingen användning av ett mellanregister (en extra lagringsresurs) eller (för numeriska typer) ytterligare aritmetiska operationer (användning av överdriven beräkning resurser), vilket är särskilt viktigt vid programmering av mikrokontroller och liknande enkla enheter som har strikta krav på minnesförbrukning och processorcykler. Vissa optimerande kompilatorer kan generera kod som använder denna algoritm.
På moderna processorer för allmänna ändamål kan dock XOR-tekniken vara långsammare än att använda en temporär variabel för utbyte på grund av parallelliseringen av instruktionsexekveringen: i XOR-tekniken beror operanderna för alla instruktioner på resultatet av tidigare instruktioner, så de måste utföras i strikt sekventiell ordning. Ofta är detaljerna i den använda algoritmen gömda i ett makro eller en inline-funktion , och en eller annan utbytesalgoritm väljs beroende på exekveringsplattformens funktioner.
När man implementerar en sådan utbytesalgoritm finns det ett antal trap-fel, i synnerhet om utbytesfunktionen tar pekare eller referenser och anropas med samma argument, kommer data inte att utbytas utan data kommer att återställas. [ett]
Ett antal arkitekturer implementerar XOR-utbyte på hårdvarunivå, den första effektiva implementeringen är Datacraft-maskinen ( 1970 ), som gav utbyte av alla register i en klockcykel. PDP-6 hade denna förmåga så tidigt som 1964 ; dess instruktion EXCHkan utbyta innehållet i vilket register som helst med innehållet i vilken minnesplats eller annat register som helst. x86-processorer har också XCHG-instruktionen.