We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Designate the bits of a number x in the range as b_i, where b_0 is the least significant bit and b_31 (assuming a 32-bit integer) is the most significant bit. Let b_n be the most significant bit that changes over the range from l to r. Note that if b_n changed from 1 to 0 as we increment x, that would result in a carry to b_n+1, which contradicts b_n being the most significant bit to change. Ergo b_n must be 0 at l, switch to 1 at some point, never switch back, and be 1 at r, and b_n must differ (and be the largest bit that differs) between l and r.
Given that, there must be some x_0 which is the largest number between l and r where b_n is 0, and some x_1 which is the smallest number between l and r where b_n is 1, and x_0 + 1 = x_1. In order to b_n to change when adding 1 to x_0, it must receive a carry from b_n-1, which must in turn receive a carry from b_n-2, and so on down to b_0. Thus in x_0 all the bits from b_0 to b_n-1 must be 1. Correspondingly, after adding 1 all those bits will flip as the carry propagates, so in x_1 all the bits from b_0 to b_n-1 will be 0.
Therefore, we take x_0 ^ x_1. As proven above, all the bits from b_0 to b_n differ between x_0 and x_1, and of course the bits from b_n+1 up do not differ since by assumption they are constant for all x between l and r. Thus we can get a result where all bits up to b_n are 1 in the xor, and as every higher bit must be 0 for any pair of numbers between l and r since those bits never vary this must be maximal.
Maximizing XOR
You are viewing a single comment's thread. Return to all comments →
I can provide a proof.
Designate the bits of a number x in the range as b_i, where b_0 is the least significant bit and b_31 (assuming a 32-bit integer) is the most significant bit. Let b_n be the most significant bit that changes over the range from l to r. Note that if b_n changed from 1 to 0 as we increment x, that would result in a carry to b_n+1, which contradicts b_n being the most significant bit to change. Ergo b_n must be 0 at l, switch to 1 at some point, never switch back, and be 1 at r, and b_n must differ (and be the largest bit that differs) between l and r.
Given that, there must be some x_0 which is the largest number between l and r where b_n is 0, and some x_1 which is the smallest number between l and r where b_n is 1, and x_0 + 1 = x_1. In order to b_n to change when adding 1 to x_0, it must receive a carry from b_n-1, which must in turn receive a carry from b_n-2, and so on down to b_0. Thus in x_0 all the bits from b_0 to b_n-1 must be 1. Correspondingly, after adding 1 all those bits will flip as the carry propagates, so in x_1 all the bits from b_0 to b_n-1 will be 0.
Therefore, we take x_0 ^ x_1. As proven above, all the bits from b_0 to b_n differ between x_0 and x_1, and of course the bits from b_n+1 up do not differ since by assumption they are constant for all x between l and r. Thus we can get a result where all bits up to b_n are 1 in the xor, and as every higher bit must be 0 for any pair of numbers between l and r since those bits never vary this must be maximal.