问从列表中查找XOR值最小的对

EN

(x ^ y) == (x | y) - (x & y) >= |y - x|

按顺序对数字进行排序将是一个开始，因为这些对之间的差异将给您提供xor的下限，因此也是何时停止查找要与x进行xor的数字的分界点。

还有一种快捷方式可以查找xor小于(比方说) 2的幂的数字对，因为您只对x <= y <= x|(2^N- 1)感兴趣。如果这不能为您提供足够的对，请增加N，然后重试。

编辑:当然，您可以使用x|(2^ (N - 1) - 1)

基于(排序) 1、2、2、3、4的示例

首先查找xor小于1的数字对:对于每个数字x，搜索后续数字y= x。这将得到{2，2}。

如果您需要多个数字对，请查找xor小于2但不小于1的数字对:对于每个数字x，搜索数字x

请注意，最终的XOR值并没有完全排序，但每一批都严格小于前一批。

如果需要更多，请查找xor小于4但不小于2的数字对:对于每个数字x，搜索数字x|1

如果需要更多，请查找xor小于8但不小于4的数字对:对于每个数字x，搜索数字x|3

我会首先对整数的输入数组进行排序。然后，具有最小XOR值的对将彼此相邻(但不是所有相邻对都具有最小XOR值)。您可以从相邻的配对开始，然后向外工作，检查配对(N，N+2)，(N，N+3)，直到您获得所需的K个最小结果列表。

对于示例数组{1 3 2 4 2}，排序后的数组为{1 2 2 3 4}，成对XOR值为：

1 xor 2 = 3
2 xor 2 = 0
2 xor 3 = 1
3 xor 4 = 7

对于下一步，

1 xor 2 = 3
2 xor 3 = 1
2 xor 4 = 6

再一次，

1 xor 3 = 2
2 xor 4 = 6

最后，

1 xor 4 = 5

这个想法并不完整，但您应该能够使用它来帮助构建一个完整的解决方案。