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

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

異或邏輯

只有當兩個參數不同時，XOR 運算才會為真。也就是說，相同位元異或為0，不同位元異或為1。

相同的位元 -

0^0=0

1^1=0

不同的位元 −

0^1=1

1 ^ 0 = 1

問題陳述

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

提示 − 透過在較小的數字後面加上尾隨的零，二進位表示將變得相等。

範例

輸入 -

a = 10，b = 5

輸出-

0

說明

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

將尾隨零加到 5 就得到 1010。

因此，1010^1010的異或結果為0。

因此，輸出。

輸入 -

a = 15，b = 8

輸出 −

#7

說明 -

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

由於兩個二進位表示的長度相等，因此不需要添加尾部的零。

1111 ^ 1000 的異或結果為 0111，即十進位表示為 7。因此，輸出結果為 7。

輸入 -

a = 15，b = 3

輸出 −

#7

說明 -

15的二進位表示為1111。3的二進位表示為11。3的二進位表示加上尾隨零後，變為1100。

1111^1100的異或結果為0011。

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

方法

• 計算兩個數字中的位數。

• 可以透過將數字右移直到變為零，並計算循環執行的次數來計算位數。將數字右移1位相當於將其除以2。

• 如果較小數字的位數較少，則如下進行左移：smaller_number

• XOR兩個數字以獲得答案並列印出來。

虛擬程式碼

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循環，時間複雜度是對數等級的。

由於這個數字被除以二直到變為零，複雜度變成以2為底的log n。

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

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

結論

在本文中，我們討論了在使兩個數字的二進位表示長度相等後計算它們的 XOR 的問題。

我們討論了XOR的概念，然後進行了範例和方法的解說。此方法使用尾隨零來使二進位表示的位數相等。我們也看到了該問題的偽代碼和C 程式。

以上是將兩個數字的二進位表示長度調整為相等後進行異或運算的詳細內容。更多資訊請關注PHP中文網其他相關文章！