C++ 两个数字的逻辑非或运算

逻辑非或（XNOR）门是一种数字逻辑门，它接受两个输入并给出一个输出。它的功能是逻辑异或（XOR）门的逻辑补。如果两个输入相同，输出为TRUE；如果输入不同，输出为FALSE。XNOR门的真值表如下所示。

A	B	Output
1	1	1
1	0	0
0	1	0
0	0	1

问题说明

给定两个数x和y。找出这两个数的XNOR。

示例1

Input: x = 12, y = 5

Output: 6

解释

(12)10 = (1100)2
(5)10 = (101)2
XNOR = (110)2 = (6)10

示例2

Input: x = 16, y = 16

Output: 31

解释

(16)10 = (10000)2
(16)10 = (10000)2
XNOR = (11111)2 = (31)10

方法1：蛮力法

蛮力法将检查两个数字的每一位，并比较它们是否相同。如果它们相同，就放置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)

方法2

XNOR是XOR操作的反向操作，它的真值表也是XOR表的反向。因此，将高位数字的位取反（将1设置为0，将0设置为1），然后与低位数字进行XOR运算将得到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

示例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 #){
   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

时间复杂度：由于在toggle()函数中进行遍历，所以为O(logn)

空间复杂度：O(1)

方法3：位掩码

逻辑上，XNOR是XOR的反向操作，但是在执行XOR的补码时，前导零也会被反转。为了避免这种情况，使用位掩码来移除所有不必要的前导位。

示例1

Input: x = 12, y = 5

Output: 6

解释

(12)10 = (1100)2
(5)10 = (101)2
1100 ^ 101 = 1001
Inverse of 1001 = 0110

示例2

Input: x = 12, y = 31

Output: 12

解释

(12)10 = (1100)2
(31)10 = (11111)2
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;
}