Comment fonctionne l'échange de variable XOR?

Question

Quelqu'un peut-il m'expliquer le fonctionnement de 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 depuis 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 ce n'est pas le cas.

À l’époque où nous avions des processeurs simples à cycle unique ou à cycles multiples, il était moins coûteux d’utiliser cette astuce pour éviter des déréférences de mémoire coûteuses ou la perte de registres sur la pile. Cependant, nous avons maintenant des processeurs avec des pipelines massifs. Le pipeline du P4 allait de 20 à 31 (ou plus) étapes dans ses pipelines, où toute dépendance entre la lecture et l'écriture dans un registre pourrait entraîner le blocage complet du processus. Le swap xor a de très lourdes dépendances entre A et B qui n’ont aucune importance, mais bloquent le pipeline dans la pratique. Un pipeline bloqué provoque un chemin de code lent, et si cette permutation se produit dans votre boucle interne, vous vous déplacerez très lentement.

En règle générale, votre compilateur peut déterminer ce que vous voulez vraiment faire lorsque vous effectuez un échange avec une variable temporaire et le compiler en une seule instruction XCHG. L'utilisation de l'échange 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.

Answer 3

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

Disons que vous commencez par 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

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 comprend un peu plus facilement le truc XOR en comprenant que ^ peut être considéré comme + ou - . Juste comme:

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

, donc:

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

Answer 5

La raison pour laquelle cela fonctionne est que XOR ne perd pas d’informations. Vous pouvez faire la même chose avec des additions et des soustractions 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 suit:

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

En passant, il existe un vieux truc pour coder une liste chaînée dans un seul "pointeur". Supposons que vous ayez une liste de blocs de mémoire aux adresses A, B et C. Le premier mot de chaque 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 accéder à C, vous devez utiliser le "pointeur". dans B et soustrayez A, et ainsi de suite. Cela fonctionne aussi bien à l’arrière. Pour parcourir la liste, vous devez conserver les pointeurs sur deux blocs consécutifs. Bien sûr, vous utiliseriez XOR au lieu d’addition / soustraction, de sorte que vous n’ayez pas à vous soucier des débordements.

Vous pouvez également l'étendre à un "site Web lié". si vous voulez vous amuser.

Answer 6

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

tmp = x
x = y
y = tmp

Voici une astuce de programmation intéressante pour échanger deux valeurs sans nécessiter de temp:

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

Plus de détails dans Permutez deux variables en utilisant XOR

  

Sur la ligne 1, nous combinons x et y (en utilisant XOR) pour obtenir cet "hybride" et nous le stockons dans x. XOR est un excellent moyen de sauvegarder des informations, car vous pouvez les supprimer en effectuant à nouveau un XOR.

     

A la ligne 2. Nous avons XOR l’hybride avec y, qui annule toutes les informations y, nous laissant uniquement avec x. Nous enregistrons ce résultat dans y, ils ont donc échangé leurs résultats.

     

Sur la dernière ligne, x a toujours la valeur hybride. Nous le vérifions encore une fois avec y (maintenant avec la valeur originale de x) pour supprimer toutes les traces de x de l’hybride. Cela nous laisse avec y et l’échange est terminé!

  

L’ordinateur a en fait une variable implicite «temp» qui stocke les résultats intermédiaires avant de les réécrire dans 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é arithmétique et logique) exécute en réalité l’instruction 3 + A. Il prend les entrées (3, A) et crée un résultat (3 + A), que la CPU enregistre ensuite dans le registre original de A. Nous avons donc utilisé l’ALU comme espace temporaire de travail avant d’avoir la réponse finale.

     

Nous prenons les données temporaires implicites de l’ALU comme allant de soi, mais elles sont toujours présentes. De la même manière, l’ALU peut renvoyer le résultat intermédiaire de XOR dans le cas de x = x xor y, point auquel la CPU le stocke dans le registre d'origine de x.

     

Comme nous n’avons pas l’habitude de penser à une ALU négligée et négligée, l’échange XOR semble magique, car il n’a pas de variable temporaire explicite. Certaines machines ont une instruction XCHG d'échange en une étape pour permuter deux registres.

Answer 7

@VonC a raison, c'est une astuce mathématique intéressante . Imaginez des mots de 4 bits et voyez si cela vous 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

Answer 8

L’approche XOR comporte essentiellement 3 étapes:

a ’= a XOR b (1)
b ’= a’ XOR b (2)
a ”= a’ XOR b ’(3)

Pour comprendre pourquoi cela fonctionne, notez tout d'abord que:

1. XOR ne produira un 1 que si exactement l'un de ses opérandes est 1 et que l'autre est zéro;
2. XOR est commutatif , donc un XOR b = b XOR a;
3. XOR est associatif , donc (a XOR b) XOR c = a XOR (b XOR c); et
4. a XOR a = 0 (cela devrait être évident dans la définition donnée dans 1 ci-dessus)

Après l’étape (1), la représentation binaire de a n’aura que 1 bits dans les positions de bits où a et b ont des bits opposés. C'est soit (ak = 1, bk = 0) ou (ak = 0, bk = 1). Maintenant, lorsque nous faisons la substitution à l'étape (2), nous obtenons:

b ’= (a XOR b) XOR b
    = a XOR (b XOR b) car XOR est associatif
   = un XOR 0 à cause de [4] ci-dessus
   = a en raison de la définition de XOR (voir 1 ci-dessus)

/ p>

Nous pouvons maintenant substituer à l'étape (3):

a ”= (a XOR b) XOR a

    = (b XOR a) XOR a car XOR est commutatif
    = b XOR (a XOR a) car XOR est associatif
    = b XOR 0 à cause de [4] ci-dessus
    = b en raison de la définition de XOR (voir 1 ci-dessus)

/ p>

Plus d'informations détaillées ici: Nécessaire et suffisant

Answer 9

En remarque, j’ai réinventé cette roue de manière indépendante il ya plusieurs années sous la forme de permutation de nombres 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 d'une manière difficile à lire),

Le même raisonnement s’applique exactement aux échanges xor: a ^ b ^ b = a et a ^ b ^ a = a. Puisque xor est commutatif, x ^ x = 0 et x ^ 0 = x, c'est assez facile à voir car

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

et

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

J'espère que ça aide. Cette explication a déjà été donnée ... mais pas très clairement.