XOR

Introduction

• J’ai récemment eu l’occasion d’expliquer l’opérateur XOR. Autrefois, apprendre XOR était indispensable pour manipuler des bits de bas niveau sur ordinateur, mais aujourd’hui cela relève davantage d’un choix pour les programmeurs de haut niveau.
• En préparant un cours sur XOR, j’ai rassemblé diverses réflexions et j’ai décidé de les consigner dans un document.

La logique booléenne de XOR

Qu’est-ce que XOR ?

• XOR est un opérateur logique qui prend deux bits en entrée et produit un bit en sortie.
• Le fonctionnement de XOR peut être expliqué à l’aide d’une table de vérité.

« OR exclusif »

• XOR signifie « OR exclusif » et renvoie vrai lorsque l’une des deux entrées, et une seule, est vraie.

L’opérateur « différent de »

• XOR renvoie 1 lorsque les deux entrées sont différentes, il fonctionne donc de la même manière que a ≠ b.

Inversion conditionnelle

• XOR peut être vu comme une opération d’inversion conditionnelle où une entrée détermine si l’autre doit être inversée.

Parité, ou reste de la division par 2

• XOR renvoie 1 lorsqu’un nombre impair de bits d’entrée est vrai.

Différence modulo 2

• XOR fonctionne de la même manière que le reste de l’addition et de la soustraction modulo 2.

Les propriétés de XOR

• XOR suit les lois de commutativité et d’associativité, 0 agit comme élément neutre, et chaque entrée est son propre inverse.

XOR bit à bit sur les entiers

• Les entiers peuvent être représentés en binaire afin d’effectuer une opération XOR bit à bit.
• Le XOR bit à bit possède les mêmes propriétés que le XOR booléen.

Applications de XOR

Chiffrement : combiner le texte en clair et le flot de clés

• XOR est utilisé en chiffrement pour combiner le texte en clair et le flot de clés.
• XOR est plus simple que l’addition en matériel, ce qui le rend efficace.

Graphismes en pixels : dessiner des formes faciles à effacer

• Dans les graphismes informatiques des années 1980, XOR servait à dessiner des formes faciles à effacer.
• Avec XOR, il suffit de redessiner les pixels pour les restaurer à leur état d’origine.

« L’identité du demi-additionneur »

• XOR représente le bit de poids faible de l’addition, tandis que AND représente le bit de poids fort.
• Sur les entiers, on peut effectuer l’addition à l’aide de XOR et de AND.

Ce document explique diverses propriétés et applications de XOR, et aide à comprendre comment XOR fonctionne et dans quels cas il peut être utile.