Intuition de l'opération XOR

Question

Je suis récemment tombé sur este J'ai posé une question sur Leetcode et j'ai trouvé une solution pour laquelle j'ai besoin d'une clarification :

Dans un tableau d'entiers, chaque élément apparaît deux fois sauf un. Trouvez cet élément unique.

Note : Votre algorithme doit avoir une complexité d'exécution linéaire. Pourriez-vous l'implémenter sans utiliser de mémoire supplémentaire ?

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for(auto & c : nums) {
            result ^= c;
        }
        return result;
    }
};

Tout d'abord, à quels types de mots-clés dois-je prêter attention pour comprendre que je dois utiliser une opération XOR pour cette question ?

De plus, pourquoi le fait de faire un XOR de tous les éléments du vecteur les uns avec les autres nous donne celui qui n'est pas répété ?

---

Merci à tous pour ces réponses, voici quelques informations supplémentaires sur les propriétés binaires pour toute personne intéressée : Plus d'informations sur les bits

Answer 1

1. A ^ 0 == A

2. A ^ A == 0

3. A ^ B == B ^ A

4. (A ^ B) ^ C == A ^ (B ^ C)

(3) et (4) signifient ensemble que l'ordre dans lequel les numéros sont xor ed n'a pas d'importance.

Ce qui signifie que, par exemple, A^B^X^C^B^A^C est égal à A^A ^ B^B ^ C^C ^ X .

En raison du (2) qui est égal à 0^0^0^X .

En raison du (1) qui est égal à X .

---

Je ne pense pas qu'il y ait de mots-clés spécifiques qui puissent vous aider à identifier de tels problèmes. Vous devez simplement connaître les propriétés ci-dessus de XOR.

Answer 2

L'opérateur Xor est commutatif :

1.      X  Y = Y  X                    for any integers X and Y

y associatif :

2.      X  (Y  Z) = (X  Y)  Z      for any integers X, Y and Z

Il s'ensuit que le résultat de toute séquence de xor est totalement indépendante de l'ordre des opérandes (c'est-à-dire l'ordre des éléments du tableau).

3.     X  X = 0                         for any integer X

4.     X  0 = 0  X = X                for any integer X

---

Dans le problème, nous avons une expression où chaque élément Ai apparaît deux fois, sauf un élément singulier B. L'opération Xor qui en résulte est équivalente à :

     (A1  A1)  (A2  A2)     ...    B
 = 
         0            0         ...    B
 = 
         B

---

Quels sont les mots-clés auxquels je dois faire attention pour comprendre que je dois utiliser une opération XOR pour cette question ?

Certains problèmes peuvent être résolus rapidement en utilisant la manipulation des bits. Après vous être familiarisé avec les opérateurs booléens et leurs propriétés, et avoir vu suffisamment d'applications comme celle-ci, vous " sentirez " naturellement quand ils sont utiles pour résoudre un problème donné.

Answer 3

L'aspect intuitif clé qui distingue XOR des autres opérateurs logiques est qu'il est sans perte o sans perte ce qui signifie que, contrairement à ET et OU (et plus similaire à NO à cet égard), il est déterministcalement réversible : Vous pouvez exactement récupérer une des valeurs d'entrée étant donné le reste de l'historique du calcul.

Les schémas suivants illustrent que ET y OU ont chacune au moins un cas où l'état de l'une des entrées est irrécupérable, étant donné une certaine valeur de l'autre entrée. Je les désigne comme des entrées "perdues".

Pour le XOR il n'existe aucune condition dans laquelle une valeur d'entrée ou de sortie ne peut être récupérée, compte tenu du reste de l'historique du calcul. En fait, il y a une symétrie qui sait que deux valeurs quelconques du triple (in0, in1, out) vous permet de récupérer le troisième. En d'autres termes, quelle que soit l'entrée ou la sortie, chacune de ces trois valeurs est la XOR des deux autres !

Cette image suggère qu'une autre façon de penser à la XOR est en tant que contrôlable NON porte. En basculant l'une des entrées (l'entrée supérieure dans l'exemple ci-dessus), vous pouvez contrôler si l'autre entrée (inférieure) est niée ou non.

Un autre point de vue équivalent est que XOR met en œuvre le positive-logique non égal à (!=) par rapport à ses deux entrées. Et donc aussi la est égal à fonction (=) sous logique négative .

