Comment fonctionne l'échange de variable XOR?

Question

Quelqu'un peut-il m'expliquer comment fonctionne l'échange XOR de deux variables sans variable temporaire?

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

Je comprends CE QUE CELA FAIT, mais quelqu'un peut-il me guider dans la logique de son fonctionnement?

Answer 1

Vous pouvez voir comment cela fonctionne en effectuant la substitution:

 x1 = x0 xor y0
y2 = x1 xor y0
x2 = x1 xor y2
 

En remplaçant,

 x1 = x0 xor y0
y2 = (x0 xor y0) xor y0
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0)
 

Parce que xor est totalement associatif et commutatif:

 y2 = x0 xor (y0 xor y0)
x2 = (x0 xor x0) xor (y0 xor y0) xor y0
 

Depuis x xor x == 0 pour tout x,

 y2 = x0 xor 0
x2 = 0 xor 0 xor y0
 

Et puisque x xor 0 == x pour tout x,

 y2 = x0
x2 = y0
 

Et l'échange est terminé.

Answer 2

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

Retour dans la journée quand nous avons eu des simple à cycle unique ou multi-cycle Cpu, il était moins coûteux d'utiliser cette astuce pour éviter de coûteux mémoire déréférence ou de renverser les registres de la pile. Cependant, nous avons maintenant des Processeurs avec une massive des pipelines de la place. La P4 du pipeline variait de 20 à 31 (ou presque) les étapes de l'exploitation de leurs pipelines, où toute dépendance entre la lecture et l'écriture dans un registre pourrait provoquer le tout décrochage. Le xor swap a quelques très fortes dépendances entre A et B, qui n'a pas vraiment d'importance, mais à tous les caler le pipeline dans la pratique. Un blocage de pipeline provoque une lente chemin de code, et si ce swap est dans votre boucle, vous allez être en se déplaçant très lentement.

Dans la pratique, le compilateur peut déterminer ce que vous voulez vraiment faire, quand tu fais un swap avec une température variable et peut compiler en une seule instruction XCHG. À l'aide de la xor swap rend beaucoup plus difficile pour le compilateur de deviner vos intentions et, par conséquent, beaucoup moins susceptibles d'optimiser correctement. Pour ne pas mentionner le code de maintenance, etc.

Answer 3

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 machine hypothétique à 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 inversée 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!
 

Answer 4

En voici un qui devrait être un peu plus facile à comprendre:

 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 un peu plus facilement l’astuce XOR en comprenant que ^ peut être considéré comme + ou - . Tout comme:

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

, alors:

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

Answer 5

La plupart des gens permuter deux variables x et y à l'aide d'une variable temporaire, comme ceci:

tmp = x
x = y
y = tmp

Voici un joli programmation astuce pour échanger deux valeurs sans avoir besoin d'un temp:

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

Plus de détails dans Permuter deux variables à l'aide de XOR

Sur la ligne 1, nous combinons x et y (en utilisant XOR) pour bénéficier de cet "hybride" et nous l'enregistrons de retour dans x. XOR est une excellente façon d'économiser de l'information, parce que vous pouvez le supprimer en faisant un XOR de nouveau.

Sur la ligne 2. Nous XOR l'hybride avec y, qui annule tous les y des informations, nous laissant seuls avec x. Nous sauver ce résultat dans y, alors maintenant, ils ont échangé.

Sur la dernière ligne, x a encore de l'hybride valeur. Nous XOR encore avec y (avec x la valeur de l'achat) pour supprimer toutes les traces de x de l'hybride. Ce qui nous laisse avec y, et le swap est terminé!

---

L'ordinateur dispose d'un implicite "temp" de la variable qui stocke les résultats intermédiaires avant d'écrire de nouveau à un registre. Par exemple, si vous ajoutez 3 à un registre (en langage machine) pseudo-code):

ADD 3 A // add 3 to register A

L'ALU (Unité Arithmétique et Logique) est en fait ce qu'exécute l'instruction 3+R. Il faut entrées (3,A) et crée un résultat (3 + A), le PROCESSEUR stocke ensuite de retour dans Un original du registre. Ainsi, nous avons utilisé l'ALU comme temporaire de l'espace de travail avant d'avoir la réponse finale.

Nous prenons l'ALU implicite de données temporaires pour acquis, mais il est toujours là. De manière similaire, l'ALU peut retourner le résultat intermédiaire de la XOR dans le cas de x = x xor y, à quel point le PROCESSEUR stocke dans x de caisse original.

Parce que nous ne sommes pas habitués à réfléchir sur les pauvres, négligées ALU, le XOR swap semble magique car il n'a pas explicitement la variable temporaire. Certaines machines ont un 1-l'étape d'échange d'instruction XCHG pour permuter les deux registres.