Maximizing XOR HackerRank Solution

Maximizing XOR HackerRank Solution
Source : https://www.hackerrank.com/challenges/maximizing-xor

Given two integers, and , find the maximal value of xor , written , where and satisfy the following condition:

For example, if and , then

Our maximum value is .

Function Description

Complete the maximizingXor function in the editor below. It must return an integer representing the maximum value calculated.

maximizingXor has the following parameter(s):

• l: an integer, the lower bound, inclusive
• r: an integer, the upper bound, inclusive

Input Format

The first line contains the integer .
The second line contains the integer .

Constraints

³

Output Format

Return the maximal value of the xor operations for all permutations of the integers from to , inclusive.

Sample Input 0

1015

Sample Output 0

7

Explanation 0

The input tells us that and . All the pairs which comply to above condition are the following:





















Here two pairs (10, 13) and (11, 12) have maximum xor value 7, and this is the answer.

Sample Input 1

11100

Sample Output 1

127

Source : https://www.hackerrank.com/challenges/maximizing-xor

Solution

	// Karthikalapati.blogspot.com
	// To maximize A xor B, we want A and B to differ as much as possible at every bit index.
	// We first find the most significant bit that we can force to differ by looking at L and R.
	// For all of the lesser significant bits in A and B, we can always ensure that they differ
	// and still have L <= A <= B <= R. Our final answer will be the number represented by all
	// 1s starting from the most significant bit that differs between A and B
	// Example:
	// L = 10111
	// R = 11100
	// _X___ <-- that's most significant differing bit
	// 01111 <-- here's our final answer
	//
	// Notice that we never directly calculate the values of A and B
	static int maximizingXor(int L, int R) {
	int xored = L ^ R;
	int significantBit = 31 - Integer.numberOfLeadingZeros(xored);
	int result = (1 << (significantBit + 1)) - 1;
	return result;
	}
	// Discuss on HackerRank: https://www.hackerrank.com/challenges/maximizing-xor/forum/comments/284317