Que signifie XOR (OU exclusif)?

J’essaie de comprendre les opérateurs binarys en C # ou en général, en particulier ^ – exclusif ou .

Par exemple:

Étant donné un tableau d’entiers positifs. Tous les nombres apparaissent un nombre pair de fois, sauf un nombre qui apparaît un nombre de fois impair. Trouvez le nombre dans O (n) temps et espace constant.

Cela peut être fait avec ^ comme suit: Faites XOR bitwise de tous les éléments. Enfin, nous obtenons le nombre qui a des occurrences impaires.

Comment ça marche?

Quand je fais:

int res = 2 ^ 3; res = 1; int res = 2 ^ 5; res = 7; int res = 2 ^ 10; res = 8; 

Qu’est-ce qui se passe réellement? Quelles sont les autres magies? Toute référence que je peux rechercher et en apprendre davantage à leur sujet?

Pour voir comment cela fonctionne, vous devez d’abord écrire les deux opérandes en binary, car les opérations binarys fonctionnent sur des bits individuels.

Ensuite, vous pouvez appliquer la table de vérité pour votre opérateur particulier. Il agit sur chaque paire de bits ayant la même position dans les deux opérandes (la même valeur de position). Donc, le bit le plus à gauche (MSB) de A est combiné avec le MSB de B pour produire le MSB du résultat.

Exemple: 2^10 :

  0010 2 XOR 1010 8 + 2 ---- 1 xor(0, 1) 0 xor(0, 0) 0 xor(1, 1) 0 xor(0, 0) ---- = 1000 8 

Et le résultat est 8.

Je sais que c’est un article plutôt ancien, mais je voulais simplifier la réponse car je suis tombé dessus en cherchant autre chose.
XOR (OU exclusif ou / ou), peut être traduit simplement en tant que activé / désactivé.
Qui exclura ou inclura les bits spécifiés.

En utilisant 4 bits (1111), nous obtenons 16 résultats possibles de 0 à 15:

  decimal | binary | expanded 0 | 0000 | 1 | 0001 | 2 | 0010 | 3 | 0011 | (1+2) 4 | 0100 | 5 | 0101 | (1+4) 6 | 0110 | (2+4) 7 | 0111 | (1+2+4) 8 | 1000 | 9 | 1001 | (1+8) 10 | 1010 | (2+8) 11 | 1011 | (1+2+8) 12 | 1100 | (4+8) 13 | 1101 | (1+4+8) 14 | 1110 | (2+4+8) 15 | 1111 | (1+2+4+8) 

La valeur décimale à gauche de la valeur binary correspond à la valeur numérique utilisée dans XOR et les autres opérations au niveau du bit.

Par exemple: 0011 sont les bits 1 et 2, laissant les bits 4 et 8 éteints. Qui est représenté par la valeur décimale de 3 pour indiquer les bits activés et affichés sous la forme 1+2 .


En ce qui concerne ce qui se passe avec la logique derrière XOR, voici quelques exemples
De la poste d’origine

2 ^ 3 = 1

  • 2 est membre de 1 + 2 (3) retirer 2 = 1

2 ^ 5 = 7

  • 2 n’est pas membre de 1 + 4 (5) append 2 = 1 + 2 + 4 (7)

2 ^ 10 = 8

  • 2 est membre de 2 + 8 (10) enlève 2 = 8

Autres exemples

1 ^ 3 = 2

  • 1 est membre de 1 + 2 (3) retirer 1 = 2

4 ^ 5 = 1

  • 4 est membre de 1 + 4 (5) enlève 4 = 1

4 ^ 4 = 0

  • 4 est un membre de lui-même supprimer 4 = 0

1 ^ 2 ^ 3 = 0
Logique: ((1 ^ 2) ^ (1 + 2))

  • (1 ^ 2) 1 n’est pas membre de 2 append 2 = 1 + 2 (3)
  • (3 ^ 3) 1 et 2 sont membres de 1 + 2 (3) retirer 1 + 2 (3) = 0

1 ^ 1 ^ 0 ^ 1 = 1
Logique: (((1 ^ 1) ^ 0) ^ 1)

  • (1 ^ 1) 1 est membre de 1 remove 1 = 0
  • (0 ^ 0) 0 est membre de 0 remove 0 = 0
  • (0 ^ 1) 0 n’est pas membre de 1 add 1 = 1

