We need to maximise the xor between 'small' and 'high'.
So let's take an example to understand this.
5 xor 2 = 101 xor 010
first case: MSB bit is not set for both the values in the range.If want to maximimize this then what we need to do is to keep the MSB of 5 (100) as it is and think about maximizing the remaining lower bits. As we know that lower bits
all will be one for the case when everything is 11 which is nothing but 3 i.e. 2^2-1. Since the problem is talking about the range between 2 to 5 we defintely have 3 in the range. So all we need to do is to find out the highest MSB
set in the larger of 2 values and add the remaining 1's for
the lower bits.
second case: As for the case when MSB is set for both the values in the range
doing xor will defintely have those bits set as 0 and we need to go back to lower bits. Again for lower bits we need to repeat the same logic as first case.
example: (10, 12) (1010, 1100)
As you can see both have MSB set as 1 then we have to go back to
lower bits which is 010 and 100. Now this problem is same as the
There are several ways to code this. What I did is to do just the xor between
'small' and 'high' and that will remove MSB bit if both 'small' and 'high' have MSB bit set. Incase that is not the case then it will preserve the MSB bit. After that I am trying to make all lower bits 1's by finding out the maximum power of 2 in the xored output and subtracting from 1.
def range_xor_max(small, high):
if small == high:
xor = small ^ high
#how many power of 2 is present
how_many_power_of_2 = math.log(xor, 2)
#we need to make all one's below the highest set bit
return 2**int(math.floor(how_many_power_of_2)+1) - 1