我想我有一个O（n lg U）算法，其中U是最大的数字。这个想法类似于user949300的想法，但有更多细节。

直觉如下。当您将两个数字异或时，要获得最大值，您希望在最高位置上有一个1，然后在此位置上有1的配对中，想要与下一个有1的配对可能的最高位置，等等。

因此算法如下。首先找到数字中任意位置的最高1位（您可以通过对n个数字中的每个数字进行O（lg U）运算，在时间O（n lg
U）中进行此操作）。现在，将数组分为两部分-
其中一个数字为1，该组数字为0。任何最佳解决方案都必须将第一个点中带有1的数字与那个点中带有0的数字组合在一起，因为这将使1位尽可能高。任何其他配对那里都有0。

现在，递归地，我们要从1和0组中找到具有最高1的数字对。为此，将这两个组分为四个组：

• 以11开头的数字
• 以10开头的数字
• 以01开头的数字
• 以00开头的数字

如果11和00组或10和01组中有任何数字，则它们的XOR是理想的（从11开始）。因此，如果这些组对中的任何一个都不为空，则从这些组递归计算理想解，然后返回这些子问题解的最大值。否则，如果两个组都为空，则意味着所有数字在第二个位置必须具有相同的数字。因此，以1开头的数字和以0开头的数字的最佳XOR运算将导致下一个第二位被抵消，因此我们只看一下第三位。

这给出了以下递归算法，该算法从由其MSB划分的两组数字开始，给出了答案：

• 给定组1和组0以及位索引i：
  • 如果位索引等于位数，则返回1组中（唯一）编号和0组中（唯一）编号的XOR。
  • 从这些组构造组11、10、01和00。
  • 如果组11和组00为非空，则递归地找到从位i + 1开始的那两个组的最大XOR。
  • 如果组10和组01为非空，则从第i + 1位开始递归地找到这两个组的最大XOR。
  • 如果以上任何一种配对均可行，则返回递归找到的最大配对。
  • 否则，所有数字都必须在位置i处具有相同的位，因此返回通过查看组1和0上的位i + 1找到的最大对。

要开始使用该算法，您实际上可以将初始组中的数字分为两组-具有MSB 1的数字和具有MSB 0的数字。然后使用两组数字对上述算法进行递归调用。

例如，考虑数字5 1 4 3 02。它们具有表示形式

101  001  100   011   000   010

我们首先将它们分为1组和0组：

101  100
001  011  000  010

现在，我们应用以上算法。我们将其分为11、10、01和00组：

11:
10:  101  100
01:  011  010
00:  000  001

现在，我们无法将任何11个元素与00个元素配对，因此我们只递归10和01组。这意味着我们构造了100、101、010和011组：

101: 101
100: 100
011: 011
010: 010

现在我们只剩下其中一个元素的存储桶，我们只需检查对101和010（给出111）以及100和011（给出111）。这两种方法都适用，因此我们得到的最佳答案是7。

让我们考虑一下该算法的运行时间。注意，最大递归深度为O（lg U），因为数字中只有O（log
U）位。在树的每个级别上，每个数字恰好出现在一个递归调用中，并且每个递归调用的确与0和1组中的总数成比例，因为我们需要按位分配它们。因此，递归树中有O（log
U）个级别，每个级别都执行O（n），因此总工作量为O（n log U）。

希望这可以帮助！这是一个了不起的问题！