421. Maximum XOR of Two Numbers in an Array

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.

题目希望找到两个数的XOR最大。

求数组中两两数字的异或运算的最大值，brute force的解法是O(n ^ 2)，

怎么样才能XOR最大呢？我们从最大bit位上面看，如果有0，有1那么这位可以在答案中加上。

nums中，与mask按位与结果为0的所有数字，记为nums0

nums中，与mask按位与结果为1的所有数字，记为nums1

如果nums0与nums1其一为空，说明nums中所有数字在该二进制位同0或同1，其异或结果一定为0

如果nums0与nums1均不为空，说明nums中的数字在该位的异或值为1，令mask右移一位，再将nums0与nums1进一步划分成四部分：

nums0中，与mask按位与结果为0的所有数字，记为nums00

nums0中，与mask按位与结果为1的所有数字，记为nums01

nums1中，与mask按位与结果为0的所有数字，记为nums10

nums1中，与mask按位与结果为1的所有数字，记为nums11

分治法（Divide and Conquer）+ 位运算（Bit Manipulation）就是上面分析过程引用bookshadow的解法http://bookshadow.com/weblog/2016/10/15/leetcode-maximum-xor-of-two-numbers-in-an-array/

2.
一个比较直观的解法，用prefix Trie
对于每一个num来说，看它会不会构成最后的结果，就是看它的sibling有没有，如果有sibling，那么这位xor的结果就是1，不然xor的结果是0.对个num都做一遍，然后去取最大的值。https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie/2


3. 构造这个xor结果

example: Given [14, 11, 7, 2], which in binary are [1110, 1011, 0111, 0010].
Since the MSB is 3, I'll start from i = 3 to make it simplify.

1. i = 3, set = {1000, 0000}, max = 1000  
2. i = 2, set = {1100, 1000, 0100, 0000}, max = 1100  -> 1110 0010 或者 1100 0010 或者 1010 0100 或者 1000 0110 都可以构成1110
3. i = 1, set = {1110, 1010, 0110, 0011}, max = 1100
4. i = 0, set = {1110, 1011, 0111, 0011}, max = 1101

外循环是31～0
因此每一位的比较，我们还需要知道前边那些位，比如我们这轮儿想要知道答案有没有111X（因为我们已经知道有11XX）因此我们取出每个数前3个bit位放入set。在set中利用想要知道的结果来找另一半。（x^y = z --> x^z = y   =》 x^y =  max(理想的) --> x^max = y)）

int findMaximumXOR(vector<int>& nums) {
        int max = 0, mask = 0;
        unordered_set<int> t;
        // search from left to right, find out for each bit is there 
        // two numbers that has different value
        for (int i = 31; i >= 0; i--){
            // mask contains the bits considered so far
            mask |= (1 << i);
            t.clear();
            // store prefix of all number with right i bits discarded
            for (int n: nums){
                t.insert(mask & n);
            }
            
            // now find out if there are two prefix with different i-th bit
            // if there is, the new max should be current max with one 1 bit at i-th position, which is candidate
            // and the two prefix, say A and B, satisfies:
            // A ^ B = candidate
            // so we also have A ^ candidate = B or B ^ candidate = A
            // thus we can use this method to find out if such A and B exists in the set 
            int candidate = max | (1<<i);
            for (int prefix : t){
                if (t.find(prefix ^ candidate) != t.end()){
                    max = candidate;
                    break;
                }
                
            }
        }
        return max;
    }

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