XOR swap-algoritm

Använda XOR swap-algoritmen för att utbyta nibbles mellan variabler utan användning av tillfällig lagring

I datorprogrammering är den exklusiva eller swap (ibland förkortad till XOR swap ) en algoritm som använder den exklusiva eller bitvisa operationen för att byta värden för två variabler utan att använda den temporära variabeln som normalt krävs.

Algoritmen är i första hand en nyhet och ett sätt att demonstrera egenskaperna hos den exklusiva eller operationen. Det diskuteras ibland som en programoptimering , men det finns nästan inga fall där byte via exklusivt eller ger fördelar jämfört med den vanliga, uppenbara tekniken.

Algoritmen

Konventionellt byte kräver användning av en temporär lagringsvariabel. Med XOR-swapalgoritmen behövs dock ingen tillfällig lagring. Algoritmen är som följer:

     
     
      X  :=  X  XOR  Y  ;  // XOR värdena och lagra resultatet i X  Y  :=  Y  XOR  X  ;  // XOR värdena och lagra resultatet i Y  X  :=  X  XOR  Y  ;  // XELLER värdena och lagra resultatet i X

Eftersom XOR är en kommutativ operation , kan antingen XXOR Y eller Y XOR X användas omväxlande i någon av de tre föregående raderna. Observera att på vissa arkitekturer anger den första operanden av XOR-instruktionen målplatsen där resultatet av operationen lagras, vilket förhindrar denna utbytbarhet. Algoritmen motsvarar vanligtvis tre maskinkodinstruktioner , representerade av motsvarande pseudokod och monteringsinstruktioner i de tre raderna i följande tabell:

Pseudokod	IBM System/370 montering	x86 montering
`X := X XELLER Y`	`XR R1 , R2`	`xor eax , ebx`
`Y := Y XOR X`	`XR R2 , R1`	`xor ebx , eax`
`X := X XELLER Y`	`XR R1 , R2`	`xor eax , ebx`

I ovanstående System/370-sammansättningskodprov är R1 och R2 distinkta register , och varje XR- operation lämnar sitt resultat i registret som namnges i det första argumentet. Med x86-sammansättning finns värdena X och Y i registren eax och ebx (respektive), och xor placerar resultatet av operationen i det första registret.

Emellertid, i pseudokoden eller högnivåspråkversionen eller implementeringen, misslyckas algoritmen om x och y använder samma lagringsplats, eftersom värdet som lagras på den platsen nollställs av den första XOR-instruktionen och sedan förblir noll; den kommer inte att "bytas med sig själv". Detta är inte samma sak som om x och y har samma värden. Problemet kommer bara när x och y använder samma lagringsplats, i vilket fall deras värden redan måste vara lika. Det vill säga, om x och y använder samma lagringsplats, då raden:

     X  :=  X  XELLER  Y

sätter x till noll (eftersom x = y så X XELLER Y är noll) och sätter y till noll (eftersom den använder samma lagringsplats), vilket gör att x och y förlorar sina ursprungliga värden.

Bevis på riktighet

Den binära operationen XOR över bitsträngar med längden $N$ uppvisar följande egenskaper (där $\oplus$ anger XOR):

L1. Kommutativitet : $A\oplus B=B\oplus A$
L2. Associativitet : $(A\oplus B)\oplus C=A\oplus (B\oplus C)$
L3. Identitet finns : det finns en bitsträng, 0, (av längden N ) så att $A\oplus 0=A$ för valfri $A$
L4. Varje element är sin egen invers : för varje $A$ , $A\oplus A=0$ .

Antag att vi har två distinkta register R1 och R2 som i tabellen nedan , med initialvärden A respektive B. Vi utför operationerna nedan i ordningsföljd och minskar våra resultat med hjälp av egenskaperna som anges ovan.

