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.
Why this works.. this looks for highest bit which is different between l and r: for example (11, 12) that is third bit with value 4.. all bits above it are identical in both l and r, and you can not produce any l<=a<=b<=r which have non zero result of a^b.
But you can find value a which has third bit zero and all remaining bits set (11 in this example), and b = a + 1 will clear all lower bits and set third bit, so a^b is all ones from highest difference bit down to bottom bit = maximum xor difference. qed.
Maximizing XOR
You are viewing a single comment's thread. Return to all comments →
C++ O(1) solution:
Why this works.. this looks for highest bit which is different between l and r: for example (11, 12) that is third bit with value 4.. all bits above it are identical in both l and r, and you can not produce any l<=a<=b<=r which have non zero result of a^b. But you can find value a which has third bit zero and all remaining bits set (11 in this example), and b = a + 1 will clear all lower bits and set third bit, so a^b is all ones from highest difference bit down to bottom bit = maximum xor difference. qed.