https://www.hackerrank.com/contests/w1/challenges/maximizing-xor/
找了半天规律,答案竟然是暴力,伤感。我找到的方法是利用规律2^x XOR 2^x - 1会最大,感觉稍微效率高点。
int maxXor(int l, int r) { if (l == r) return 0; int p = 1; for (int i = 0; i <= 10; i++) { if (p * 2 > r) break; p *= 2; } if (p - 1 >= l) return (p - 1) ^ p; else return maxXor(l - p, r - p); }
但事实上有个O(1)的方法:https://www.hackerrank.com/challenges/maximizing-xor/forum/questions/5407 @UlyssesB
2^((L XOR R).bit_length) - 1
其实和我的方法类似,但更高效。就是找出L和R最左边第一个不同的bit,那么之后的部分,肯定有个从类似7=>8 的过程,必然能得到15。