Given two numbers A, B, What is the maximum value of A' XOR B', where A', B' are obtained by permuting the binary representations of A, B respectively.
For example assume A = 3, B = 1 and they are represented in 4 bits. A = 0011, B = 0001 in binary. Suppose A' = 1100, B' = 0010, then we get the A' ^ B' = 1110 = 13. So 13 is the answer. For no other values of A’, B’, the XOR will be maximum.
Let us look at another example A = 3, B = 7, again represented using 4 bits. A' = 0011, B' = 1101 and A' ^ B' = 0011 ^ 1101 = 1110 = 14. So 14 is the answer.
This problem was originally appeared on Codechef. The problem has 3 inputs N (number of bits), A, B. How many 1s are possible in the result number?
Since 1^0 = 1 and 0^1 = 1, to get a 1 in the final result, We should have a
- 1 bit in A, and 0 bit in B or
- 0 bit in A, and 1 bit in B
So the total number 1s possible in the result is Minimum( 1s in A, 0s in B) + Minimum( 0s in A, 1s in B). The remaining bits are Zeros.
How should we arrange these bits to get the maximum value? All 1s should be pushed to left (Most significant bits). So the result will be of the form 1111…00
Here is the Java code which implements the above approach.