XOR

 (chiark.greenend.org.uk)
1 points par GN⁺ 2025-02-19 | 1 commentaires | Partager sur WhatsApp
  • Le XOR est une opération qui vaut 1 lorsque deux bits sont différents ; on peut la comprendre comme un lien entre l’OR exclusif, l’inégalité, l’inversion conditionnelle et l’addition/soustraction modulo 2 en une seule opération
  • Le XOR bit à bit appliqué aux entiers traite chaque position indépendamment, met en évidence les différences bit par bit, fonctionne comme une addition binaire sans retenue et conserve les propriétés de commutativité, d’associativité, d’élément neutre 0 et d’auto-inversion
  • En cryptographie, il sert à combiner un texte en clair avec un flux de clés ; autrefois, dans les graphismes en pixels, il permettait d’effacer une image en la redessinant à l’identique afin de réduire la charge mémoire et CPU
  • Les propriétés du XOR sont exploitées directement dans des calculs qui créent une différence puis l’annulent, comme l’identité du demi-additionneur, l’échange de bits, le swap XOR en trois étapes et la condition de victoire au jeu de Nim
  • Il se prolonge jusqu’à la différence symétrique des ensembles, aux groupes d’exposant 2, au nim-sum, à l’algèbre linéaire et aux polynômes sur GF(2), avec des applications à la détection/correction d’erreurs et à la cryptographie comme les codes de Hamming, le CRC, AES, GCM et Classic McEliece

Sens fondamental du XOR

  • Le XOR est une opération booléenne avec deux bits d’entrée et un bit de sortie, dont la table de vérité est 00→0, 01→1, 10→1, 11→0
  • Vu comme un “exclusive OR”, il vaut 1 lorsque l’un des deux inputs seulement est vrai, et 0 s’ils sont tous deux vrais
  • Vu comme “not equals”, a XOR b est équivalent à a ≠ b et produit donc 1 lorsque deux valeurs booléennes sont différentes
  • Vu comme une inversion conditionnelle, si a=0 alors b reste inchangé, et si a=1 alors b est inversé
    • Pour la même raison, on peut aussi interpréter b comme l’entrée de contrôle qui inverse a
  • Du point de vue de la parité, il indique si le nombre de 1 dans les entrées est impair
    • Avec deux bits, il est identique à a+b mod 2
    • Il est aussi identique à a-b mod 2
    • En faisant le XOR de plusieurs valeurs, on peut savoir si le nombre total de 1 dans l’ensemble des entrées est pair ou impair

Propriétés algébriques du XOR

  • Le XOR satisfait la commutativité et l’associativité
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • Dans une longue liste de XOR, ni l’ordre ni le groupement n’influencent le résultat
  • 0 est l’élément neutre du XOR
    • a XOR 0 = 0 XOR a = a
    • Dans une longue liste de XOR, on peut supprimer les 0
  • Chaque valeur est son propre inverse
    • a XOR a = 0
    • Lorsqu’une même variable apparaît deux fois, on peut supprimer ces deux termes ensemble
    • On peut aussi éliminer un terme déjà mélangé en lui appliquant à nouveau un XOR, comme dans (a XOR b) XOR b = a

XOR bit à bit sur les entiers

  • Le XOR bit à bit sur des entiers consiste à écrire deux entiers en binaire puis à appliquer le XOR indépendamment à chaque position
  • Les propriétés du XOR sur un bit s’appliquent telles quelles aux entiers
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • a XOR 0 = a
    • a XOR a = 0
  • Le XOR bit à bit met en évidence les différences bit par bit entre deux entiers
    • Si a=b, alors a XOR b = 0
    • Si a≠b, alors au moins un bit diffère, donc a XOR b ≠ 0
    • Les bits à 1 dans le résultat indiquent les positions où les deux entrées diffèrent
  • On peut aussi voir le XOR bit à bit comme un inverseur conditionnel de bits
    • Il inverse les bits de données uniquement aux positions où la valeur de contrôle contient des bits à 1
    • En ASCII et dans certains encodages dérivés, les lettres latines majuscules et minuscules ne diffèrent que d’un bit ; faire un XOR de la valeur du caractère avec 32 permet donc de changer la casse
    • Cette règle ne s’applique pas à tous les caractères Unicode, et beaucoup n’ont pas de notion de casse ou ne suivent pas cette structure
  • Le XOR bit à bit est équivalent à une addition binaire sans retenue
    • À chaque position, on effectue seulement une addition modulo 2 sans propager de retenue au bit suivant

