XOR swap ( eng. Xor swap algorithm ) er en algoritme , der bruger den bitvise XOR -operation (eksklusive "eller") til at udveksle værdier mellem variabler, der indeholder data af samme type, uden at bruge en ekstra (midlertidig) variabel. Løsningen af problemet er tilvejebragt på grund af egenskaben af selvreversibilitet XOR: A XOR A = 0 для всех A.
Algoritme i pseudokode :
X := X XOR Y Y := Y XOR X X := X XOR YDette svarer normalt til tre instruktioner i maskinkoden , såsom i IBM System/370 assembler kode :
XOR R1, R2 XOR R2, R1 XOR R1, R2hvor R1og R2 er registre , og XOR-operationen gemmer resultatet i det første argument.
Algoritmen bruges især ofte i praksis med programmering i assembler på grund af dens effektivitet: andre udvekslingsalgoritmer kræver enten brugen af et mellemregister (en ekstra lagerressource) eller (for numeriske typer) yderligere aritmetiske operationer (brugen af overdreven databehandling) ressourcer), hvilket er særligt vigtigt ved programmering af mikrocontrollere og lignende simple enheder, der har strenge krav til hukommelsesforbrug og processorcyklusser. Nogle optimeringskompilere kan generere kode, der bruger denne algoritme.
På moderne CPU'er til generelle formål kan XOR-teknikken dog være langsommere end at bruge en midlertidig variabel til udveksling på grund af paralleliseringen af instruktionsudførelsen: i XOR-teknikken afhænger operanderne af alle instruktioner af resultaterne af tidligere instruktioner, så de skal udføres i streng rækkefølge. Ofte er detaljerne i den anvendte algoritme skjult inde i en makro eller en inline-funktion , og en eller anden udvekslingsalgoritme vælges afhængigt af funktionerne i udførelsesplatformen.
Når en sådan udvekslingsalgoritme implementeres, er der en række fældefejl, især hvis udvekslingsfunktionen tager pointere eller referencer og kaldes med de samme argumenter, vil data ikke blive udvekslet, men data vil blive nulstillet. [en]
En række arkitekturer implementerer XOR-udveksling på hardwareniveau, den første effektive implementering er Datacraft-maskinen ( 1970 ), som sørgede for udveksling af eventuelle registre i en clock-cyklus. PDP-6 havde denne evne allerede i 1964 ; dens instruktion EXCHkunne udveksle indholdet af ethvert register med indholdet af enhver hukommelsesplacering eller andet register. x86-processorer har også XCHG-instruktionen.