Le XOR
|
26-10-2014, 02h35
(Modification du message : 26-10-2014, 15h15 par Kiwazaru.)
Message : #1
|
|
Kiwazaru
Padawan d'un super escargot Messages : 284 Sujets : 26 Points: 139 Inscription : Mar 2012 |
Le XOR
Dans cet article, j'insisterais fortement sur les mots associativité et commutativité car ce sont deux notions très importante qui rentrent tous deux en compte dans la particularité du XOR; Il est possible que l'article comprenne des erreurs d’inattention ou tout simplement une erreur de compréhension, merci de le faire remarquer pour que cela soit corrigé.
Je vais essayer de détailler les particularités du XOR, et pour cela on va commencer par un exemple: Code : Soit un ensemble S ordonnée ou désordonnée de couples (x, x) avec x appartenant à N* et v un entier valant 0, alors si on effectue un XOR sur v pour chaque valeurs contenues dans S on obtient v la valeur qui ne présente aucun couple dans la liste (S) si elle est supérieure à 0 si et seulement si la liste ne présente qu'un seul cas de non-couple. Code PSEUDO :
En Python cela donne donc: Code PYTHON :
Output: Code : Le nombre qui n'a pas de copain est: 15 Pour bien apréhender la suite, il faut bien retenir que le XOR n'est pas une opération sur un ensemble de bit, mais bien bit-à-bit alors quelques rappels sur le XOR s'imposent: Code : A | B | A ⊕ B Code : A ⊕ A = 0 ( 111 ⊕ 111 -> 1 ⊕ 1 ; 1 ⊕ 1 ; 1 ⊕ 1 -> 000 -> 0 ) Pour comprendre l'approche mathématique du problème, il faut bien avoir en tête le fait que l'ensemble doit absolument contenir un et un seul non-couple. Ainsi on peut définir la propriété suivante: Code : Soit S un ensemble dit contenant des couples, alors si la taille de cet ensemble est pair l'ensemble ne contient que des couples ou contient 2 ou plus non-couples. Preuve: Code : S = [ 20, 30, 20, 30 ] Le XOR a des propriétés particulières ce qui lui permet d'être particulièrement intéressant. En effet il est mathématiquement entièrement commutatif et associatif. Commtuativité: Code : A ⊕ B = B ⊕ A Associativité: Code : A ⊕ ( B ⊕ C ) <=> ( A ⊕ B ) ⊕ C A partir d'ici on commence à se faire une idée du pourquoi du comment l'algorithme fonctionne et pourquoi il a ces propriétés. Prenons l'exemple ci-dessous: Code : S = [ A, A, B, B, C ] Ainsi arrivé à la dernière valeur, nous allons simplement effectuer: 0 xor C, et on sait que 0 xor C = C, on retrouve ainsi notre non-couple à la fin de notre algorithme. Prenons maintenant ce second exemple: Code : S = [ A, B, A, B, C ] On remarque que A xor B ne nous donnera pas la même valeur que A auquel le résultat sera XOR ensuite, mais c'est sans compter le fait que le XOR soit associatif et commutatif. En effet, l'opération: (A xor B) xor A peut s'écrire A xor (B xor A) ou ecore plus simplement de part sa commutativité: (A xor A) xor B. Ainsi la logique est visible => A xor A = 0 et 0 xor B = B. Ainsi A xor B xor A = B et ce résultat est ensuite XOR par B, B xor B = 0 et 0 xor C = C. On retombe bien sur nos patte et nous retrouvons bien notre non-couple C. Prenons maintenant un cas plus concret: Code : S = [ A, B, D, C, D, B, A ] De tête le calcul est moins simple, mais il faut se rappeler que le XOR est commutatif et associatif, c'est à dire que peut importe l'ordre des bits, le résultat sera toujours le même. On peut ainsi représenter le calcul ainsi: Code : Algorithme => ( A ⊕ A ) ⊕ ( B ⊕ B ) ⊕ ( D ⊕ D ) ⊕ C Ainsi on se retrouve avec une séquence de calcul: A xor A = 0; B xor B = 0; D xor D = 0; 0 xor C = C. On retombe encore une fois sur nos pattes, ce qui explique que l'algorithme fonctionne même dans une liste totalement désordonnée. Mais alors que se passe t-il si l'algorithme est utilisée sur un ensemble mal formée ? Il y a 2 cas: - Premier cas: L'ensemble ne contient que des couples. Code : S = [ A, B, A, B ] Code : A ⊕ A ⊕ B ⊕ B... ⊕ N ⊕ N <=> 0 ⊕ 0... ⊕ 0 - Second cas: L'ensemble comporte 2 ou plus non-couples. Code : S = [ A, B, C, A, X, B, C, Z, Y ] On replace correctement nos bits afin de retrouver une séquence de calcul valant: 0 xor 0 xor 0... puis nous mettons à la fin nos non-couples. Soit NC l'ensemble des non-couples de l'ensemble S de taille supérieur à 1, alors on se retrouve avec la séquence de calcul suivante: 0 xor 0... xor NC[0]... xor NC[n]. Finalement cela revient à dire que pour tout ensemble S, si cet ensemble contient plus d'un non-couple le résultat sera équivalent au résultat du XOR de chacun de ceux-ci entre eux. L'associativité et la commutativité du XOR peut aussi être aperçu dans l'opération qui permute deux variable. Soient x, y deux variable alors: Code : x = x ⊕ y Développons maintenant cette suite de calcul, à chaque calcul x et y changent de valeur autrement dit: Code : x = x ⊕ y On peut donc en déduire que cette opération de swap est totalement reversible. Mais alors pourquoi est-ce que le XOR est associatif et commutatif, et pourquoi est-ce que cela lui donne une telle particularité? Et bien en fait, il faut savoir qu'il n'y a pas seulement le XOR qui est entièrement associatif et commutatif, l'opération AND et OR le sont tous deux aussi. La spécificité du XOR réside dans sa table de vérité mêlée à la commutativité et à l'associativité. Ci-dessous, la preuve de l'associativité et la commutativité de chacun de ces opérateurs (AND/OR/XOR): Code : AND: La ligne importante de la table de vérité est la suivante: 1 ⊕ 1 = 0; C'est grâce à cette propriété logique du XOR qu'il est possible de faire tant de chose avec. Effectivement, on a vu dans nos calcul que l'associativité nous permettait d'ordonner nos calculs, mais ceci ne serait pas utile dans notre algorithme si on ne pouvais pas obtenir un calcul donnant un résultat nul ensuite (0). C'est grâce à cela que nous pouvons ensuite obtenir un calcul équivalent à: 0 xor A = A, qui nous permet par exemple de ressortir le non-couple d'un ensemble de couples. C'est pour cela qu'il est important de connaître les deux propriétés du XOR rappelées ci-dessus ( A xor A = 0; 0 xor B = B ). Plus de précisions: La table de vérité du XOR nous permet d'annuler deux valeurs identiques, par exemple A et A puisque la table indique que pour tout bit à 1 XORée à un autre bit à 1, le résultat est 0, et que pour tout bit 0 XORée à un autre bit à 0 le résultat est 0. Ainsi on obtient l'annulation totale d'une suite de bit XORée elle-même. Trace de l'opération A xor A avec A = 5: Code : 101 ⊕ 101 La table de vérité nous permet aussi d'obtenir A si A est XORée par 0 grâce au fait que 0 xor 1 = 1 et 1 xor 0 = 1, car dans le cas contraire l'utilité du XOR perdrait tout son sens. Ainsi, on peut obtenir une suite de XOR valant 0 XORée elle-même par une valeur A qui retourne A. Trace de l'opération 0 xor A = A avec A = 5: Code : 000 ⊕ 101 L'opération OR vérifie la même propriété que 0 xor A = A mais pas celle de A xor A = 0, tandis que AND ne vérifie aucune des deux propriétés du XOR. Code : Propriété: A xor A = 0 Pour finir, nous allons démontrer une astuce connue avec le XOR: Code : plaintext ⊕ key = ciphertext Si vous voulez vérifier que vous avez bien compris je vous laisse démontrer ça tout seul, je met la solution en spoiler. [spoiler] Code : A ⊕ B = C
Toucher au Kernel, c'est un peut comme se shooter au LSD, on pense pouvoir tout faire mais ça finit souvent mal.
|
|
26-10-2014, 20h00
Message : #2
|
|
supersnail
Éleveur d'ornithorynques Messages : 1,609 Sujets : 71 Points: 465 Inscription : Jan 2012 |
RE: Le XOR
Sympa ton petit post, cependant quelques petites remarques:
Sinon, pour rajouter quelques précisions, on peut dire aussi que l'opérateur XOR est l'addition modulo 2 sur les entiers (qui forme un groupe additif qu'on note Z/2Z d'élément neutre 0) si on veut avoir une vision algébrique de la chose et pas trop s'enquiquinner avec des tables de vérité :o)).
Mon blog
Code : push esp ; dec eax ; inc ebp ; and [edi+0x41],al ; dec ebp ; inc ebp "VIM est merveilleux" © supersnail |
|
26-10-2014, 21h38
(Modification du message : 26-10-2014, 21h38 par b0fh.)
Message : #3
|
|
b0fh
Membre actif Messages : 210 Sujets : 17 Points: 309 Inscription : Jul 2012 |
RE: Le XOR
Quelques remarques sur le langage mathématique:
Citation :Soit un ensemble S ordonnée ou désordonnée de couples (x, x) avec x appartenant à N* A ce stade, on s'imagine un ensemble Code : S = { (1,1), (2,2), (4,4), (8,8), ... } Code : S = { 1, 1, 2, 2, 4, 4, 8, 8, ... } Citation : et v un entier valant 0 Si v vaut 0, on ne l'appelle pas v, on l'appelle 0 ! Citation :alors si on effectue un XOR sur v pour chaque valeurs contenues dans S on obtient v On comprend ça comme: Code : { x XOR v | x ∈ S } = {v} Ce qui n'a aucun sens, Citation :la valeur qui ne présente aucun couple dans la liste (S) si elle est supérieure à 0 si et seulement si la liste ne présente qu'un seul cas de non-couple. Aaaah, S est une liste, pas un ensemble. Mais la liste contient des couples, pas des valeurs, et pourquoi parle-on soudainement de non-couples ? La formulation correcte du problème serait: Citation :Soit S un multiensemble supporté par N*, dans lequel il existe exactement un élément x de multiplicité impaire. Soit v le produit des éléments de S par l'opération XOR; alors v = x. Enfin, a propos des itérateurs. On n'écrit pas: Code PYTHON :
for x in range(len(S)): on écrit: Code PYTHON :
for s in S: (Et par convention on réserve les majuscules pour les types de classe) |
|
« Sujet précédent | Sujet suivant »
|
Utilisateur(s) parcourant ce sujet : 2 visiteur(s)