Comment fonctionne L'échange de variables XOR?

d'Autres personnes ont expliqué, maintenant, je veux expliquer pourquoi c'était une bonne idée, mais maintenant, n'est-ce pas.

à l'époque où nous avions des CPU simples à cycle simple ou à cycle multiple, il était moins coûteux d'utiliser cette astuce pour éviter des déréférences de mémoire coûteuses ou le déversement de registres à la pile. Cependant, nous avons maintenant CPUs avec des pipelines massifs à la place. Le pipeline du P4 comportait de 20 à 31 (ou plus) étapes, où toute dépendance entre la lecture et l'écriture une caisse enregistreuse pourrait tout faire capoter. Le swap xor a de très fortes dépendances entre A et B qui n'ont pas d'importance, mais qui bloquent le pipeline dans la pratique. Un pipeline bloqué provoque un chemin de code lent, et si ce swap est dans votre boucle interne, vous allez vous déplacer très lentement.

en pratique générale, votre compilateur peut comprendre ce que vous voulez vraiment faire quand vous faites un swap avec une variable temp et peut le compiler avec une instruction xchg unique. L'utilisation du swap xor rend beaucoup plus difficile pour le compilateur de deviner votre intention et donc beaucoup moins susceptible de l'optimiser correctement. Sans parler de la maintenance du code, etc.

j'aime y penser graphiquement plutôt que numériquement.

disons que vous commencez avec x = 11 et y = 5 En binaire (et je vais utiliser une hypothétique machine 4 bits), voici x et y

       x: |1|0|1|1|   -> 8 + 2 + 1
       y: |0|1|0|1|   -> 4 + 1

maintenant pour moi, XOR est une opération inverse et le faire deux fois est un miroir:

     x^y: |1|1|1|0|
 (x^y)^y: |1|0|1|1|   <- ooh!  Check it out - x came back
 (x^y)^x: |0|1|0|1|   <- ooh!  y came back too!

En voici un qui devrait être légèrement plus facile à grok:

int x = 10, y = 7;

y = x + y; //x = 10, y = 17
x = y - x; //x = 7, y = 17
y = y - x; //x = 7, y = 10

maintenant, on peut comprendre l'astuce XOR un peu plus facilement en comprenant que ^ peut être considéré comme + ou - . Tout comme:

x + y - ((x + y) - x) == x 

, donc:

x ^ y ^ ((x ^ y) ^ x) == x

la raison pour laquelle il fonctionne est parce que XOR ne perd pas l'information. Vous pourriez faire la même chose avec l'addition et la soustraction ordinaires si vous pouviez ignorer le débordement. Par exemple, si la paire de variables A,B contient à l'origine les valeurs 1,2, vous pouvez les échanger comme ceci:

 // A,B  = 1,2
A = A+B // 3,2
B = A-B // 3,1
A = A-B // 2,1

BTW il y a un vieux truc pour encoder une liste bidirectionnelle dans un seul "pointeur". Supposons que vous ayez une liste de blocs de mémoire aux adresses A, B et C. Le premier mot dans chaque le bloc est , respectivement:

 // first word of each block is sum of addresses of prior and next block
 0 + &B   // first word of block A
&A + &C   // first word of block B
&B + 0    // first word of block C

si vous avez accès au bloc A, il vous donne L'adresse de B. Pour obtenir C, vous prenez le" pointeur " en B et soustrayez A, et ainsi de suite. Il fonctionne aussi bien vers l'arrière. Pour exécuter le long de la liste, vous devez garder des pointeurs à deux blocs consécutifs. Bien sûr, vous utiliseriez XOR à la place d'addition / subtration, de sorte que vous n'auriez pas à vous soucier de débordement.

vous pouvez étendre cela à un "Web Lié" si vous voulez avoir du plaisir.

la plupart des gens changeraient deux variables x et y en utilisant une variable temporaire, comme ceci:

tmp = x
x = y
y = tmp

voici un astucieux truc de programmation pour échanger deux valeurs sans avoir besoin d'une température:

x = x xor y
y = x xor y
x = x xor y

plus de détails dans changer deux variables en utilisant XOR

