题目来源
感觉很巧妙的一道题，一个数组中，任取两个元素，求最大的异或和，要求O(n)的做法。我这种渣渣只能想到n方的做法…
看了好久答案才理解。
首先了解一个知识点，假如
A XOR B = C then
A XOR C = B and
B XOR C = A
然后整数类型最多31位，所以从高往低，用&操作来截取高位，然后通过上面这个知识点来判断当前位是否存在两个数异或使得当前位为1，并且高位的那些还是保持原来的。
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int mask = 0, maximum = 0;
for (int i=31; i>=0; i--) {
mask |= 1 << i;
unordered_set<int> prefixs;
for (auto num : nums)
prefixs.insert(num & mask);
int tmp = maximum | 1 << i;
for (auto prefix : prefixs)
if (prefixs.count(tmp ^ prefix)) {
maximum = tmp;
break;
}
}
return maximum;
}
};