Steg	Drift	Registrera dig 1	Registrera dig 2	Minskning
0	Ursprungligt värde	$A$	$B$	—
1	`R1 := R1 XOR R2`	$A\oplus B$	$B$	—
2	`R2 := R1 XOR R2`	$A\oplus B$	$(A\oplus B)\oplus B=A\oplus (B\oplus B)$ $=A\oplus 0$ $=A$	L2 L4 L3
3	`R1 := R1 XOR R2`	$(A\oplus B)\oplus A=(B\oplus A)\oplus A$ $= B\oplus (A\oplus A)$ $=B\oplus 0$ $=B$	$\ A$	L1 L2 L4 L3

Linjär algebratolkning

Eftersom XOR kan tolkas som binär addition och ett par bitar kan tolkas som en vektor i ett tvådimensionellt vektorutrymme över fältet med två element , kan stegen i algoritmen tolkas som multiplikation med 2×2 matriser över fält med två element. För enkelhetens skull, anta initialt att x och y var och en är enstaka bitar, inte bitvektorer.

Till exempel steget:

     X  :=  X  XELLER  Y

som också har det implicita:

   Y  :=  Y

motsvarar matrisen $\left({\begin{smallmatrix}1&1\\0&1\end{smallmatrix}}\right)$ som

{\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}={\begin{pmatrix}x+y\\y\end {pmatrix}}.

Sekvensen av operationer uttrycks sedan som:

{\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}1&0\\1&1\ end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}

(arbetar med binära värden, så $1+1=0$ ), vilket uttrycker den elementära matrisen för att byta två rader (eller kolumner) i termer av transvektionerna (skjuvningar) för att lägga till ett element till det andra .

För att generalisera till där X och Y inte är enstaka bitar, utan istället bitvektorer med längden n , ersätts dessa 2×2-matriser med 2 n ×2 n blockmatriser såsom $\left({\begin{smallmatrix}I_{n}&I_{n}\\0&I_{n}\end{smallmatrix}}\right).$

Dessa matriser arbetar på värden, inte på variabler (med lagringsplatser), därför abstraherar denna tolkning bort från frågor om lagringsplats och problemet med att båda variablerna delar samma lagringsplats.

Kodexempel

En C -funktion som implementerar XOR-swapalgoritmen:

     

     
  
      
      
      
  
 void  XorSwap  (  int  *  x  ,  int  *  y  )  {  if  (  x  !=  y  )  {  *  x  ^=  *  y  ;  *  y  ^=  *  x  ;  *  x  ^=  *  y  ;  }  }

Koden kontrollerar först om adresserna är distinkta. Annars, om de var lika, skulle algoritmen vikas till en trippel *x ^= *x vilket resulterade i noll.

XOR-swapalgoritmen kan också definieras med ett makro:







 #define XORSWAP_UNSAFE(a, b) \  ((a) ^= (b), (b) ^= (a), \  (a) ^= (b))  /* Fungerar inte när a och b är samma objekt - tilldelar noll \  (0) till objektet i det fallet */  #define XORSWAP(a, b) \  ((&(a) == &(b)) ? (a)  /* Sök efter distinkta adresser * /  \  : XORSWAP_UNSAFE(a, b))

Skäl till undvikande i praktiken

På moderna CPU-arkitekturer kan XOR-tekniken vara långsammare än att använda en temporär variabel för att byta. Åtminstone på de senaste x86-processorerna, både av AMD och Intel, medför att flytta mellan register regelbundet noll latens. (Detta kallas MOV-eliminering.) Även om det inte finns något arkitektoniskt register tillgängligt att använda, XCHG- instruktionen att vara minst lika snabb som de tre XOR tillsammans. En annan anledning är att moderna CPU:er strävar efter att exekvera instruktioner parallellt via instruktionspipelines . I XOR-tekniken beror ingångarna till varje operation på resultatet av den föregående operationen, så de måste utföras i strikt sekventiell ordning, vilket förnekar alla fördelar med parallellism på instruktionsnivå .

Aliasing

XOR-bytet kompliceras också i praktiken genom aliasing . Om ett försök görs att XOR-byta innehållet på någon plats med sig själv, blir resultatet att platsen nollställs och dess värde förloras. Därför får XOR-byte inte användas blint på ett högnivåspråk om alias är möjligt. Det här problemet gäller inte om tekniken används vid montering för att byta innehållet i två register.