Le XOR en cryptographie

  • En cryptographie, on peut produire un flux de clés de la même longueur que le texte en clair, puis le combiner avec les octets ou mots du texte en clair pour produire le texte chiffré
  • Le XOR est généralement utilisé pour cette étape de combinaison
    • Le destinataire peut refaire le XOR avec le même flux de clés pour retrouver le texte en clair d’origine
    • Le fait que l’émetteur et le destinataire utilisent la même opération apporte aussi une légère commodité
  • La manière de produire le flux de clés lui-même peut être plus complexe
    • Le one-time pad utilise des données véritablement aléatoires de la taille complète du message ; il est incassable, mais très peu pratique pour la plupart des usages
    • En pratique, on utilise le plus souvent un chiffrement par flot ou un chiffrement par blocs en mode compteur pour générer un flux de clés de la longueur voulue à partir d’une petite clé
  • Cette approche peut fournir la confidentialité si le flux de clés est de bonne qualité, mais elle ne fournit pas l’intégrité qui permet de détecter la modification d’un message
    • La protection de l’intégrité est un problème distinct
    • Oublier l’intégrité est une erreur fréquente dans les conceptions cryptographiques débutantes, et cela conduit aussi à de mauvais résultats dans des schémas plus complexes
  • En matériel, le XOR est plus simple qu’une addition
    • Une addition exige une propagation des retenues entre les bits, ce qui coûte davantage en surface de puce et en temps
    • Le XOR n’ayant pas de retenue, il est moins coûteux dans du matériel spécialisé

Dessin en XOR et graphismes en pixels

  • Dans les micro-ordinateurs domestiques des années 1980, le nombre de bits par pixel et la RAM étaient limités, ce qui rendait difficile le stockage de deux copies complètes de l’écran
  • Si l’on dessine un objet mobile avec un XOR, il suffit de redessiner le même objet pour restaurer l’écran d’origine
    • En faisant le XOR entre une valeur de pixel S et le pixel M de l’objet mobile, on obtient C, puis on refait plus tard le XOR avec le même M pour retrouver S
  • Sur des écrans où plusieurs pixels sont packed dans un octet ou organisés en bit planes, la composition basée sur l’addition est délicate
    • Avec une addition classique, la retenue d’un pixel peut se propager au pixel suivant
    • Le XOR n’a aucune retenue, ce qui évite totalement ce problème
  • Si l’on trace des lignes avec un XOR, les pixels d’intersection de deux lignes sont inversés deux fois et reviennent donc à la couleur de fond, ce qui peut donner l’impression d’un petit défaut visuel
    • Ce défaut était accepté en échange du fait qu’effacer une ligne n’abîmait pas les autres
  • Le dessin en XOR était aussi pratique pour des animations simples
    • Il suffisait de tracer une nouvelle ligne et de redessiner l’ancienne pour l’effacer afin d’obtenir l’image suivante
    • Inutile de redessiner tous les pixels de l’écran ou toutes les lignes en cours, ce qui réduisait l’usage mémoire et CPU
    • Cette technique a notamment été utilisée pour les lignes mobiles du jeu Qix en 1981, ainsi que pour les contours de déplacement de fenêtres dans les premiers GUI