1 ^ 8 ^ 4 = 13
Logique: ((1 ^ 8) ^ 4)

  • (1 ^ 8) 1 n’est pas membre de 8 append 1 = 1 + 8 (9)
  • (9 ^ 4) 1 et 8 ne sont pas membres de 4 append 1 + 8 = 1 + 4 + 8 (13)

4 ^ 13 ^ 10 = 3
Logique: ((4 ^ (1 + 4 + 8)) ^ (2 + 8))

  • (4 ^ 13) 4 est membre de 1 + 4 + 8 (13) enlève 4 = 1 + 8 (9)
  • (9 ^ 10) 8 est membre de 2 + 8 (10) enlève 8 = 2
    • 1 n’est pas membre de 2 +8 (10) append 1 = 1 + 2 (3)

4 ^ 10 ^ 13 = 3
Logique: ((4 ^ (2 + 8)) ^ (1 + 4 + 8))

  • (4 ^ 10) 4 n’est pas membre de 2 + 8 (10) append 4 = 2 + 4 + 8 (14)
  • (14 ^ 13) 4 et 8 sont membres de 1 + 4 + 8 (13) retirent 4 + 8 = 1
    • 2 n’est pas membre de 1 + 4 + 8 (13) append 2 = 1 + 2 (3)

L’autre façon de montrer ceci est d’utiliser l’algèbre de XOR; vous n’avez pas besoin de savoir quoi que ce soit sur les bits individuels.

Pour tout nombre x, y, z:

XOR est commutatif: x ^ y == y ^ x

XOR est associatif: x ^ (y ^ z) == (x ^ y) ^ z

L’identité est 0: x ^ 0 == x

Chaque élément est sa propre inverse: x ^ x == 0

Compte tenu de cela, il est facile de prouver le résultat déclaré. Considérons une séquence:

a ^ b ^ c ^ d ...

Puisque XOR est commutatif et associatif, l’ordre n’a pas d’importance. Donc, sortingez les éléments.

Maintenant, tous les éléments identiques adjacents x ^ x peuvent être remplacés par 0 (propriété d’auto-inverse). Et tout 0 peut être supprimé (parce que c’est l’identité).

Répétez aussi longtemps que possible. Tout nombre qui apparaît un nombre pair de fois a un nombre entier de paires, donc ils deviennent tous 0 et disparaissent.

Finalement, il ne vous rest plus qu’un élément, celui qui apparaît un nombre de fois impair. Chaque fois qu’il apparaît deux fois, ces deux disparaissent. Finalement, il ne vous rest qu’une occurrence.

[mettre à jour]

Notez que cette preuve nécessite uniquement certaines hypothèses sur l’opération. Spécifiquement, supposons un ensemble S avec un opérateur . a les propriétés suivantes:

Assocativity: x . (y . z) = (x . y) . z x . (y . z) = (x . y) . z x . (y . z) = (x . y) . z pour tout x , y et z dans S.

Identité: Il existe un seul élément e tel que e . x = x . e = x e . x = x . e = x e . x = x . e = x pour tout x dans S.

Fermeture: Pour tout x et y dans S, x . y x . y est aussi en S.

Auto-inverse: Pour tout x dans S, x . x = e x . x = e

