查找最大XOR匹配

Question

我需要找到一个给定序列的数量，它与给定的常数值具有最大XOR。假设如下：
给定系列：6 7 8 9 10并且给定的常数是10。10与其他给定数字的最大异或为13，即7。所以我需要找到7。
现在我正在遵循标准方法。问题是，当我得到100000个整数时，我的代码占用了太多时间。有其他有效的方法吗？

Answer 1

我能想到的最快的方法是循环遍历数字数组，并将它们与常数异或，通过将它们与之前找到的最大值进行比较来找到最大值。在找到最大的数字后，只需再次将其与常数进行异或，即可找到原始值。

Java代码：

public int findMaximumXOR(int[] nums, int constantNum)
{
    int largest = nums[0] ^ constantNum;
    for (int i = 1; i<nums.length; ++i)
        if (largest<(nums[i] ^ constantNum))
            largest = (nums[i] ^ constantNum);
    return (largest ^ constantNum);
}

Answer 2

设a为数组，q为数字。

首先对给定的数组进行排序，然后对(MAX-q)执行二进制搜索，其中MAX是最大可能的整数（2³¹-1）。其思想是，当所有比特都与数字q中的比特相反时，excor是最大的。

Answer 3

这里可以使用树。

在输入数字时构造一个二进制树，MSB位于顶部。

现在，对于每个数字（例如1011），遍历树以获得0100…

在任何时候，如果没有找到理想的赞美，就为现有的一切妥协，并继续下去。

Answer 4

import java.util.Scanner;
public class Solution {

    public static void main(String[] args) throws Exception{
        Scanner in = new Scanner(System.in);
        int l = in.nextInt();
        int r = in.nextInt();
        String ls = Integer.toBinaryString(l);
        String rs = Integer.toBinaryString(r);
        if (ls.length() != rs.length()) {
            System.out.println((int)Math.pow(2, rs.length())-1);        
            return;
        }
        int len = ls.length();      
        int index=0;
        for(; index < len; ++index){
            if (ls.charAt(index) != rs.charAt(index))
                break;
        }
        if (index == len) //l = r
            System.out.println(0);
        else
            System.out.println((int)Math.pow(2, len-index)-1);
    }
}

Answer 5

int L = 0, R = n-1;
for(int i = 31; i >= 0 && L < R; i--) {
  if(((a[L]>>i)&1) == ((a[R]>>i)&1))
    continue;
  int l = L, r = R;
  while(r - l > 1) {
    int m = (r+l)/2;
    if((a[m]>>i)&1) r = m;
    else l = m;
  }
  if((b>>i)&1) R = l;
  else L = r;
}

CCD_ 6是与数b最大化xor的数的索引a包含按排序顺序排列的数字