XNOR(异或非)门是一种数字逻辑门,它接受两个输入并给出一个输出。其功能是异或(XOR)门的逻辑补。如果两个输入相同,则输出为 TRUE;如果输入不同,则输出为 FALSE。下面给出了异或非门的真值表。
一个 | B | 输出 |
---|---|---|
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 0 | 1 |
给定两个数字 x 和 y。求两个数的异或。
Input: x = 12, y = 5
Output: 6
(12)<sub>10</sub> = (1100)<sub>2</sub> (5)<sub>10</sub> = (101)<sub>2</sub> XNOR = (110)2 = (6)<sub>10</sub>
Input: x = 16, y = 16
Output: 31
(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>
暴力方法是检查两个数字的每一位并比较它们是否相同。如果相同则加1,否则加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
在下面的程序中,检查x和y的位是否相同,然后设置答案中的位。
#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; }
XNOR of 10 and 11 = 14
时间复杂度:O(logn),因为遍历是对所有 logn 位进行的。
空间复杂度:O(1)
XNOR是XOR运算的逆运算,它的真值表也是XOR表的逆运算。因此,切换较高数字的位,即将 1 设置为 0,将 0 设置为 1,然后与较低数字进行异或将产生 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
在下面的程序中,较高数字的所有位都会被切换,然后与较低数字进行异或。
#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; }
XNOR of 5 and 15 = 5
时间复杂度:O(logn),由于在toggle()函数中进行遍历
空间复杂度:O(1)
从逻辑上讲,XNOR是XOR的反向操作,但是在对XOR进行补码操作时,前导零也会被反转。为了避免这种情况,可以使用位掩码来去除所有不必要的前导位。
Input: x = 12, y = 5
Output: 6
(12)<sub>10</sub> = (1100)<sub>2</sub> (5)<sub>10</sub> = (101)<sub>2</sub> 1100 ^ 101 = 1001 Inverse of 1001 = 0110
Input: x = 12, y = 31
Output: 12
(12)<sub>10</sub> = (1100)<sub>2</sub> (31)<sub>10</sub> = (11111)<sub>2</sub> 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
在下面的程序中,位掩码用于从 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; }
XNOR of 10 and 10 = 7
总之,可以使用各种方法和时间复杂度来找到两个数字的XNOR,范围从O(logn)的暴力法到O(1)的最优化方法。应用位运算更加廉价,因此暴力法的复杂度是对数级别的。
以上是两个数字的XNOR的详细内容。更多信息请关注PHP中文网其他相关文章!