Liknande problem uppstår med call by name , som i Jensens Device , där byte av i och A[i] via en temporär variabel ger felaktiga resultat på grund av att argumenten är relaterade: swapping via temp = i; i = A[i]; A[i] = temp ändrar värdet för i i den andra satsen, vilket sedan resulterar i det felaktiga i-värdet för A[i] i den tredje satsen.

Variationer

Den underliggande principen för XOR-swapalgoritmen kan tillämpas på alla operationer som uppfyller kriterierna L1 till L4 ovan. Att ersätta XOR genom addition och subtraktion ger olika lite olika, men i stort sett ekvivalenta, formuleringar. Till exempel:

        

     
  
        
        
        
  
 void  AddSwap  (  osignerad  int  *  x  ,  osignerad  int  *  y  )  {  if  (  x  !=  y  )  {  *  x  =  *  x  +  *  y  ;  *  y  =  *  x  -  *  y  ;  *  x  =  *  x  -  *  y  ;  }  }

Till skillnad från XOR-bytet kräver denna variation att den underliggande processorn eller programmeringsspråket använder en metod som modulär aritmetik eller bignums för att garantera att beräkningen av X + Y inte kan orsaka ett fel på grund av heltalsspill . Därför ses det ännu mer sällan i praktiken än XOR-bytet.

Implementeringen av AddSwap ovan i programmeringsspråket C fungerar dock alltid även vid heltalsspill, eftersom addition och subtraktion av heltal utan tecken enligt C-standarden följer reglerna för modulär aritmetik , dvs görs i den cykliska gruppen $\mathbb {Z} /2^{s}\mathbb {Z}$ där $s$ är antalet bitar av osignerad int . Faktum är att algoritmens korrekthet följer av det faktum att formlerna $(x+y)-y=x$ och $(x+y)-((x+y)-y)=y$ håller i valfri abelsk grupp . Detta generaliserar beviset för XOR-swapalgoritmen: XOR är både addition och subtraktion i den abelska gruppen $(\mathbb {Z} /2\mathbb {Z} )^{s}$ (vilket är den direkta summan av s kopior av ${\displaystyle \mathbb {Z} /2\mathbb {Z} } )$ .

Detta gäller inte när man hanterar den signerade int- typen (standardinställningen för int ). Signerat heltalsspill är ett odefinierat beteende i C och därför garanteras inte modulär aritmetik av standarden, vilket kan leda till felaktiga resultat.

Sekvensen av operationer i AddSwap kan uttryckas via matrismultiplikation som:

{\begin{pmatrix}1&-1\\0&1\end{pmatrix}}{\begin{pmatrix}1&0 \\1&-1\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}

Ansökan om att registrera tilldelning

På arkitekturer som saknar en dedikerad växlingsinstruktion, eftersom den undviker det extra temporära registret, krävs XOR swap-algoritmen för optimal registerallokering . Detta är särskilt viktigt för kompilatorer som använder statisk enkel tilldelningsformulär för registertilldelning; dessa kompilatorer producerar ibland program som behöver byta två register när inga register är lediga. XOR swap-algoritmen undviker behovet av att reservera ett extra register eller att spilla några register till huvudminnet. Alternativet addition/subtraktion kan också användas för samma ändamål.

Denna metod för registerallokering är särskilt relevant för GPU- skuggningskompilatorer. På moderna GPU-arkitekturer är det dyrt att spilla variabler på grund av begränsad minnesbandbredd och hög minneslatens, medan begränsning av registeranvändning kan förbättra prestandan på grund av dynamisk partitionering av registerfilen . XOR-swapalgoritmen krävs därför av vissa GPU-kompilatorer.

Se även

Symmetrisk skillnad
XOR länkad lista
Feistel-chiffer (XOR-swap-algoritmen är en degenererad form av ett Feistel-chiffer)

Anteckningar