XNOR von zwei Zahlen

Das XNOR-Gatter (XNOR) ist ein digitales Logikgatter, das zwei Eingänge akzeptiert und einen Ausgang liefert. Seine Funktion ist das logische Komplement des Exklusiv-ODER-Gatters (XOR). Die Ausgabe ist TRUE, wenn die beiden Eingaben gleich sind; FALSE, wenn die Eingaben unterschiedlich sind. Die Wahrheitstabelle des XNOR-Gatters ist unten angegeben.

eins	B	Ausgabe
1	1	1
1	0	0
0	1	0
0	0	1

Problemstellung

Gegeben seien zwei Zahlen x und y. Finden Sie das XOR zweier Zahlen.

Beispiel Beispiel 1

Input: x = 12, y = 5

Output: 6

Anleitung

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

Die chinesische Übersetzung von

Sampe Beispiel 2

lautet:

Sampe Beispiel 2

Input: x = 16, y = 16

Output: 31

Anleitung

(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>

Methode 1: Gewalttätige Methode

Die Brute-Force-Methode besteht darin, jedes Bit der beiden Zahlen zu überprüfen und zu vergleichen, ob sie gleich sind. Wenn sie gleich sind, addieren Sie 1, andernfalls addieren Sie 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

Beispiel: C++-Implementierung

Überprüfen Sie im folgenden Programm, ob die Bits von x und y gleich sind, und setzen Sie dann die Bits in der Antwort.

#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;
}

Ausgabe

XNOR of 10 and 11 = 14

Zeitliche Komplexität: O(logn), da die Durchquerung für alle logn-Bits durchgeführt wird.

Raumkomplexität: O(1)

Methode 2

XNOR ist die Umkehroperation der XOR-Operation, und ihre Wahrheitstabelle ist auch die Umkehroperation der XOR-Tabelle. Wenn Sie also die Bits der höheren Zahl vertauschen, d. h. 1 auf 0 und 0 auf 1 setzen, dann wird durch XOR-Verknüpfung mit der niedrigeren Zahl eine XNOR-Zahl erzeugt.

Beispiel 1

Input: x = 12, y = 5

Output: 6

Anleitung

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

Die chinesische Übersetzung von

Sampe Beispiel 2

lautet:

Sampe Beispiel 2

Input: x = 12, y = 31

Output: 12

Anleitung

(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

Beispiel: C++-Implementierung

Im Programm unten werden alle Bits der höheren Zahl umgeschaltet und dann mit der niedrigeren Zahl XOR-verknüpft.

#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;
}

Ausgabe

XNOR of 5 and 15 = 5

Zeitkomplexität: O(logn), aufgrund des Durchlaufs in der Funktion toggle()

Raumkomplexität: O(1)

Methode 3: Bitmaske

Logisch gesehen ist XNOR die Umkehroperation von XOR, aber wenn eine Zweierkomplementoperation auf XOR durchgeführt wird, werden führende Nullen ebenfalls invertiert. Um dies zu vermeiden, kann eine Bitmaske verwendet werden, um alle unnötigen führenden Bits zu entfernen.

Beispiel Beispiel 1

Input: x = 12, y = 5

Output: 6

Anleitung

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

Beispiel 2

Input: x = 12, y = 31

Output: 12

Anleitung

(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

Beispiel: C++-Implementierung

Im folgenden Programm wird die Bitmaske verwendet, um nur die erforderlichen Bits aus der Umkehrung von x x oder y zu erhalten.

#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;
}

Ausgabe

XNOR of 10 and 10 = 7

Fazit

Zusammenfassend lässt sich sagen, dass das XNOR zweier Zahlen mit einer Vielzahl von Methoden und zeitlicher Komplexität ermittelt werden kann, die von O(logn)-Brute-Force-Methoden bis hin zu O(1)-Optimalmethoden reichen. Die Anwendung bitweiser Operationen ist kostengünstiger, daher ist die Komplexität von Brute Force logarithmisch.

Das obige ist der detaillierte Inhalt vonXNOR von zwei Zahlen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!