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

Easy
0/40
Average time to solve is 20m
profile
Contributed by
22 upvotes
Asked in companies
OptumUrban Company (UrbanClap)American Express

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
16
Sample Output 1:
2305843009213693935
Explanation for sample input 1:
The XOR of numbers 16 and 2305843009213693935 equals 2305843009213693951, which is the maximum allowed XOR value.
Sample Input 2:
1
0
Sample Output 2:
2305843009213693951
Approaches (1)
Bits Manipulation and properties of bitwise XOR
  • 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. 1^0 = 1.
  2. 0^1 = 1.
  3. 0^0 = 0.
  4. 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.
Time Complexity

O(1), as all operations take constant time.

Space Complexity

O(1), as we are using constant extra memory.

Code Solution
(100% EXP penalty)
Find a value whose XOR with a given value is maximum.
Full screen
Console