En fin de compte, il n’est pas nécessaire de supposer la commutativité. nous pouvons le prouver:

 (x . y) . (x . y) = e (by self-inverse) x . (y . x) . y = e (by associativity) x . x . (y . x) . y . y = x . e . y (multiply both sides by x on the left and y on the right) y . x = x . y (because x . x = y . y = e and the e's go away) 

Maintenant, j’ai dit que “vous n’avez rien besoin de savoir sur les bits individuels”. Je pensais que tout groupe satisfaisant à ces propriétés serait suffisant et qu’un tel groupe ne doit pas nécessairement être isomorphe aux nombres entiers sous XOR.

Mais @Steve Jessup m’a prouvé le contraire dans les commentaires. Si vous définissez la multiplication scalaire par {0,1} comme:

 0 * x = 0 1 * x = x 

… alors cette structure satisfait à tous les axiomes d’un espace vectoriel sur les entiers mod 2.

Ainsi, une telle structure est isomorphe à un ensemble de vecteurs de bits sous XOR au niveau des composants.

Les opérateurs binarys traitent les bits dans une valeur entière comme un tout petit tableau de bits . Chacun de ces bits est comme une minuscule valeur bool . Lorsque vous utilisez l’exclusivité ou l’opérateur au niveau du bit, une interprétation de l’opérateur est:

  • pour chaque bit de la première valeur, basculer le bit si le bit correspondant dans la deuxième valeur est défini

L’effet net est qu’un seul bit commence false et que si le nombre total de “bascules” est pair, il sera toujours false à la fin. Si le nombre total de “bascules” est impair, ce sera true à la fin.

Il suffit de penser “minuscule tableau de valeurs booléennes” et cela commencera à avoir un sens.

La définition de l’opérateur XOR (OR exclusif), sur bits, est la suivante:

 0 XOR 0 = 0 0 XOR 1 = 1 1 XOR 0 = 1 1 XOR 1 = 0 

Une des façons de l’imaginer est de dire que le “1” sur le côté droit change le bit du côté gauche et que le 0 sur le côté droit ne change pas le bit du côté gauche. Cependant, XOR est commutatif, donc la même chose est vraie si les côtés sont inversés. Comme n’importe quel nombre peut être représenté sous forme binary, deux nombres quelconques peuvent être XOR-ed ensemble.

Pour prouver qu’il est commutatif, vous pouvez simplement regarder sa définition et voir que pour chaque combinaison de bits de chaque côté, le résultat est le même si les côtés sont modifiés. Pour prouver qu’il est associatif, vous pouvez simplement parcourir toutes les combinaisons possibles de 3 bits XOR-ed les uns aux autres, et le résultat restra le même quel que soit l’ordre.

Maintenant, comme nous l’avons prouvé ci-dessus, voyons ce qui se passe si nous XOR le même nombre sur lui-même. Comme l’opération fonctionne sur des bits individuels, nous pouvons le tester sur deux nombres seulement: 0 et 1.

 0 XOR 0 = 0 1 XOR 1 = 0 

Donc, si vous XOR un nombre sur lui-même, vous obtenez toujours 0 (croyez-le ou non, mais cette propriété de XOR a été utilisée par les compilateurs, quand un 0 doit être chargé dans un registre CPU. que de pousser explicitement 0 dans un registre, le compilateur ne produira que du code assembleur sur XOR un registre sur lui-même).

Maintenant, si X XOR X vaut 0 et que XOR est associatif, vous devez déterminer quel nombre n’a pas été répété dans une séquence de nombres où tous les autres nombres ont été répétés deux fois (ou tout autre nombre impair de fois). Si nous avions les nombres répétés ensemble, ils seront XOR à 0. Tout ce qui est XOR-ed avec 0 restra lui-même. Donc, à partir de XOR -ing une telle séquence, vous finirez par avoir un nombre qui ne se répète pas (ou répète un nombre pair de fois).

Cela a beaucoup d’échantillons de diverses fonctionnalités effectuées par bit-fiddling. Certains peuvent être assez complexes, alors méfiez-vous.

Ce que vous devez faire pour comprendre les opérations sur les bits est au moins ceci:

  • les données d’entrée, sous forme binary
  • une table de vérité qui vous dit comment “mélanger” les entrées pour former le résultat

Pour XOR, la table de vérité est simple:

 1^1 = 0 1^0 = 1 0^1 = 1 0^0 = 0 

Pour obtenir le bit n dans le résultat, vous appliquez la règle aux bits n dans les première et deuxième entrées.

Si vous essayez de calculer 1^1^0^1 ou toute autre combinaison, vous découvrirez que le résultat est 1 s’il y a un nombre impair de 1 et 0 sinon. Vous découvrirez également que tout nombre XOR avec lui-même est égal à 0 et que l’ordre dans lequel vous effectuez les calculs n’a pas d’importance, par exemple 1^1^(0^1) = 1^(1^0)^1 .

Cela signifie que lorsque vous faites XOR tous les nombres de votre liste, ceux qui sont en double (ou présentent un nombre pair de fois) seront XOR à 0 et vous ne restrez que celui qui est présent un nombre impair de fois.

Ceci est basé sur le simple fait que XOR d’un nombre avec lui-même donne Zéro.

et XOR d’un nombre avec 0 donne le nombre lui-même.

Donc, si nous avons un tableau = {5,8,12,5,12}.

5 se produit 2 fois. 8 se produit 1 fois. 12 se produit 2 fois.

Nous devons trouver le nombre qui se produit nombre impair de fois. Clairement, 8 est le nombre.

Nous commençons avec res = 0 et XOR avec tous les éléments du tableau.

int res=0; for(int i:array) res = res ^ i;

  1st Iteration: res = 0^5 = 5 2nd Iteration: res = 5^8 3rd Iteration: res = 5^8^12 4th Iteration: res = 5^8^12^5 = 0^8^12 = 8^12 5th Iteration: res = 8^12^12 = 8^0 = 8