Identité du demi-additionneur

  • Dans une addition sur un bit, le bit de poids faible de a+b est a XOR b, et le bit de poids fort est a AND b
  • La même relation vaut aussi pour les opérations bit à bit sur les entiers
    • a + b = (a XOR b) + 2 × (a AND b)
    • a XOR b est la somme sans retenue, et a AND b contient les bits de retenue qui auraient dû être générés à chaque position
  • On peut voir cette relation comme l’identité du demi-additionneur
    • Un demi-additionneur matériel produit la retenue et le bit faible d’une addition sur deux bits avec des portes AND et XOR
    • Cela ne signifie pas qu’on reconstruit toute l’addition d’entiers uniquement avec des opérations simples ; le + du membre de droite termine bien la propagation des retenues
  • Cette identité peut servir à calculer la moyenne de deux entiers sans overflow
    • Si l’on fait simplement a+b puis un décalage à droite, on peut perdre le bit de poids fort d’une somme sur 33 bits
    • Sur des CPU sans carry flag, ou où des instructions comme RRX/RCR sont absentes ou peu pratiques, une forme comme (a XOR b) >> 1 + (a AND b) peut servir d’alternative
    • Par exemple, MIPS, RISC-V et DEC Alpha n’ont pas de carry flag, et le premier Arm Thumb ne disposait pas de RRX
  • Sur un CPU sans instruction XOR, on peut inverser cette identité pour fabriquer un XOR
    • a XOR b = (a + b) − 2 × (a AND b)
    • Les CPU Data General des années 1970 disposaient d’un AND mais pas d’un XOR bit à bit

Échange de bits et de valeurs

  • Le problème consistant à échanger deux bits se ramène au fait que, s’ils sont égaux, aucune opération n’est nécessaire, et que, s’ils diffèrent, il suffit d’inverser les deux bits
  • Avec un XOR et des décalages, on peut détecter si deux bits diffèrent puis inverser les deux positions si nécessaire
    • diff_all = input XOR (input >> distance) calcule les différences entre des paires de bits séparées d’une distance fixe
    • Un AND permet ensuite de ne conserver que les positions qui nous intéressent
    • On recopie ensuite les différences sélectionnées vers l’autre position, puis on applique un XOR à l’entrée pour n’inverser les deux bits que si nécessaire
  • La même méthode peut servir à échanger en une seule fois plusieurs paires de bits séparées de la même distance
    • On utilise alors un masque contenant plusieurs bits au lieu d’un masque à un seul bit
    • Un réseau de Beneš peut représenter une permutation arbitraire en échangeant de nombreuses paires à même distance sur plusieurs étapes
  • Il existe aussi le swap XOR en trois étapes pour échanger deux valeurs entières
    • a = a XOR b
    • b = b XOR a
    • a = a XOR b
    • Les deux valeurs sont alors échangées sans variable temporaire
  • Ce swap XOR en trois étapes présente un problème d’aliasing
    • Il fonctionne si l’on échange deux variables distinctes
    • Si deux noms pointent vers le même emplacement mémoire, comme lorsqu’on échange un élément de tableau avec lui-même, la valeur peut devenir 0

Le jeu de Nim et le XOR

  • Nim est un jeu où l’on choisit à chaque tour un tas parmi plusieurs puis on retire autant d’objets qu’on le souhaite, à condition d’en retirer au moins un ; le joueur qui ne peut plus jouer a perdu
  • Dans la version simple de Nim, une position perdante est une position où le XOR bit à bit des tailles de tous les tas vaut 0
  • Si le XOR vaut 0 et que l’on remplace la taille d’un tas a par une autre valeur b, le XOR total change de a XOR b ; comme a≠b, il devient donc non nul
  • Si le XOR n’est pas nul, on peut regarder le bit à 1 le plus significatif de la valeur totale x, choisir un tas dont ce bit vaut 1, puis réduire sa taille à pile XOR x afin de ramener le XOR total à 0
  • Par exemple, avec des tas de tailles 12, 10 et 3, les écritures binaires sont 1100, 1010, 0011, et leur XOR vaut 0101
    • Seul le plus grand tas, 12, est réduit à 9 lorsqu’on lui applique un XOR avec 0101
    • Le coup gagnant consiste donc à retirer 3 objets du tas de 12 pour le ramener à 9