Conformément à ses propriétés de symétrie et de préservation de l'information, XOR devrait venir à l'esprit pour les problèmes qui nécessitent une réversibilité ou une récupération parfaite des données. L'exemple le plus évident est celui XOR L'utilisation d'un ensemble de données avec une "clé" constante obscurcit trivialement les données de sorte que la connaissance de la clé (qui peut être gardée "secrète") permet une récupération exacte.

La préservation de l'ensemble des informations disponibles est également souhaitable dans les cas suivants hachage . Comme vous voulez des valeurs de hachage qui discriminent au maximum les éléments sources, vous devez vous assurer que le plus grand nombre possible de leurs caractéristiques distinctives sont incorporées, en minimisant les pertes, dans le code de hachage. Par exemple, pour hacher une valeur de 64 bits en 32 bits, vous utiliserez le langage de programmation suivant XOR opérateur ^ car c'est un moyen simple de garantir que chacun des 64 bits d'entrée a la possibilité d'influencer la sortie :

uint GetHashCode(ulong ul)
{
    return (uint)ul ^ (uint)(ul >> 32); 
}

Notez que dans cet exemple, l'information est perdue même si XOR a été utilisé. (En fait, la "perte d'information stratégique" est en quelque sorte le but du hachage). La valeur originale de ul n'est pas récupérable à partir du code de hachage, car avec cette seule valeur, vous n'avez pas deux des trois valeurs de 32 bits qui ont été utilisées dans le calcul interne. Rappelez-vous que vous devez conserver deux des trois valeurs pour une inversion parfaite. A partir du code de hachage résultant et des deux valeurs qui étaient XOR ed, vous avez peut-être sauvegardé le résultat, mais vous ne sauvegardez généralement pas l'un ou l'autre pour l'utiliser comme valeur clé pour obtenir l'autre. 1

En guise d'aparté amusant, XOR a été d'une aide précieuse à l'époque de des astuces pour le travail en équipe . Ma contribution à l'époque était un moyen de Activation ou désactivation conditionnelle des bits sans branchement en C/C++ :

unsigned int v;       // the value to modify
unsigned int m;       // mask: the bits to set or clear
int f;                // condition: 0 to 'set', or 1 to 'clear'

v ^= (-f ^ v) & m;    // if (f) v |= m; else v &= ~m;

Sur une note plus sérieuse, le fait que XOR est non-lossy a important théorie de l'information implications pour l'informatique futuriste, en raison d'une relation importante entre le traitement de l'information et la Deuxième loi de la thermodynamique . Comme expliqué dans un livre excellent et accessible de Charles Seife, Décoder l'univers il s'avère que la perte d'information pendant le calcul a un impact sur la productivité. exact relation mathématique avec le rayonnement du corps noir émanant d'un système de traitement. En effet, la notion de entropie joue un rôle central dans la quantification de la manière dont la "perte" d'information est (ré)exprimée en chaleur (il s'agit également de la même relation proéminente de la célèbre étude de Steven Hawking pari du trou noir ).

