Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, 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.

这道题是一道典型的位操作Bit Manipulation的题目，我开始以为异或值最大的两个数一定包括数组的最大值，但是OJ给了另一个例子{10,23,20,18,28}，这个数组的异或最大值是10和20异或，得到30。那么只能另辟蹊径，正确的做法是按位遍历，题目中给定了数字的返回不会超过231,那么最多只能有32位，我们用一个从左往右的mask，用来提取数字的前缀，然后将其都存入HashSet中，我们用一个变量t，用来验证当前位为1再或上之前结果res，看结果和HashSet中的前缀异或之后在不在HashSet中，这里用到了一个性质，若a^b=c，那么a=b^c，因为t是我们要验证的当前最大值，所以我们遍历HashSet中的数时，和t异或后的结果仍在HashSet中，说明两个前缀可以异或出t的值，所以我们更新res为t，继续遍历，如果上述讲解不容易理解，那么建议自己带个例子一步一步试试，并把每次循环中HashSet中所有的数字都打印出来，基本应该就能理解了，算了，还是博主带着大家来看题目中给的例子吧：

3        10        5        25        2        8

11      1010     101     11001     10      1000

我们观察这些数字最大的为25，其二进制最高位在 i=4 时为1，那么我们的循环[31, 5]之间是取不到任何数字的，所以不会对结果res有任何影响。

当 i=4 时，我们此时mask为前28位为‘1’的二进制数，跟除25以外的任何数相‘与’，都会得到0。 然后跟25的二进制数10101相‘与’，得到二进制数10000，存入HashSet中，那么此时HashSet中就有0和16两个数字。此时我们的t为结果res（此时为0）‘或’上二进制数10000，得到二进制数10000。然后我们遍历HashSet，由于HashSet是无序的，所以我们会取出0和16中的其中一个，如果prefix取出的是0，那么t=16‘异或’上0，还等于16，而16是在HashSet中存在的，所以此时结果res更新为16，然后break掉遍历HashSet的循环。实际上prefix先取16的话也一样，那么t=16‘异或’上16，等于0，而0是在HashSet中存在的，所以此时结果res更新为16，然后break掉遍历HashSet的循环。

3        10        5        25        2        8

11      1010     101     11001     10      1000

当 i=3 时，我们此时mask为前29位为‘1’的二进制数，如上所示，跟数字3，5，2中任何一个相‘与’，都会得到0。然后跟10的二进制数1010，或跟8的二进制数1000相‘与’，都会得到二进制数1000，即8。跟25的二进制数11001相‘与’，会得到二进数11000，即24，存入HashSet中，那么此时HashSet中就有0，8，和24三个数字。此时我们的t为结果res（此时为16）‘或’上二进制数1000，得到二进制数11000，即24。此时遍历HashSet中的数，当prefix取出0，那么t=24‘异或’上0，还等于24，而24是在HashSet中存在的，所以此时结果res更新为24，然后break掉遍历HashSet的循环。大家可以尝试其他的数，当prefix取出24，其实也可以更新结果res为24的。但是8就不行啦，因为HashSet中没有16。不过无所谓了，我们只要有一个能更新结果res就可以了。

3        10        5        25        2        8

11      1010     101     11001     10      1000

当 i=2 时，我们此时mask为前30位为‘1’的二进制数，如上所示，跟3的二进制数11相‘与’，会得到二进制数0，即0。然后跟10的二进制数1010相‘与’，会得到二进制数1000，即8。然后跟5的二进制数101相‘与’，会得到二进制数100，即4。然后跟25的二进制数11001相‘与’，会得到二进制数11000，即24。跟数字2和8相‘与’，分别会得到0和8，跟前面重复了。所以最终HashSet中就有0，4，8，和24这四个数字。此时我们的t为结果res（此时为24）‘或’上二进制数100，得到二进制数11100，即28。那么就要验证结果res能否取到28。我们遍历HashSet，当prefix取出0，那么t=28‘异或’上0，还等于28，但是HashSet中没有28，所以不行。当prefix取出4，那么t=28‘异或’上二进制数100，等于24，在HashSet中存在，Bingo！结果res更新为28。其他的数可以不用试了。

3        10        5        25        2        8

11      1010     101     11001     10      1000

当 i=1 时，我们此时mask为前31位为‘1’的二进制数，如上所示，每个数与mask相‘与’后，我们HashSet中会有2，4，8，10，24这五个数。此时我们的t为结果res（此时为28）‘或’上二进制数10，得到二进制数11110，即30。那么就要验证结果res能否取到30。我们遍历HashSet，当prefix取出2，那么t=30‘异或’上2，等于28，但是HashSet中没有28，所以不行。当prefix取出4，那么t=30‘异或’上4，等于26，但是HashSet中没有26，所以不行。当prefix取出8，那么t=30‘异或’上8，等于22，但是HashSet中没有22，所以不行。当prefix取出10，那么t=30‘异或’上10，等于20，但是HashSet中没有20，所以不行。当prefix取出24，那么t=30‘异或’上24，等于6，但是HashSet中没有6，所以不行。遍历完了HashSet所有的数，结果res没有被更新，还是28。

3        10        5        25        2        8

11      1010     101     11001     10      1000

当 i=0 时，我们此时mask为前32位为‘1’的二进制数，如上所示，每个数与mask相‘与’后，我们HashSet中会有2，3，5，8，10，25这六个数。此时我们的t为结果res（此时为28）‘或’上二进制数1，得到二进制数11101，即29。那么就要验证结果res能否取到29。取出HashSet中每一个数字来验证，跟上面的验证方法相同，这里博主偷懒就不写了，最终可以发现，结果res无法被更新，还是28，所以最终的结果就是28。

综上所述，我们来分析一下这道题的核心。我们希望用二进制来拼出结果的数，最终结果28的二进制数为11100，里面有三个‘1’，我们来找一下都是谁贡献了这三个‘1’？在 i=4 时，数字25贡献了最高位的‘1’，在 i=3 时，数字25贡献了次高位的‘1’，在 i=2 时，数字5贡献了第三位的‘1’。而一旦某个数贡献了‘1’，那么之后在需要贡献‘1’的时候，此数就可以再继续贡献‘1’。而一旦有两个数贡献了‘1’后，那么之后的‘1’就基本上只跟这两个数有关了，其他数字有‘1’也贡献不出来。验证方法里使用了前面提到的性质，a ^ b = t，如果t是所求结果话，我们可以先假定一个t，然后验证，如果a ^ t = b成立，说明该t可以通过a和b‘异或’得到。参见代码如下：

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int res = 0, mask = 0;
        for (int i = 31; i >= 0; --i) {
            mask |= (1 << i);
            unordered_set<int> s;
            for (int num : nums) {
                s.insert(num & mask);
            }
            int t = res | (1 << i);
            for (int prefix : s) {
                if (s.count(t ^ prefix)) {
                    res = t;
                    break;
                }
            }
        }
        return res;
    }
};

参考资料：

https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap

LeetCode All in One 题目讲解汇总(持续更新中...)