| Submit | All submissions | Best solutions | Back to list |
AKVLKO01 - A XOR Problem |
Let us suppose we have a “N” bit integer X. We call an integer X’ as neighbor-X, if X’ can be obtained by shuffling the bits of integer X.
For example If X = 6 and N = 5, then X will be represented as X = (00110)2, So all the 5 bit integers that have exactly two 1s in their binary representation are called neighbor-X. For example (00011)2, (01001)2, (10100)2, ... all of these are neighbor-X.
Now you are given two N bit integers “X” and “Y”, then you have to find the maximum possible value of (X’ xor Y’) where X’ is neighbor-X.
xor operator takes two bit strings and performs XOR operation between them. For example:
(10010)2 xor (01011)2 = (11001)2
Input
The first line of the input will contain an integer “T”, the number of test cases. Each of the next “T” lines will contain three integers “N”, “X” and “Y”, N is the number of bits in integers X and Y.
Output
For each test case you have to print the maximum possible value of (X’ xor Y’) in a separate line.
Constraints
1 <= T <= 50
1 <= N <= 30
0 <= X, Y < 2^N
Example
Input: 3 3 5 4 5 0 1 4 3 7 Output: 7 16 14
Explanation
In the first case X = 5 = (101)2 and Y = 4 = (100)2, So we can have X' = (101)2 and Y' = (010)2, X' xor Y' = (111)2 = 7
In the second case X = 0 = (00000)2 and Y = 1 = (00001)2, So we can have X' = (00000)2 and Y' = (10000)2, X' xor Y' = (10000)2 = 16
In the third case X = 3 = (0011)2 and Y = 7 = (0111)2, So we can have X' = (0011)2 and Y' = (1101)2, X' xor Y' = (1110)2 = 14
| Added by: | Ankit Kumar Vats |
| Date: | 2013-08-27 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
RSS