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。因此，輸出結果。
方法
虛擬程式碼
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中文網其他相關文章！
