[LeetCode] 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:

這道題是一道典型的位操作Bit Manipulation的題目，我開始以為異或值最大的兩個數一定包括數組的最大值，但是OJ給了另一個例子{10,23,20,18,28}，這個數組的異或最大值是10和20異或，得到30。那麼隻能另辟蹊徑，正确的做法是按位周遊，題目中給定了數字的傳回不會超過231,那麼最多隻能有32位，我們用一個從左往右的mask，用來提取數字的字首，然後将其都存入set中，我們用一個變量t，用來驗證目前位為1再或上之前結果res，看結果和set中的字首異或之後在不在set中，這裡用到了一個性質，若a^b=c，那麼a=b^c，因為t是我們要驗證的目前最大值，是以我們周遊set中的數時，和t異或後的結果仍在set中，說明兩個字首可以異或出t的值，是以我們更新res為t，繼續周遊，如果上述講解不容易了解，那麼建議自己帶個例子一步一步試試，并把每次循環中set中所有的數字都列印出來，基本應該就能了解了，參見代碼如下：