https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
利用了异或的”自反性“: a ^ b = c,而a ^ b ^ b = a, 则 c ^ b = a
其他运算定律有:交换律、结合律、分配律。
注意:计算使用的结果,不是只看一位,而是每次把新的一位加到原来的结果后面。这样的好处是不需要记录之前的结果满足条件的有哪些,每次就重新计算和查找就可以了,大大降低了复杂度。
// 非常非常棒// 参考了 https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap// 特别的,利用了异或的强大运算特性,见22行,来加速运算public class Solution { public int findMaximumXOR(int[] nums) { int max = 0; int flag = 0; // from left to right for (int i=31; i>=0; i--) { SetprefixSet = new HashSet(); // flag : 11110000 flag = flag | (1<