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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。