XNOR de deux nombres

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

Énoncé du problème

Étant donné deux nombres x et y. Trouvez le XOR de deux nombres.

Exemple Exemple 1

Input: x = 12, y = 5

Output: 6

Instructions

(12)<sub>10</sub> = (1100)<sub>2</sub>
(5)<sub>10</sub> = (101)<sub>2</sub>
XNOR = (110)2 = (6)<sub>10</sub>

La traduction chinoise de

Sampe Exemple 2

est :

Sampe Exemple 2

Input: x = 16, y = 16

Output: 31

Instructions

(16)<sub>10</sub> = (10000)<sub>2</sub>
(16)<sub>10</sub> = (10000)<sub>2</sub>
XNOR = (11111)<sub>2</sub> = (31)<sub>10</sub>

Méthode 1 : Méthode violente

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.

pseudocode

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

Exemple : implémentation C++

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.

#include <bits/stdc++.h>
using 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;
}

Sortie

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)

Méthode 2

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.

Exemple 1

Input: x = 12, y = 5

Output: 6

Instructions

(12)10 = (1100)2
(5)10 = (101)2
Toggled bits of 12 = 0011
0011 ^ 101 = 0110

La traduction chinoise de

Sampe Exemple 2

est :

Sampe Exemple 2

Input: x = 12, y = 31

Output: 12

Instructions

(12)10 = (1100)2
(31)10 = (11111)2
Toggled bits of 31 = 00000
00000 ^ 1100 = 01100

pseudocode

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

Exemple : implémentation C++

Dans le programme ci-dessous, tous les bits du nombre le plus élevé sont basculés puis XOR avec le nombre le plus bas.

#include <bits/stdc++.h>
using 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;
}

Sortie

XNOR of 5 and 15 = 5

Complexité temporelle : O(logn), due au parcours dans la fonction toggle()

Complexité spatiale : O(1)

Méthode 3 : Masque de bits

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.

Exemple Exemple 1

Input: x = 12, y = 5

Output: 6

Instructions

(12)<sub>10</sub> = (1100)<sub>2</sub>
(5)<sub>10</sub> = (101)<sub>2</sub>
1100 ^ 101 = 1001
Inverse of 1001 = 0110

Exemple 2

Input: x = 12, y = 31

Output: 12

Instructions

(12)<sub>10</sub> = (1100)<sub>2</sub>
(31)<sub>10</sub> = (11111)<sub>2</sub>
1100 ^ 11111 = 10011
Inverse of 10011 = 01100

pseudocode

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

Exemple : implémentation C++

Dans le programme ci-dessous, le masque de bits est utilisé pour obtenir uniquement les bits requis de l'inverse de x xor y.

#include <bits/stdc++.h>
using 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;
}

Sortie

XNOR of 10 and 10 = 7

Conclusion

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!