首頁 > 後端開發 > C++ > 主體

兩個數字的XNOR

WBOY
發布: 2023-09-09 20:33:04
轉載
683 人瀏覽過

兩個數字的XNOR

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)的最佳化方法。應用位運算更廉價,因此暴力法的複雜度是對數等級的。

以上是兩個數字的XNOR的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:tutorialspoint.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板