设 a 为答案最大值
设 b,c 为 list 的两数字
1 2 3 4 ... k
a x x x x ... x
b x x x x ... x
c x x x x ... x
每次 a 由左至右算第 k 位 bit 时，都先假设为 1
如果能找到一组(b,c)，使得:
prefix(a,k) & prefix(b',k) = prefix(a,k) & prefix(c,k)
则 a 的第 k bit 必存在有 1 的解，否则该 bit 为 0
注: 红色等式如果改成:
prefix(b,k) ^ prefix(a,k) = prefix(c,k)
感觉比较好理解！
※ 引述《benchen0812 (あBen)》之铭言：
: 第一次发文
: 如果有那里不妥当请告知
: 最近在LEETCODE刷提 遇到一题求 list 里面任意两数字XOR最大值
: 题目连结在这边
: https://goo.gl/HPH4Sm
: 这题最快的解答是
: class Solution:
: def findMaximumXOR(self, nums):
: """
: :type nums: List[int]
: :rtype: int
: """
: ans = 0
: for bit in range(31, -1, -1) :
: ans = (ans << 1) + 1
: pre = set()
: for n in nums :
: p = (n >> bit) & ans
: if p in pre : #1
: break #2
: pre.add(ans - p) #3
: else : #4
: ans -= 1
: return ans
: 我的问题在我标#1-4的地方
: 我不太明白这边的if else statement 怎么运作的(特别是#4)
: 一开始我以为是当if p not in pre:
: 就会直接跳到#4
: 但是好像不太对
: 请问有人可以跟我说明一下吗?
: 非常感谢!