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++程序。
