algorithm - 数组的所有子集之间的最大异或

Question

我必须在数组子集的元素中找到异或的最大值。我必须检查数组的每个子集，将产生最大 xor 的子集就是答案。

例如-让F(S) 表示对数组P 的子集S 的所有元素进行异或的函数={1,2,3,4}

F({1,2}) = 3
F({1,3}) = 2
F({1,2,3}) = 0  
F({1,4}) = 5
F({2,3}) = 1  
F({2,4}) = 6  
F({3,4}) = 7  
F({2,3,4}) = 5  
F({1,2,3,4}) = 4`  

它们中的最大值是 7。因此答案是 7。(还有其他子集，但不值得考虑)。 如果你要告诉我关于Gaussian Elimination 方法，我在 MSE 的某个地方读过，但我一点都不清楚。如果高斯消去法是唯一的答案，请向我详细说明，或者是否有一些我不知道的方法/算法？

Answer 1

高斯消元是您所需要的。

例如:3 个数字 {9, 8, 5}

首先将它们按降序排列并转换成二进制:

9 : 1001
8 : 1000
5 : 0101

观察第一个数字。最高位是 4。
现在检查 1st 数字 (9) 的 4th 位。因为它是 1，所以将第 4 位为 1 的数字与其余数字异或。

9 : 1001
1 : 0001 > changed
5 : 0101

现在检查 2nd 数 (1) 的 3rd 位。因为它是 0，请检查下面其余的数字，其中 3rd 位是 1。
数字 5 在 3rd 位中有 1。交换它们:

9 : 1001
5 : 0101 > swapped
1 : 0001 >

现在 xor 5 与 3rd 位为 1 的其余数字。这里不存在。所以不会有任何变化。

现在检查 3rd 数 (1) 的 2nd 位。因为它是0，而第2位为1的地方下面没有其他数，所以不会有变化。

现在检查 3rd 数 (1) 的 1st 位。由于它是 1，因此更改 1st 位为 1 的其余数字。

8 : 1000 > changed
4 : 0100 > changed
1 : 0001

没有更多的考虑:)

现在对整个剩余数组进行异或运算 {8 ^ 4 ^ 1} = 13

所以 13 是解决方案:)

这几乎就是您使用高斯消去法解决问题的方法:)

这是我的 C++ 实现:

#include <bits/stdc++.h>
using namespace std;

typedef long long int           ll;
typedef unsigned long long int  ull;

ull check_bit(ull N,int POS){return (N & (1ULL<<POS));}

vector<ull>v;
ull gaussian_elimination()
{
    int n=v.size();
    int ind=0;  // Array index
    for(int bit=log2(v[0]);bit>=0;bit--)
    {
        int x=ind;
        while(x<n&&check_bit(v[x],bit)==0)
          x++;
        if(x==n)
          continue; // skip if there is no number below ind where current bit is 1
        swap(v[ind],v[x]);
        for(int j=0;j<n;j++)
        {
            if(j!=ind&&check_bit(v[j],bit))
                v[j]^=v[ind];
        }
        ind++;
    }
    ull ans=v[0];
    for(int i=1;i<n;i++)
      ans=max(ans,ans^v[i]);
    return ans;
}
int main()
{
    int i,j,k,l,m,n,t,kase=1;
    scanf("%d",&n);
    ull x;
    for(i=0;i<n;i++)
    {
        cin>>x;
        v.push_back(x);
    }
    sort(v.rbegin(),v.rend());
    cout<<gaussian_elimination()<<"\n";
return 0;
}