Given a non-empty array of numbers, a₀, a₁, a₂, … , a_n-1, where 0 ≤ a_i < 2³¹.

Find the maximum result of a_i XOR a_j, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8] 
Output: 28 
Explanation: The maximum result is 5 ^ 25 = 28.

这道题是在刷Explore的Trie tree topic里面看到的。首先一拿到题目，下意识的反应就是这道题没那么简单。最暴力的方法就是穷举遍历了，这样的话time complexity就会达到O(n^2)。

之后联想Trie tree和Binary之间的关系，可以画出上面这个图。这样问题就被转换为了找到最高的具有1节点的父节点，然后向下尽量找a^b = 1的分支 (我感觉我没有说清楚。。。)

之后看了讨论版里一位大佬的题解，真的是颇为震撼。他用了位运算的方法省去了很多不必要的步骤。 其中比较不好理解的是：

result += any(result ^ 1 ^ p in prefixes for p in prefixes)

为了理解这句话，首先我们得知道：a^b^a=b.

在这里result^1 == a^b, p = a, 所以result^1^p = b。如果在prefixes中有任意两个数a,b可以得到result^1, 而且这两个数a,b构成了previous result，那么新的result就可以是result += 1了，不然只能是result <<= 1(末位为0)。

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        result = 0
        
        for i in range(32)[::-1]:
            result <<= 1
            prefixes = {num >> i for num in nums}
            result += any(result ^ 1 ^ p in prefixes for p in prefixes)
            
        return result