De tels propos concernant XOR n'est pas nécessairement exagéré ; Seife note que le développement des CPU modernes se heurte actuellement à des limites de tolérance fondamentales sur le plan de l'architecture de l'ordinateur. watts/cm² des matériaux semi-conducteurs, et qu'une solution serait de concevoir des systèmes informatiques réversibles, ou sans perte. Dans cette future génération spéculative de CPU, XOR La capacité de l'entreprise à préserver l'information. et ainsi évacuer la chaleur -serait inestimable pour augmenter la densité de calcul (c'est-à-dire, MIPS /par cm²) malgré les limitations de ces matériaux.

---

1. Dans cet exemple simple, les 3 valeurs pertinentes seraient le code de hachage et les parties supérieure et inférieure de l'original. ulong valeur. Bien sûr, les "données" hachées originales, représentées par ul ici, probablement est retenu.

Answer 4

XOR est toujours défini en termes de chiffres binaires (ou de notions équivalentes, comme les affirmations vraies ou fausses). Il n'y a pas de XOR spécial pour les entiers, autre que le XORing des bits correspondants de leurs représentations binaires.

Soit A et B deux variables booléennes, et soit XOR une fonction booléenne qui prend deux variables booléennes.
AB = 1 si soit (A = 0 et B = 1), soit (A = 1 et B = 0) (c'est-à-dire qu'ils sont différents),
AB=0 si soit (A = 0 et B = 0), soit (A = 1 et B = 1). (c'est-à-dire qu'ils sont identiques)

Ainsi, en prenant en considération votre question, puisque sur les n éléments du vecteur, chaque élément apparaît deux fois, sauf un, l'idée est la suivante que la représentation binaire des nombres dupliqués serait la même, donc le résultat XOR s'annulerait mutuellement comme 11 =0 et 00= 0.

Pour A=5 ,sa représentation binaire est 101,donc AA = (101)(101) = 000 dont la représentation décimale est 0.

RAPPELEZ-VOUS QUE L'ORDRE DANS LEQUEL LES NOMBRES APPARAISSENT LES UNS APRÈS LES AUTRES N'A PAS D'IMPORTANCE CAR ((AB)C) = (A(BC)) . Finalement, ce que vous obtenez à la fin après avoir XORÉ chaque nombre est le nombre qui apparaît une fois.

Pour répondre à votre question concernant le moment où vous devez utiliser les opérations XOR pour résoudre une question, pratiquez quelques questions de MANIPULATION DE BITS ; vous finirez par y arriver.
Un indice : La question qui demande de trouver un élément qui a une propriété unique par rapport aux autres, nécessite la manipulation de bits.
Exemple : Dans un tableau où chaque élément apparaît trois fois, à l'exception d'un élément qui n'apparaît qu'une fois. Trouvez l'élément qui apparaît une fois.

Answer 5

Une opération simple qui peut être effectuée sur le tableau est de choisir une propriété P et comptez le nombre d'éléments du tableau qui satisfont à la propriété. Par exemple, si P est la propriété d'être divisible par 5, nous pouvons parcourir le tableau en boucle et compter le nombre d'éléments qui sont divisibles par 5.

La précondition sur le tableau nous permet d'obtenir des informations sur l'élément singleton à partir d'un tel comptage. Si le nombre d'éléments satisfaisant P est impair, alors le singleton a la propriété P . Si le nombre d'éléments satisfaisant P est pair, alors le singleton ne doit pas avoir la propriété P . Par exemple, si on compte 3 éléments divisibles par 5, alors le singleton doit être divisible par 5.

Par conséquent, si nous pouvons inventer une collection de propriétés telle que le fait de savoir si chaque propriété est vraie ou fausse spécifiera entièrement tout élément, nous pouvons obtenir la réponse en comptant le nombre d'éléments avec chaque propriété et en vérifiant la parité des comptes.

Il existe de nombreuses collections de propriétés différentes qui fonctionneront. Mais autant être efficace. Étant donné b propriétés différentes, il y a (au maximum) 2**b Les tests peuvent être réalisés de plusieurs manières différentes, et nous ne pouvons donc faire la distinction qu'entre autant d'éléments possibles. Ainsi, nous avons besoin d'au moins b différentes propriétés pour spécifier complètement un b -un nombre de bits.

Une telle collection minimale de propriétés qui est facile à tester par un ordinateur est la collection où le n La propriété est "Est-ce que le nombre a un 1 dans le n ". Si nous connaissons la réponse à cette question pour chaque n alors nous pouvons clairement reconstituer le nombre.

Une autre optimisation est que nous n'avons pas besoin de garder la trace du nombre total d'éléments satisfaisant une propriété ; nous avons seulement besoin de la parité. Si nous nous contentons de garder la trace du nombre modulo 2, nous n'avons besoin que d'un bit pour garder la trace au lieu d'un entier size_t .

Puisque nous gardons la trace de b différents bits d'information, chacun correspondant à une valeur de place particulière n nous pouvons assembler ces bits ensemble dans une b -un nombre de bits.

C'est exactement la solution XOR présentée dans la question.

Pour commencer, le compte courant du nombre de nombres ayant chaque bit est 0 pour chaque bit (d'où result est initialisé à 0). Ainsi, lorsque nous effectuons le XOR d'un élément du tableau, nous ajoutons en fait un modulo 2 à ces bits du tableau. result où l'élément avait un 1. Enfin, result ne nécessite aucun décodage, car le nombre avec 1 bits exactement où result a 1 bits est result lui-même.