【特别好】【位运算】maximum-xor-of-two-numbers-in-an-array

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 rightfor (int i=31; i>=0; i--) {Set<Integer> prefixSet = new HashSet();// flag : 11110000flag = flag | (1<<i);for (int num : nums) {prefixSet.add(num & flag);}// tmp, max: 10101000000, add more 1 int tmp = max | (1<<i);for (int prefix : prefixSet) {// 利用了 ^ 的 a ^ b = c，则 b ^ c = aif (prefixSet.contains(tmp ^ prefix)) {max = tmp;break;}}}return max;} }

 

总结

以上是生活随笔为你收集整理的【特别好】【位运算】maximum-xor-of-two-numbers-in-an-array的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。