> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/bit-manipulation/xor/maximum-xor-of-two-numbers-in-an-array.md).

# Maximum XOR of Two Numbers in an Array

<https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/>

> 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.
>
> Example:
>
> Input: \[3, 10, 5, 25, 2, 8]
>
> Output: 28
>
> Explanation: The maximum result is 5 ^ 25 = 28.

## Thoughts

<https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/>

想让一个二进制数尽量大, 那么应从高位起尽量让它们为1. 并且当高位为1时, 即使低位为0, 也比低位为1的高位为0的大. 因此我们依次从高位到低位遍历, 判断该位是否能为1, 并且利用之前高位中找出的候选者不断筛选. 比如 \[110011, 110010, 010111], 当遍历到第二位时, 即使110011第二位为0, 010111第二位为1, 后者也不用再考虑了. 于是我们可以设置一个candidate表示遍历到i位时, 理想中能达到的最大的数: candidate前i - 1位为前i - 1位中能达到的数, 第i位理想情况下是1. 所以任务变为判断是否有两个数到i位时的prefix相xor能成为candidate. 这时利用xor的性质, 即当a ^ b = candidate时, 有a ^ candidate = b 且 b ^ candidate = a.

## Code

```
class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        // 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--) {
            // the mask woule be 1000..., 11000..., 111000...
            mask |= (1 << i);
            //System.out.println(Integer.toBinaryString(mask));
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                // store prefix of all number with right i bits discarded
                set.add(num & mask);
                //System.out.println(num + "," + Integer.toBinaryString(num) + ": " + Integer.toBinaryString(mask) + "," + Integer.toBinaryString(mask & num));
            }
            // 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 : set) {
                if (set.contains(candidate ^ prefix)) {
                    max = candidate;
                    break;
                }
            }
        }

        return max;
    }
}
```

## Analysis

时间复杂度O(N).