Last Updated: 20 Nov, 2020

Find a value whose XOR with a given value is maximum.

Easy

Asked in companies

Solve now

Problem statement

You are given an integer 'X' and your task is to find an integer 'Y' such that the bitwise XOR of the integers 'X' and 'Y' give the maximum possible value. The integer 'Y' should not be greater than 2305843009213693951 ((2^61) - 1).

A bitwise XOR is a binary operation that takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only one of the bits is 1, but will be 0 if both are 0 or both are 1.

Note:

1. The maximum obtainable value can always be stored in 64-bit memory space.
2. The given number 'X' is always non-negative.

Input Format:

The first line of the input contains an integer 'T' denoting the number of test cases.

The first line and the only line of each test case contains an integer 'X'.

Output Format:

For each test case, print an integer 'Y' whose XOR with 'X' yields the maximum obtainable value in separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10^4
0 <= X <= 10^18

Time Limit: 1sec

Solve now

Approaches

01 Approach

Consider two numbers ‘A’ = 7, ‘B’ = 3. Bitwise representation of ‘A’ = 0 1 1 1, and ‘B’ = 0 0 1 1, as you can see, there is an extra bit set in ‘A’ as compared to ‘B’ and that too at a more significant place, and that is why ‘A’ > ‘B’. This fact clearly proves that the maximum xor value of ‘X’ and some possible ‘Y’ should have the maximum possible bit-positions as set.
In the given problem, the maximum value of XOR of ‘X’ and ‘Y’ will be a value if all bits in the number(up to 61 bit-positions obviously) are set to 1 because this is the best we can have (as we are given that the maximum allowed XOR value can be up to 2^61 - 1.
Using XOR property:

1^0 = 1.
0^1 = 1.
0^0 = 0.
1^1 = 0.

You can observe that the bitwise xor of same bits is 0, while different bits is 1.

If a particular bit in ‘X’ is set, then that bit needs to be unset in ‘Y’ and vice-versa.
We have been given the total no of bits in ‘X’ = 64 bits signed.
We can find the integer ‘Y’ by traversing across all the bits in ‘X’ and checking if that bit is set or unset and setting the corresponding bits in ‘Y’.
The other way to do this is to use the equation: X ^ ( X ^ Y ) = Y.
The maximum XOR ( X ^ Y ) which will be all set bits. E.g. 111111….(61 bits) can be calculated by (1<<61)-1.
To get ‘Y’, XOR the maximum XOR with ‘X’ and return the answer.

Solve now