The XNOR (XNOR) gate is a digital logic gate that accepts two inputs and gives one output. Its function is the logical complement of the exclusive OR (XOR) gate. The output is TRUE if the two inputs are the same; FALSE if the inputs are different. The truth table of the XNOR gate is given below.
| one | B | Output |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Given two numbers x and y. Find the XOR of two numbers.
Input: x = 12, y = 5
Output: 6
(12)10 = (1100)2 (5)10 = (101)2 XNOR = (110)2 = (6)10
Input: x = 16, y = 16
Output: 31
(16)10 = (10000)2 (16)10 = (10000)2 XNOR = (11111)2 = (31)10
The brute force method is to check every bit of the two numbers and compare whether they are the same. If they are the same, add 1, otherwise add 0.
procedure xnor (x, y) if x > y then swap(x,y) end if if x == 0 and y == 0 then ans = 1 end if while x x_rem = x & 1 y_rem = y & 1 if x_rem == y_rem then ans = ans | (1 << count) end if count = count + 1 x = x >> 1 y = y >> 1 end procedure
In the following program, check if the bits of x and y are the same, then set the bits in the answer.
#includeusing namespace std; // Function to swap values of two variables void swap(int *a, int *b){ int temp = *a; *a = *b; *b = temp; } // Function to find the XNOR of two numbers int xnor(int x, int y){ // Placing the lower number in variable x if (x > y){ swap(x, y); } // Base Condition if (x == 0 && y == 0){ return 1; } // Cnt for counting the bit position Ans stores ans sets the bits of XNOR operation int cnt = 0, ans = 0; // executing loop for all the set bits in the lower number while (x){ // Gets the last bit of x and y int x_rem = x & 1, y_rem = y & 1; // If last bits of x and y are same if (x_rem == y_rem){ ans |= (1 << cnt); } // Increase counter for bit position and right shift both x and y cnt++; x = x >> 1; y = y >> 1; } return ans; } int main(){ int x = 10, y = 11; cout << "XNOR of " << x << " and " << y << " = " << xnor(x, y); return 0; }
XNOR of 10 and 11 = 14
Time complexity: O(logn), because the traversal is performed on all logn bits.
Space complexity: O(1)
XNOR is the inverse operation of the XOR operation, and its truth table is also the inverse operation of the XOR table. So switching the bits of the higher number, i.e. setting 1 to 0 and 0 to 1, then XORing with the lower number will produce an XNOR number.
Input: x = 12, y = 5
Output: 6
(12)10 = (1100)2 (5)10 = (101)2 Toggled bits of 12 = 0011 0011 ^ 101 = 0110
Input: x = 12, y = 31
Output: 12
(12)10 = (1100)2 (31)10 = (11111)2 Toggled bits of 31 = 00000 00000 ^ 1100 = 01100
procedure toggle (n) temp = 1 while temp <= n n = n ^ temp temp = temp << 1 end procedure procedure xnor (x, y) max_num = max(x,y) min_num = min(x,y) toggle (max_num) ans = max_num ^ min_num end procedure
In the program below, all bits of the higher number are toggled and then XORed with the lower number.
#includeusing namespace std; // Function to toggle all bits of a number void toggle(int &num){ int temp = 1; // Execute loop until set bit of temp cross MST of num while (temp <= num){ // Toggle bit of num corresponding to set bit in temp num ^= temp; // Move set bit of temp to left temp <<= 1; } } // Function to find the XNOR of two numbers int xnor(int x, int y){ // Finding max and min number int max_num = max(x, y), min_num = min(x, y); // Togglinf the max number toggle(max_num); // XORing toggled max num and min num return max_num ^ min_num; } int main(){ int x = 5, y = 15; cout << "XNOR of " << x << " and " << y << " = " << xnor(x, y); return 0; }
XNOR of 5 and 15 = 5
Time complexity: O(logn), due to traversal in the toggle() function
Space complexity: O(1)
Logically speaking, XNOR is the inverse operation of XOR, but when performing a complement operation on XOR, leading zeros will also be inverted. To avoid this, a bit mask can be used to remove all unnecessary leading bits.
Input: x = 12, y = 5
Output: 6
(12)10 = (1100)2 (5)10 = (101)2 1100 ^ 101 = 1001 Inverse of 1001 = 0110
Input: x = 12, y = 31
Output: 12
(12)10 = (1100)2 (31)10 = (11111)2 1100 ^ 11111 = 10011 Inverse of 10011 = 01100
Procedure xnor (x, y) bit_count = log2 (maximum of a and y) mask = (1 << bit_count) - 1 ans = inverse(x xor y) and mask end procedure
In the following program, a bit mask is used to get only the required bits from the inverse of x xor y.
#includeusing namespace std; // Function to find the XNOR of two numbers int xnor(int x, int y){ // Maximum number of bits used in both the numbers int bit_count = log2(max(x, y)); int mask = (1 << bit_count) - 1; // Inverse of XOR operation int inv_xor = ~(x ^ y); // GEtting the required bits and removing the inversion of leading zeroes. return inv_xor & mask; } int main(){ int x = 10, y = 10; cout << "XNOR of " << x << " and " << y << " = " << xnor(x, y); return 0; }
XNOR of 10 and 10 = 7
In summary, the XNOR of two numbers can be found using a variety of methods and time complexity, ranging from O(logn) brute force methods to O(1) optimal methods. Applying bitwise operations is cheaper, so the complexity of the brute force method is logarithmic.
The above is the detailed content of XNOR of two numbers. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