sur la ligne 1 nous combinons x et y (en utilisant XOR) pour obtenir cette" hybride " et nous la stockons en retour dans X. XOR est un excellent moyen de sauver information, parce que vous pouvez l'enlever en faisant un XOR à nouveau.

sur la ligne 2. Nous XOR l'hybride avec y, qui annule toutes les informations y, nous laissant seulement avec x. Nous sauvegardons ce résultat dans y, donc maintenant ils ont changé.

sur la dernière ligne, x a encore la valeur hybride. Nous XORONS encore une fois avec y (maintenant avec la valeur originale de x) pour enlever toutes les traces de x de l'hybride. Cela nous laisse avec y, et l'échange est complet!

l'ordinateur a en fait une variable" temp " implicite qui stocke les résultats intermédiaires avant de les réécrire à un registre. Par exemple, si vous ajoutez 3 à un registre (en pseudocode en langage machine):

ADD 3 A // add 3 to register A

L'ALU (unité logique arithmétique) est en fait ce qui exécute l'instruction 3+A. Elle prend les entrées (3, A) et crée un résultat (3 + a), que le CPU puis les magasins de nouveau dans le registre d'origine de A. Donc, nous avons utilisé L'ALU comme espace de grattage temporaire avant d'avoir la réponse finale.

nous tenons les données implicites temporaires de L'ALU pour acquises, mais elles sont toujours là. De la même manière, L'ALU peut retourner le résultat intermédiaire du XOR dans le cas de x = x xor y, à partir duquel le CPU le stocke dans le registre original de x.

parce que nous ne sommes pas habitués à penser aux pauvres, négligés ALU, les XOR swap semble magique parce qu'il n'a pas de variable temporaire explicite. Certaines machines ont une instruction xchg d'échange en une étape pour échanger deux registres.

@VonC a raison, c'est une astuce mathématique. Imaginez 4 mots de bit et voir si cela aide.

word1 ^= word2;
word2 ^= word1;
word1 ^= word2;


word1    word2
0101     1111
after 1st xor
1010     1111
after 2nd xor
1010     0101
after 3rd xor
1111     0101

il y a essentiellement 3 étapes dans L'approche XOR:

a’ = A XOR b (1)

b’ = a ' XOR b (2)

a" = A ' XOR b’ (3)

comprendre pourquoi cela fonctionne de la première note que:

1. XOR produira un 1 seulement si exactement l'un de ses opérandes est 1, et le autre est zéro;
2. XOR est commutative donc a XOR b = b XOR un;
3. XOR est associatif (a XOR b) XOR c = a XOR b XOR c); et
4. a XOR a = 0 (cela doit être évident d'après la définition de 1 ci-dessus)

Après l'Étape (1), la représentation binaire d'une aura 1 bits seulement dans les positions de bits où un et b ont des parties opposées. Soit (ak=1, bk=0) ou (ak=0, bk=1). Maintenant, quand nous faisons la substitution dans L'Étape (2) nous obtenons:

b’ = (a XOR b) XOR b

= a XOR (b XOR b) parce que XOR est associatif

= a XOR 0 en raison de [4] au-dessus de

= a en raison de la définition de XOR (voir 1 ci-dessus)

maintenant nous pouvons remplacer dans le Pas (3):

a "= (a XOR b) XOR a

= (b XOR a) XOR a parce que XOR est commutatif

= b XOR (a XOR a) parce que XOR est associatif

= B XOR 0 à cause de [4] au-dessus de

= b en raison de la définition de XOR (voir 1 ci-dessus)

plus d'informations ici: nécessaire et suffisant

j'ai réinventé cette roue de façon indépendante il y a plusieurs années sous la forme d'un échange d'entiers en faisant:

a = a + b
b = a - b ( = a + b - b once expanded)
a = a - b ( = a + b - a once expanded).

(ceci est mentionné ci-dessus de façon difficile à lire),

le même raisonnement s'applique aux échanges xor: A ^ b ^ b = A et a ^ b ^ a = a. Comme xor est commutatif, x ^ x = 0 et x ^ 0 = x, c'est assez facile à voir depuis

= a ^ b ^ b
= a ^ 0
= a

et

= a ^ b ^ a 
= a ^ a ^ b 
= 0 ^ b 
= b

Espérons que cette aide. Cette explication a déjà été donnée... mais pas très clairement de l'omi.