给定一个由N个整数组成的整数数组A，在数组中找到具有最小XOR值的整数对这是Brute-Force解决方案，我们找到每对可能的，计算XOR并找到每对的最小值：
int minXOR(int arr[], int n)
{
int min_xor = INT_MAX; // Initialize result
// Generate all pair of given array
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
// update minimum xor value if required
min_xor = min(min_xor, arr[i] ^ arr[j]);
return min_xor;
}
以下是具有O(n*logn(复杂性的代码：
int Solution::findMinXor(vector<int> &A) {
sort(A.begin(),A.end());
int min=INT_MAX;
int val;
for(int i=0;i<A.size();i++)
{
val=A[i]^A[i+1];
if(val<min)
min=val;
}
return min;
}
我的疑问是，排序如何帮助找到最小异或值对？在这个解决方案中，我们只找到连续排序元素的xor。我们不会错过其他不连续的潜在最小异或值对吗？我还在学习一些小技巧，所以如果这个怀疑看起来太愚蠢，请原谅我。
XOR在数字之间的绝对差中是单调的。(如果数字相同，则XOR为零(。如果你忽略负数的可能性，把数字写成二进制，这就很明显了。
因此，排序列表中的最小值总是在特定的相邻对之间。找到那个对是一个O(N(遍历。
我必须承认，我不理解@Bathseba投票最多的答案：xor的参数之间的绝对差异不是单调的，请参阅@OfekShilon的评论。
该特性可以通过例如完全归纳来证明。以下是主要想法：
考虑一下二进制表示中的几个不同数字，按升序排列：
N = 6
A[1] = 10001
A[2] = 10011
A[3] = 11000
A[4] = 11100
A[5] = 11110
A[6] = 11111
设CCD_ 1。设k是x的比特表示中最左边的1的位置，从右边开始计数。其中：x = 10001 xor 11111 = 01110和k = 5(对于最低有效位使用约定k=1(。所有留给k的比特(即，在更重要的位置上(在每个数字中都是相同的，因此它们可以被忽略，甚至被设置为零。在我们的示例中，位置5(一(、6(零(、7(零(等处的所有位都是不相关的。我们只能考虑比特1，。。。，k.
N=2的情况是平凡的，所以假设我们至少有3个数字
我们可以将数字划分为两个不相交的子集(或者实际上是子序列(，B_0={第k位设置为0的数字}，B_1={第k位设置为1的数字}。
B_0:
A[1] = 10001
A[2] = 10011
B_1:
A[3] = 11000
A[4] = 11100
A[5] = 11110
A[6] = 11111
没有一个是空的。每个元素少于N个。其中一个具有至少2个元素(回想一下N>2(。在最小化A[i] xor A[j]的对中，两个数字必须属于相同的子集，即B_0或B_1，因为只有这样的组合才会产生第k位(以及所有更重要的位(设置为0的数字。这足以证明使xor最小化的对必须是A的连续元素对之一的说法(我们可以将N元素问题简化为元素数量较少的问题，并且"定理"对于N=2是平凡的，因此完全归纳法就可以完成这项工作(。
较小数字的异或很小，所以基本上可以将其视为2个数字2和3的异或，其二进制表示为010表示2，011表示3。如果对这两个数字执行异或，答案将是001，即1。同样的方法，如果你对2(010(和4(100(进行异或运算，答案是110，也就是6。所以基本上，随着数字的增加，它们的xor值也会增加。因此，对数组进行排序可以在最少的迭代次数中为我们提供最小异或值对。
具有O(n*logn(复杂度的Java代码
public int findMinXor(ArrayList<Integer> A) {
Collections.sort(A);
int res = Integer.MAX_VALUE;
for(int i = 0; i < A.size()-1; i++){
int temp = A.get(i)^A.get(i+1);
if(res > temp){
res = temp;
}
}
return res;