XNOR daripada dua nombor

Gat XNOR (XNOR) ialah get logik digital yang menerima dua input dan memberikan satu output. Fungsinya ialah pelengkap logik gerbang OR (XOR) eksklusif. Keluaran adalah BENAR jika kedua-dua input adalah sama; Jadual kebenaran get XNOR diberikan di bawah.

satu	B	Output
1	1	1
1	0	0
0	1	0
0	0	1

Pernyataan Masalah

Diberi dua nombor x dan y. Cari XOR bagi dua nombor.

Contoh Contoh 1

Input: x = 12, y = 5

Output: 6

Arahan

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

Terjemahan Cina bagi

Sampe Contoh 2

ialah:

Sampe Contoh 2

Input: x = 16, y = 16

Output: 31

Arahan

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

Kaedah 1: Kaedah ganas

Kaedah brute force adalah untuk memeriksa setiap bit dua nombor dan membandingkan sama ada ia sama. Jika sama, tambah 1, jika tidak tambah 0.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam atur cara di bawah, semak sama ada bit x dan y adalah sama dan kemudian tetapkan bit dalam jawapan.

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

Output

XNOR of 10 and 11 = 14

Kerumitan masa: O(logn), kerana traversal dilakukan pada semua bit logn.

Kerumitan ruang: O(1)

Kaedah 2

XNOR ialah operasi songsang bagi operasi XOR, dan jadual kebenarannya juga ialah operasi songsang bagi jadual XOR. Jadi menukar bit nombor yang lebih tinggi, iaitu menetapkan 1 kepada 0 dan 0 kepada 1, kemudian XOR dengan nombor yang lebih rendah akan menghasilkan nombor XNOR.

Contoh 1

Input: x = 12, y = 5

Output: 6

Arahan

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

Terjemahan Cina bagi

Sampe Contoh 2

ialah:

Sampe Contoh 2

Input: x = 12, y = 31

Output: 12

Arahan

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

pseudokod

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

Contoh: Pelaksanaan C++

Dalam program di bawah, semua bit nombor yang lebih tinggi ditogol dan kemudian XOR dengan nombor yang lebih rendah.

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

Output

XNOR of 5 and 15 = 5

Kerumitan masa: O(log masuk), disebabkan oleh traversal dalam fungsi togol()

Kerumitan ruang: O(1)

Kaedah 3: Topeng Bit

Secara logiknya, XNOR ialah operasi songsang XOR, tetapi apabila melakukan operasi pelengkap dua pada XOR, sifar pendahuluan juga terbalik. Untuk mengelakkan ini, topeng sedikit boleh digunakan untuk mengeluarkan semua bit utama yang tidak perlu.

Contoh Contoh 1

Input: x = 12, y = 5

Output: 6

Arahan

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

Contoh 2

Input: x = 12, y = 31

Output: 12

Arahan

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

pseudokod

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

Contoh: Pelaksanaan C++

Dalam program di bawah, topeng bit digunakan untuk mendapatkan hanya bit yang diperlukan daripada songsangan 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;
}

Output

XNOR of 10 and 10 = 7

Kesimpulan

Ringkasnya, XNOR dua nombor boleh didapati menggunakan pelbagai kaedah dan kerumitan masa, daripada kaedah kekerasan O(logn) hingga kaedah optimum O(1). Menggunakan operasi bitwise adalah lebih murah, jadi kerumitan kaedah brute force adalah logaritma.

Atas ialah kandungan terperinci XNOR daripada dua nombor. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!