La porte XNOR (XNOR) est une porte logique numérique qui accepte deux entrées et donne une sortie. Sa fonction est le complément logique de la porte OU exclusif (XOR). La sortie est VRAI si les deux entrées sont identiques ; FAUX si les entrées sont différentes. La table de vérité de la porte XNOR est donnée ci-dessous.
| un | B | Sortie |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Étant donné deux nombres x et y. Trouvez le XOR de deux nombres.
Input: x = 12, y = 5
Output: 6
(12)10 = (1100)2 (5)10 = (101)2 XNOR = (110)2 = (6)10
Input: x = 16, y = 16
Output: 31
(16)10 = (10000)2 (16)10 = (10000)2 XNOR = (11111)2 = (31)10
La méthode de la force brute consiste à vérifier chaque bit des deux nombres et à comparer s'ils sont identiques. S'ils sont identiques, ajoutez 1, sinon ajoutez 0.
procedure xnor (x, y) if x > y then swap(x,y) end if if x == 0 and y == 0 then ans = 1 end if while x x_rem = x & 1 y_rem = y & 1 if x_rem == y_rem then ans = ans | (1 << count) end if count = count + 1 x = x >> 1 y = y >> 1 end procedure
Dans le programme ci-dessous, vérifiez si les bits de x et y sont identiques, puis définissez les bits dans la réponse.
#includeusing namespace std; // Function to swap values of two variables void swap(int *a, int *b){ int temp = *a; *a = *b; *b = temp; } // Function to find the XNOR of two numbers int xnor(int x, int y){ // Placing the lower number in variable x if (x > y){ swap(x, y); } // Base Condition if (x == 0 && y == 0){ return 1; } // Cnt for counting the bit position Ans stores ans sets the bits of XNOR operation int cnt = 0, ans = 0; // executing loop for all the set bits in the lower number while (x){ // Gets the last bit of x and y int x_rem = x & 1, y_rem = y & 1; // If last bits of x and y are same if (x_rem == y_rem){ ans |= (1 << cnt); } // Increase counter for bit position and right shift both x and y cnt++; x = x >> 1; y = y >> 1; } return ans; } int main(){ int x = 10, y = 11; cout << "XNOR of " << x << " and " << y << " = " << xnor(x, y); return 0; }
XNOR of 10 and 11 = 14
Complexité temporelle : O(logn), car le parcours est effectué sur tous les bits de journal.
Complexité spatiale : O(1)
XNOR est l'opération inverse de l'opération XOR, et sa table de vérité est également l'opération inverse de la table XOR. Ainsi, en commutant les bits du nombre le plus élevé, c'est-à-dire en réglant 1 sur 0 et 0 sur 1, puis XOR avec le nombre inférieur produira un nombre XNOR.
Input: x = 12, y = 5
Output: 6
(12)10 = (1100)2 (5)10 = (101)2 Toggled bits of 12 = 0011 0011 ^ 101 = 0110
Input: x = 12, y = 31
Output: 12
(12)10 = (1100)2 (31)10 = (11111)2 Toggled bits of 31 = 00000 00000 ^ 1100 = 01100
procedure toggle (n) temp = 1 while temp <= n n = n ^ temp temp = temp << 1 end procedure procedure xnor (x, y) max_num = max(x,y) min_num = min(x,y) toggle (max_num) ans = max_num ^ min_num end procedure
Dans le programme ci-dessous, tous les bits du nombre le plus élevé sont basculés puis XOR avec le nombre le plus bas.
#includeusing namespace std; // Function to toggle all bits of a number void toggle(int &num){ int temp = 1; // Execute loop until set bit of temp cross MST of num while (temp <= num){ // Toggle bit of num corresponding to set bit in temp num ^= temp; // Move set bit of temp to left temp <<= 1; } } // Function to find the XNOR of two numbers int xnor(int x, int y){ // Finding max and min number int max_num = max(x, y), min_num = min(x, y); // Togglinf the max number toggle(max_num); // XORing toggled max num and min num return max_num ^ min_num; } int main(){ int x = 5, y = 15; cout << "XNOR of " << x << " and " << y << " = " << xnor(x, y); return 0; }
XNOR of 5 and 15 = 5
Complexité temporelle : O(logn), due au parcours dans la fonction toggle()
Complexité spatiale : O(1)
Logiquement parlant, XNOR est l'opération inverse de XOR, mais lors de l'opération de complément à deux sur XOR, les zéros non significatifs sont également inversés. Pour éviter cela, un masque de bits peut être utilisé pour supprimer tous les bits de début inutiles.
Input: x = 12, y = 5
Output: 6
(12)10 = (1100)2 (5)10 = (101)2 1100 ^ 101 = 1001 Inverse of 1001 = 0110
Input: x = 12, y = 31
Output: 12
(12)10 = (1100)2 (31)10 = (11111)2 1100 ^ 11111 = 10011 Inverse of 10011 = 01100
Procedure xnor (x, y) bit_count = log2 (maximum of a and y) mask = (1 << bit_count) - 1 ans = inverse(x xor y) and mask end procedure
Dans le programme ci-dessous, le masque de bits est utilisé pour obtenir uniquement les bits requis de l'inverse de x xor y.
#includeusing namespace std; // Function to find the XNOR of two numbers int xnor(int x, int y){ // Maximum number of bits used in both the numbers int bit_count = log2(max(x, y)); int mask = (1 << bit_count) - 1; // Inverse of XOR operation int inv_xor = ~(x ^ y); // GEtting the required bits and removing the inversion of leading zeroes. return inv_xor & mask; } int main(){ int x = 10, y = 10; cout << "XNOR of " << x << " and " << y << " = " << xnor(x, y); return 0; }
XNOR of 10 and 10 = 7
En résumé, le XNOR de deux nombres peut être trouvé en utilisant une variété de méthodes et de complexité temporelle, allant des méthodes de force brute O(logn) aux méthodes optimales O(1). L'application d'opérations au niveau du bit est moins coûteuse, la complexité de la force brute est donc logarithmique.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
Introduction à l'utilisation de la boîte de message
Pilote de clavier Lenovo
Comment résoudre l'erreur http 503
Le rôle de la balise em en HTML
Qu'est-ce que la topologie de réseau en étoile ?
Qu'est-ce qu'un tableau vide en php
Est-il nécessaire de mettre à niveau Windows 11 ?
Quelle est la différence entre webstorm et idée ?
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
