XOR swap ( angl. Xor swap algorithm ) je algoritmus , který používá bitovou operaci XOR (kromě „nebo“) k výměně hodnot mezi proměnnými, které obsahují data stejného typu, bez použití další (dočasné) proměnné. Řešení problému je zajištěno díky vlastnosti sebereverzibility XOR: A XOR A = 0 для всех A.
Algoritmus v pseudokódu :
X := X XOR Y Y := Y XOR X X := X XOR YTo obvykle odpovídá třem instrukcím ve strojovém kódu , například v kódu assembleru IBM System/370 :
XOR R1, R2 XOR R2, R1 XOR R1, R2kde R1a R2 jsou registry a operace XOR uloží výsledek do prvního argumentu.
Algoritmus je zvláště často používán v praxi programování v assembleru kvůli jeho efektivitě: jiné algoritmy výměny vyžadují buď použití přechodného registru (další úložný zdroj) nebo (u numerických typů) další aritmetické operace (použití nadměrného počítání zdrojů), což je důležité zejména při programování mikrokontrolérů a podobných jednoduchých zařízení, která mají přísné požadavky na spotřebu paměti a cykly procesoru. Některé optimalizační kompilátory mohou generovat kód, který používá tento algoritmus.
Na moderních univerzálních CPU však může být technika XOR pomalejší než použití dočasné proměnné pro výměnu kvůli paralelizaci provádění instrukcí: v technice XOR závisí operandy všech instrukcí na výsledcích předchozích instrukcí, takže musí být provedeny v přísném sekvenčním pořadí. Podrobnosti o použitém algoritmu jsou často skryty uvnitř makra nebo vložené funkce a jeden nebo jiný algoritmus výměny je vybrán v závislosti na vlastnostech prováděcí platformy.
Při implementaci takového algoritmu výměny dochází k řadě chyb v pasti, zejména pokud funkce výměny bere ukazatele nebo odkazy a je volána se stejnými argumenty, data se nevyměňují, ale data se resetují. [jeden]
Řada architektur implementuje XOR-exchange na hardwarové úrovni, první efektivní implementací je stroj Datacraft ( 1970 ), který zajišťoval výměnu libovolných registrů v jednom hodinovém cyklu. PDP-6 měl tuto schopnost již v roce 1964 ; jeho instrukce EXCHby mohla vyměnit obsah libovolného registru s obsahem libovolného paměťového místa nebo jiného registru. Procesory x86 mají také instrukci XCHG.