Structures mathématiques qui ressemblent au XOR

  • En théorie des ensembles, la différence symétrique X∆Y est l’opération qui contient les éléments appartenant à exactement un des deux ensembles
    • Si l’on représente l’appartenance d’un élément par une valeur booléenne, la différence symétrique est équivalente au XOR
    • Elle partage donc avec lui des propriétés comme la commutativité et l’associativité
  • En théorie des groupes, un groupe d’exposant 2 est un groupe dans lequel tout élément est son propre inverse
    • Une telle opération satisfait l’associativité et, par exercice classique, la commutativité en découle aussi
    • Le fait que deux occurrences d’un même élément s’annulent rappelle le XOR
    • Tout groupe d’exposant 2 peut être compris comme une forme de XOR bit à bit sur des fonctions à valeurs {0,1}
  • Dans l’analyse de Sprague-Grundy, on attribue un nombre de Grundy à de nombreuses positions de jeu impartial
    • Le nombre de Grundy d’une position composite obtenue en combinant plusieurs sous-jeux se calcule comme le XOR bit à bit des nombres de Grundy de chacun
    • En théorie des jeux, on appelle parfois nim-sum le XOR bit à bit d’entiers non négatifs
  • Le corps GF(2) est un corps fini ne contenant que 0 et 1
    • L’addition et la soustraction s’y comportent comme un XOR
    • La multiplication s’y comporte comme un AND
    • On a donc a AND (b XOR c) = (a AND b) XOR (a AND c)

Algèbre linéaire sur GF(2) et correction d’erreurs

  • Les vecteurs et matrices sur GF(2) sont des structures dont les composantes valent 0 ou 1, et l’addition de vecteurs ou de matrices se fait composante par composante avec un XOR
  • Multiplier une matrice M par un vecteur v revient à faire le XOR des colonnes de M sélectionnées par les composantes à 1 de v
  • Un code correcteur d’erreurs étend un message de m bits en un mot de code plus long de n bits afin de permettre la détection ou la correction de certaines erreurs de bits
    • Si des mots de code valides diffèrent sur beaucoup de bits, un petit nombre d’erreurs de bits ne transformera pas l’un en un autre mot de code valide
    • Si deux mots de code valides diffèrent d’au moins k bits, alors moins de k erreurs peuvent être détectées, et moins de k/2 erreurs peuvent être corrigées en recherchant le mot de code valide le plus proche
  • Les codes linéaires utilisent une generator matrix et une check matrix sur GF(2)
    • L’émetteur utilise la generator matrix pour étendre un message de m bits en un mot de code de n bits
    • Le récepteur utilise la check matrix pour vérifier si le mot de code reçu est valide et, en cas d’erreur, obtenir un syndrome
    • Un même motif d’erreur produit le même syndrome indépendamment du message
  • Le code de Hamming est un exemple pour les longueurs de code n de la forme 2^d−1
    • Pour n=15, on numérote les positions des 15 bits avec les nombres binaires non nuls sur 4 bits, de 0001 à 1111
    • Le récepteur fait le XOR de tous les indices correspondant à des bits à 1 ; si le résultat vaut 0, il s’agit d’un mot de code valide
    • Si un seul bit est inversé, le résultat du XOR est directement l’indice du bit inversé, ce qui permet de corriger l’erreur d’un bit sans table de lookup
    • Un code de Hamming sur 15 bits transporte 11 bits de données et utilise 4 bits pour la correction d’erreurs

