XNOR（异或非）门是一种数字逻辑门，它接受两个输入并给出一个输出。其功能是异或（XOR）门的逻辑补。如果两个输入相同，则输出为 TRUE；如果输入不同，则输出为 FALSE。下面给出了异或非门的真值表。
| 一个 | B | 输出 |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
问题陈述
给定两个数字 x 和 y。求两个数的异或。
示例示例1
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>
Sampe Example 2
的中文翻译为：示例示例2
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
示例：C++ 实现
在下面的程序中，检查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 数字。
示例 1
Input: x = 12, y = 5
Output: 6
说明
(12)10 = (1100)2 (5)10 = (101)2 Toggled bits of 12 = 0011 0011 ^ 101 = 0110
Sampe Example 2
的中文翻译为：示例示例2
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
示例：C++ 实现
在下面的程序中，较高数字的所有位都会被切换，然后与较低数字进行异或。
#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)
方法 3：位掩码
从逻辑上讲，XNOR是XOR的反向操作，但是在对XOR进行补码操作时，前导零也会被反转。为了避免这种情况，可以使用位掩码来去除所有不必要的前导位。
示例示例1
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
示例 2
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
示例：C++ 实现
在下面的程序中，位掩码用于从 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)的最优化方法。应用位运算更加廉价，因此暴力法的复杂度是对数级别的。
