将两个数字的二进制表示长度相等后进行异或运算

---

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