Adjust the binary representation lengths of two numbers to be equal and then perform an XOR operation

XOR, or exclusive OR, is a Boolean logic operation used to generate parity bits for error checking, fault tolerance, etc. Various symbols are used to represent this operation: ^, ⊕, ⊻, etc.

XOR logic

The XOR operation is true only if the two parameters are different. In other words, the XOR of the same bits is 0, and the XOR of different bits is 1.

Same bits -

0^0=0

1^1=0

Different bits −

0^1=1

1 ^ 0 = 1

Problem Statement

Given two numbers a and b, find their exclusive OR after making the lengths of their binary representations equal.

Tip − By adding a trailing zero after the smaller number, the binary representation will become equal.

Example

Input -

a = 10, b = 5

Output-

0

illustrate

The binary representation of 10 is 1010, and the binary representation of 5 is 101.

Add the trailing zero to 5 to get 1010.

Therefore, the XOR result of 1010^1010 is 0.

Therefore, output.

Enter -

a = 15, b = 8

Output −

7

illustrate -

The binary representation of

15 is 1111, and the binary representation of 8 is 1000.

Since the two binary representations are equal in length, there is no need to add trailing zeros.

1111 ^ The XOR result of 1000 is 0111, which is 7 in decimal notation. Therefore, the output is 7.

Enter -

a = 15, b = 3

Output −

7

illustrate -

The binary representation of

15 is 1111. The binary representation of 3 is 11. The binary representation of 3, with a trailing zero, becomes 1100.

The XOR result of 1111^1100 is 0011.

0011 is 3 in decimal representation. Therefore, the result is output.

method

• Calculate the number of digits in two numbers.

• The number of digits can be calculated by shifting the number to the right until it becomes zero, and counting the number of times the loop is executed. Shifting a number to the right by 1 place is equivalent to dividing it by 2.

• If the smaller number has fewer digits, the left shift is performed as follows: smaller_number

• XOR two numbers to get the answer and print it.

pseudocode

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.

Example

The following is a C program for calculating the XOR value of two numbers after making their binary representations equal in length.

#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;
}

Output

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

analyze

Time complexity - O(log n) [logarithm]

Due to the while loop in the count function, the time complexity is logarithmic.

Since this number is divided by two until it becomes zero, the complexity becomes log n base 2.

Space Complexity - O(1) [Constant]

Space complexity is constant because no extra space is used in the program.

in conclusion

In this article, we discussed the problem of computing the XOR of two numbers after making their binary representations equal in length.

We discussed the concept of XOR, and then explained examples and methods. This method uses trailing zeros to equalize the number of bits in the binary representation. We also saw pseudocode and a C program for the problem.

The above is the detailed content of Adjust the binary representation lengths of two numbers to be equal and then perform an XOR operation. For more information, please follow other related articles on the PHP Chinese website!