Polynômes sur GF(2), CRC et corps finis plus grands

  • Les polynômes sur GF(2) sont des polynômes formels dont les coefficients valent 0 ou 1, et leur addition revient à faire le XOR des coefficients de même degré
  • La multiplication de polynômes suit le principe habituel des produits partiels, puis réduit les coefficients modulo 2
    • Si l’on représente cela comme une suite de bits, cela ressemble à une multiplication entière, mais la combinaison des produits partiels utilise un XOR sans retenue au lieu d’une addition ordinaire
    • x86 fournit des instructions de multiplication sans retenue, dont CLMUL, et Arm fournit des instructions de la famille polynomial multiplication
  • Le CRC utilise comme somme de contrôle le reste d’une division polynomiale sur GF(2)
    • On considère la suite de bits du message émis comme un grand polynôme M, puis on conserve le reste M mod P après division par un polynôme convenu P
    • Cette technique est utilisée pour la vérification de paquets réseau comme Ethernet et technologies similaires
    • Le CRC ne corrige pas les erreurs, il les détecte seulement, et convient donc aux cas où la quasi-totalité des transmissions sont correctes mais où des inversions de bits ou du bruit apparaissent occasionnellement
  • On peut construire des corps finis plus grands à partir de polynômes sur GF(p) en prenant les restes modulo un irreducible polynomial Q
    • Si le degré de Q vaut d, alors le nouveau corps fini contient p^d éléments
    • Quand p=2, un irreducible polynomial peut être écrit comme un motif de bits noté comme un entier, et ces suites figurent dans OEIS A014580
  • Les corps finis de taille puissance de 2 apparaissent dans de nombreuses techniques cryptographiques
    • Le corps fini de taille 2^8 est un composant essentiel d’AES et de Twofish
    • Le corps fini de taille 2^128 est utilisé dans GCM, qui combine chiffrement de masse et protection de l’intégrité
    • Les corps finis de taille puissance de 2 apparaissent aussi dans certaines formes de cryptographie sur courbes elliptiques et dans les algorithmes de décodage du schéma post-quantique Classic McEliece

À lire aussi

