如何找到xor==n的一对数字

Question

我是位运算新手我有这个问题，我不知道如何解决它
问题 找到异或等于一个值（比如n）的对，并返回最小差异对

example n=5 possible pairs are 1-4,9-12 and so on
result is 4-1 as the diffrence of 4-1 is minimum 

暴力不适用于这里，因为范围非常大，高达1<；n<；10^18
有什么提示吗

Answer 1

假设n为正。首先使用O（logn）循环将n减少到m，这是比n小2的最高幂：

m = n
while m & (m-1):
    m = m & (m-1)

那么你的答案将是m和n-m

让我试着给出一个证明的草图：

看看为什么这适用于m ^ (n-m) == n应该很简单。现在我来证明为什么这对有最小的差异。让{}对于一些{}和{}在不丧失一般性的情况下，假设{}。我们不假定m == x，因为否则n==0。在保持m ^ x == n的同时，如果我们将它们的相同零位翻转为1，我们将它们增加相同的量，因此它们的差值m-x仍然是相同的。因此，我们也可以假设m和x上的位永远不会都是同一位置上的1。如果我们翻转在m上为0而在x上为1的位，它在x上会减少，但在m上会增加，并且差异m-x会更大。如果我们翻转在m上为1但在x上为0的位，的差异可能会更小。因此，具有最小差异的对使得我们不能进行最后的翻转，即m翻转m上的任何1位将使m < x