將兩個數字的二進位制表示長度相等後進行異或運算

---

異或 (XOR) 是一種布林邏輯運算，用於生成用於錯誤檢查、容錯等的奇偶校驗位。各種符號用於表示此運算：^、⊕、⊻ 等。

異或邏輯

只有當兩個引數不同時，異或運算才為真。這意味著相同位的異或結果為 0，不同位的異或結果為 1。

相同位 −

0 ^ 0 = 0

1 ^ 1 = 0

不同位 −

0 ^ 1 = 1

1 ^ 0 = 1

問題陳述

給定兩個數字 a 和 b，在將它們的二進位制表示長度相等後，找出它們的異或結果。

提示 − 透過向較小的數字新增尾隨零來使二進位制表示長度相等。

示例

輸入 −

a = 10, b = 5

輸出 − 0

0

解釋

10 的二進位制表示為 1010，5 的二進位制表示為 101。

向 5 新增一個尾隨零使其變為 1010。

因此，1010 ^ 1010 = 0。

這就是輸出結果。

輸入 −

a = 15, b = 8

輸出 − 7

7

解釋 −

15 的二進位制表示為 1111，8 的二進位制表示為 1000。

由於兩個二進位制表示的長度相等，不需要新增尾隨零。

1111 ^ 1000 = 0111，其十進位制表示為 7。 因此，輸出結果為 7。

輸入 −

a = 15, b = 3

輸出 − 7

7

解釋 −

15 的二進位制表示為 1111。3 的二進位制表示為 11。在 3 的二進位制表示中新增尾隨零後，它變為 1100。

1111 ^ 1100 = 0011。

0011 的十進位制表示為 3。因此，輸出結果為 3。

方法

• 計算兩個數字的位數。

• 位數可以透過右移數字直到它變為零，並計算迴圈執行的次數來計算。將數字右移 1 等效於將其除以二。

• 如果較小數字的位數較少，則進行左移操作，如下所示：smaller_number << (exceeding bits)。它將向較小數字新增與超出位數相等的尾隨零。現在兩個數字的位數相等。

• 對兩個數字進行異或運算以獲得答案並列印它。

虛擬碼

main()
Initialize a -> 15  and  b -> 3.
Function call find_xor(a,b);

find_xor(int a, int b):
c -> minimum of a and b.
d -> maximum of a and b.
count_c -> bit_count(c)
count_d ->bit_count(d)
If count_c < cound_d, then:
c -> c << (count_d - count_c)
Return c XOR d.

bit_count(int x):
count -> 0
while(x != 0):
	Increase the count by one.
	Right shift x by 1, i.e., divide it by 2.
Return x.

示例

下面是一個 C++ 程式，用於計算在將兩個數字的二進位制表示長度相等後它們的異或結果。

#include <bits/stdc++.h>
using namespace std;
// Function to count the number of bits in binary representation
// of an integer
int bit_count(int x){
   //Initialize count as zero
   int count = 0;
   //Count the bits till x becomes zero.
   while (x)	{
      //Incrementing the count
	  count++;
      // right shift x by 1
      // i.e, divide by 2
      x = x>>1;
   }
   return count;
}
//Function to find the XOR of two numbers. Trailing zeros are added to the number having a lesser number of bits to make the bits in both numbers equal.
int find_xor(int a, int b){
   //Store the minimum and maximum of both the numbers
   int c = min(a,b);
   int d = max(a,b);
   //Store the number of bits in both numbers.
   int count_c = bit_count(c);
   int count_d = bit_count(d);
   //If the number of bits in c is less, left shift if by the number of exceeding bits.
   if (count_c < count_d){
      c = c << ( count_d - count_c);
   }
   return (c^d);
}
//Driver code
int main(){
   //Initialize a and b.
   int a = 15, b = 3;
   cout << "a = 15, b = 3" << endl;
   //Store the XOR of both the numbers after required computations
   //Function call
   int ans = find_xor(a,b);
   //Print the final result
   cout << "XOR of a and b: "<<ans<<endl;
   return 0;
}

輸出

a = 15, b = 3
XOR of a and b: 3

分析

時間複雜度 − O(log n) [對數]

由於 count 函式中的 while 迴圈，時間複雜度是對數的。

由於數字被除以二直到它變為零，所以複雜度變為以二為底的對數 n。

空間複雜度 − O(1) [常數]

空間複雜度為常數，因為程式中沒有使用額外的空間。

結論

在本文中，我們討論了在將兩個數字的二進位制表示長度相等後計算它們的異或結果的問題。

我們討論了異或的概念，然後透過示例和方法進行了說明。該方法使用尾隨零來使二進位制表示的位數相等。我們還看到了該問題的虛擬碼和 C++ 程式。