1 commentaires

 
GN⁺ 2025-02-19
Avis sur Hacker News

  • Ma technique XOR maudite préférée, c’est la liste doublement chaînée XOR : https://en.m.wikipedia.org/wiki/XOR_linked_list
    Au lieu que chaque nœud stocke séparément les pointeurs suivant/précédent, il stocke une seule valeur obtenue par XOR des deux. Évidemment, ce n’est pas un pointeur valide, mais lors du parcours, faire un XOR entre le pointeur du nœud précédent et le pointeur combiné donne le pointeur du nœud suivant, et le parcours bidirectionnel reste possible. Ça a un côté illégal.

    • Par rapport à une liste doublement chaînée classique, on perd la capacité de supprimer cet élément lorsqu’on ne dispose que de l’adresse de l’élément, ou seulement d’un itérateur stable face aux insertions/suppressions. Or c’est souvent la raison principale d’utiliser une liste doublement chaînée.
      Défaut moins fondamental : écrire une liste chaînée XOR en C strictement conforme au standard est très pénible. Le standard ne garantit pas que caster le même pointeur en entier produise le même entier ; en pratique, il faut donc tout représenter en uintptr_t pour conserver une version castée en entier normalisée.
    • Même sur des processeurs 64 bits, si l’on considère que la plupart des applis se contentent de moins de 4 Go de RAM, on peut encore réduire l’espace de stockage avec seulement un espace d’adressage 32 bits.
      On pourrait même aller plus loin avec des pointeurs proches/relatifs sur 16 bits. Cela pourrait bien s’accorder avec une conception orientée données, par exemple avec des blocs de 64K éléments où les éléments internes sont référencés par des indices uint16.
    • Avec ça, le garbage collector va détester. Ou, au minimum, il considérera sans doute cette structure de données comme des déchets.
    • Je me demande pourquoi on aurait envie d’utiliser cette technique.
    • Ce n’est pas vraiment différent de stocker la différence entre deux pointeurs plutôt que les pointeurs eux-mêmes. En stockant la différence, on peut évidemment aussi parcourir dans les deux sens.

  • Il manque quelque chose. XOR est aussi une fonction de hachage linéaire 3-wise indépendante, utilisable pour l’échantillonnage quasi uniforme probabiliste des solutions de fonctions booléennes et pour leur comptage. C’est vraiment utile, et on s’en sert pour construire des compteurs qui donnent un nombre probabiliste mais prouvé. J’ai écrit une explication plus facile à comprendre ici : https://www.msoos.org/2018/12/how-approximate-model-counting...
    En gros, à chaque fois, on réduit l’espace des solutions presque exactement de moitié. On continue donc à ajouter des contraintes XOR jusqu’à ce qu’il reste, par exemple, 10 solutions ; si le nombre de XOR ajoutés est k, il suffit de multiplier 10 par 2^k. Comme on divise par deux à chaque étape, on arrive vite à l’ordre de 10 solutions, ce qui passe bien à l’échelle.
    Les articles associés sont sur https://arxiv.org/abs/1306.5726 et https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf, et les outils sur https://github.com/meelgroup/approxmc et https://github.com/meelgroup/unigen. Lors du dernier concours de model counting, combiné à un compteur exact, cela a écrasé les autres concurrents ; les slides sont ici : https://mccompetition.org/assets/files/2024/MC2024_awards.pd...

  • L’une de mes anecdotes préférées sur XOR est celle racontée par Bryan Cantrill, d’Oxide, Joyent et Sun, dans cette présentation https://speakerdeck.com/bcantrill/oral-tradition-in-software... et cette vidéo https://www.youtube.com/watch?v=4PaWFYm0kEw
    Pour résumer sans devoir cliquer sur les liens : quand il était chez Sun, il discutait avec son collègue Roger Faulkner de la raison pour laquelle C n’a pas de XOR logique. Faulkner disait que c’était parce qu’on ne peut pas faire d’évaluation en court-circuit, et Brian trouvait ça étrange. Roger a alors envoyé un e-mail à Dennis Ritchie, qui a confirmé que Faulkner avait raison. La façon dont Cantrill le raconte est drôle, mais ce qui est stupéfiant, c’est surtout qu’ils pouvaient demander directement à la personne concernée.

    • DMR était quelqu’un d’étonnamment gentil, serviable et accessible. Au milieu des années 80, quand j’étais étudiant de premier cycle, j’ai lu le « premier » cas de portage d’Unix v6 vers un Interdata 8/32 plutôt que vers un PDP-11, et j’ai envoyé un e-mail à l’aveugle à dmr@research.att.com pour demander s’il existait davantage d’informations sur l’architecture.
      À l’époque, il n’y avait pas Google et la bibliothèque de l’université n’avait pas de documentation ; quelques jours plus tard, il m’a demandé mon adresse physique, puis quelques semaines après, une copie du manuel récapitulatif du jeu d’instructions est arrivée dans ma boîte aux lettres. Ça avait des airs de famille IBM 360, et je l’ai encore.
    • C a bien un XOR logique : c’est l’opérateur !=. Contrairement aux autres opérateurs logiques, il faut normaliser ses arguments en une seule valeur vraie, et cela s’accorde bien avec l’idiome de conversion booléenne de C, !!.
    • Je ne comprends pas pourquoi « parce qu’on ne peut pas faire d’évaluation en court-circuit » ferait obstacle à l’ajout d’un opérateur. J’aimerais que quelqu’un me l’explique.
    • Le sujet commence à 37:18.
    • C possède depuis plus de 40 ans un opérateur XOR bit à bit ^ : https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/

  • J’ai appris aujourd’hui que si l’on fait un XOR entre l’emoji automobile et 0x20, autrement dit si on le « met en minuscules », il devient l’emoji piétons interdits. C’est presque trop parfait pour être une coïncidence, je me demande si quelqu’un sait si c’était intentionnel
    En poussant un peu trop l’idée, on pourrait même dire que la minuscule de l’emoji automobile est le panneau « piétons interdits »

    • Pour contourner le filtre de commentaires de HN qui supprime les emojis, on peut vérifier ainsi :
      >>> from unicodedata import lookup, name
      >>> name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20))
      'NO PEDESTRIANS'
    • La minuscule de l’automobile devrait plutôt être un kart
    • :tada: → :tophat:, :rocket: → :mountain_cableway: fonctionnent aussi

  • Une bonne analogie concrète pour expliquer XOR, c’est l’interrupteur d’éclairage en haut et en bas d’un escalier. Il y a un interrupteur en bas, un autre en haut, et les deux commandent la même lampe
    Au départ, ils sont tous les deux en position éteinte ; si on actionne l’interrupteur du bas, la lumière s’allume. On monte l’escalier et on actionne l’interrupteur du haut : les deux interrupteurs sont alors en position « allumé », mais la lumière est éteinte. La lumière n’est allumée que lorsqu’un seul interrupteur est en position « allumé » et l’autre en position « éteint » ; dans les autres cas, elle est éteinte

    • L’électricien de notre bureau a peut-être mal câblé quelque chose. Il y a deux interrupteurs dans la pièce, et en y repensant ils se comportent plutôt comme une porte AND que comme un XOR. Les deux interrupteurs du salon, eux, se comportent clairement comme un XOR

  • Je n’aime vraiment pas qu’on appelle couramment cette fonction logique XOR, c’est-à-dire « OR exclusif ». Dans presque tous les cas, ce qu’on veut vraiment dire, c’est « somme modulo 2 », autrement dit la parité, et non un OR exclusif
    La « somme modulo 2 »/parité et le « OR exclusif » sont deux fonctions logiques différentes, qui ne coïncident que lorsqu’il y a 2 opérandes d’entrée. C’est parce qu’il n’existe qu’un seul nombre impair inférieur ou égal à 2
    Quand il y a 3 entrées ou plus, ce que la plupart des gens appellent XOR est en réalité la parité, qui vaut 1 lorsqu’un nombre impair d’entrées vaut 1. En revanche, avec 3 entrées ou plus, le OR exclusif est la fonction qui ne vaut 1 que lorsqu’exactement une seule entrée vaut 1 et que toutes les autres valent 0
    Dans le matériel informatique, la parité est bien plus importante que le OR exclusif. La raison principale est que l’addition modulo 2 sert de brique de base pour implémenter l’addition de nombres plus grands. À l’inverse, en mathématiques, le OR exclusif est bien plus important que la parité
    Par exemple, les quantificateurs qui expriment qu’un prédicat est vrai pour certains éléments d’un ensemble, pour tous les éléments ou pour un unique élément reposent respectivement sur OR, AND et le OR exclusif. Le « or » du langage naturel désigne toujours un OR inclusif ou un OR exclusif, jamais la parité que beaucoup de programmeurs appellent XOR
    En programmation, on a rarement besoin de calculer la fonction logique OR exclusif, mais elle sert souvent à décrire le comportement d’un programme. Par exemple lorsqu’une seule des première, deuxième ou troisième instructions d’un bloc select/case/switch est exécutée, ou lorsqu’on décrit les types que peut prendre la valeur courante d’une variable de type union/somme

    • La norme de symboles électrotechniques IEC 60617 traite correctement ce point. Une porte XOR est notée =1, une porte de parité 2k + 1. Mais avec des logiciels de conception de circuits pour PCB ou FPGA, on peut encore se faire piéger en obtenant autre chose que ce qu’on attendait
    • Ce dont il est question en mathématiques s’appelle le quantificateur d’existence unique, et possède son propre symbole ∃!
    • L’affirmation selon laquelle, avec 3 entrées ou plus, le « OR exclusif » est vrai uniquement lorsqu’une seule entrée vaut 1 demande une justification
    • Cette interprétation est aussi abordée dans l’essai d’origine

  • Il y a aussi la table de hachage distribuée Kademlia : kademlia distributed hash table. La grande idée est que chaque nœud reçoit des bits arbitraires dans l’intervalle [0, 2^m), et que la distance est définie par XOR. On cherche un algorithme distribué permettant d’envoyer rapidement une information de X vers Y sans connaître tout le réseau
    On peut prouver que cela fonctionne uniquement avec les maths, mais l’intuition visuelle que je préfère est la suivante. Supposons que le nœud de départ X veuille trouver le nœud k. Définissons un « arbre de distances depuis X » comme un arbre binaire dont les feuilles ont pour indices 0, 1, 2..., et étiquetons chaque feuille avec X^leaf_index pour représenter sa distance à X. Par exemple, comme dist(x, x) = x^x = 0, l’étiquette du nœud X d’origine se trouve sur la feuille la plus à gauche, 0
    L’intervalle [2^i, 2^(i+1)) correspond à un certain sous-arbre de l’arbre de distances depuis X. Si l’on sait que la distance de k appartient à cet intervalle, on interroge comme voisin approximatif un nœud Y situé dans cet intervalle
    Quel que soit le Y choisi, dans l’arbre de distances depuis Y, le préfixe du résultat sera toujours une permutation du sous-arbre [2^i, 2^(i+1)) choisi dans l’arbre de distances depuis X. Plus précisément, on peut voir cela comme labels_of_leaves_of_X([2^i, 2^(i+1))) == labels_of_leaves_of_Y([0, 2^i)). Les indices sont fondés sur la distance, mais les étiquettes peuvent changer
    Il existe beaucoup de documents bien plus rigoureux, mathématiquement et empiriquement, pour comparer avec d’autres tables de hachage distribuées comme Chord. Mais cette intuition visuelle donne une idée de ce qu’est la « symétrie » de Kademlia, et du fait que chacun possède ses propres voisins locaux et son propre sous-arbre
    À l’inverse, même implémenté dans les deux sens, Chord consomme deux fois plus de mémoire, semble plus risqué à implémenter, et il est difficile d’obtenir ce niveau d’« isolation ». Une fenêtre glissante de voisins de taille S bouge en permanence, et il existe 2^m voisins différents par bit. Même si la plupart des voisins se ressemblent, ce n’est pas aussi propre
    Dans Kademlia, il y a 1 + 2 + 4 ... + 2^m-1 voisins, et l’ensemble est bien ordonné

  • Pour ceux que ça intéresse, il s’agit du même Simon Tatham que celui de Simon Tatham's Portable Puzzle Collection. Si vous ne connaissez pas, ça vaut le coup d’y jouer hors ligne quand on s’ennuie
    J’y ai passé beaucoup de temps au lycée : https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

  • De nos jours, beaucoup de solveurs d’optimisation spécialisés, par exemple les Ising Machines, utilisent le problème XOR comme benchmark. En réalité, résoudre plusieurs clauses XOR se fait en temps polynomial par élimination de Gauss, ce qui en limite un peu l’intérêt pratique, mais comme tous les solveurs présentent une mise à l’échelle exponentielle, cela reste un bon moyen d’évaluer leurs performances.
    La deuxième implémentation intéressante est liée au cryptosystème de McEliece. C’est un chiffrement à clé publique des années 1970, qui suscite à nouveau l’attention aujourd’hui en raison de sa résistance quantique. Une attaque de déchiffrement consiste à trouver la solution d’un ensemble d’équations XOR ; là encore, c’est en temps polynomial, mais avec la contrainte que la distance de Hamming doit être égale à une certaine valeur incluse dans la clé publique.

  • Quand j’apprenais l’assembleur Z80 pour programmer sur TI-83, chaque octet de code machine comptait. L’espace de stockage total de la calculatrice n’était que de 24 Ko.
    Pour initialiser à 0 le registre accumulateur principal a, on utilisait XOR a au lieu de LD a, 0. Dans les instructions arithmétiques/logiques, a est l’opérande implicite, donc XOR a effectue un XOR de a avec lui-même, et l’instruction entière ne prend qu’un seul octet. En revanche, pour charger explicitement 0 dans a, le littéral 0 doit être inclus dans l’opcode, si bien que LD a, 0 est une instruction de 2 octets.