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.
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
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.
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 of15 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 of15 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.
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.
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.
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; }
a = 15, b = 3 XOR of a and b: 3
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 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!