Problem Statement

Boneca Ambalabu gives you a sequence of $n$ integers $a_1,a_2,\ldots,a_n$.

Output the maximum value of $(a_k\oplus a_1)+(a_k\oplus a_2)+\ldots+(a_k\oplus a_n)$ among all $1 \leq k \leq n$. Note that $\oplus$ denotes the bitwise XOR operation.

Input

The first line contains an integer $t$ ($1 \leq t \leq 10^4$) – the number of independent test cases.

The first line of each test case contains an integer $n$ ($1 \leq n\leq 2\cdot 10^5$) – the length of the array.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i < 2^{30}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output the maximum value on a new line.

Solving

考虑拆位：

((1ll << j) & arr[i]) == 1 表明arr[i]二进制下的第 j 位下为1

反之则表明其二进制下第 j 位为0

我们使用一个二维数组 cnt 来统计每一位上 0 和 1 的个数。对于数组中的每个元素 arr[i]，我们遍历其每一位 j，并根据该位的值更新 cnt[j][0] 或 cnt[j][1]。

对于每个 \(a_k\)，我们遍历其每一位 j。如果 \(a_k\) 的第 j 位为 1，那么在异或运算中，它与第 j 位为 0 的元素异或结果为 1，因此该位对异或和的贡献为 cnt[j][0] << j；如果 \(a_k\) 的第 j 位为 0，那么它与第 j 位为 1 的元素异或结果为 1，该位对异或和的贡献为 cnt[j][1] << j。

注意：当且仅当二进制位与arr[i]异或后二进制位等于1时才会对sum产生贡献

若此位与arr[i]异或后为0，其贡献为 0 « j = 0，及不会产生贡献

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

void solve()
{
    int n;
    cin >> n;
    vector<int> arr(n+1);
    for(int i=1;i<=n;i++) cin >> arr[i];
    vector<vector<int>> cnt(31,vector<int>(2,0));//cnt[i][x]表示i位上为x的元素有几个
    for(int i=1;i<=n;i++)
    for(int j=0;j<=30;j++)
    {
        bool bit = (1 << j) & arr[i];// 第j位为 1 -> 1,为 0 -> 0
        cnt[j][bit]++;
    }
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        int sum = 0;
        for(int j=0;j<=30;j++)
        { 
            if((1<<j)&arr[i])//如果arr[i]的该位为1
            {
                //则当且仅当与其异或的二进制位为0时，异或后的比特位才为1，才会产生贡献 
                sum += cnt[j][0] << j;
            }
            else//如果arr[i]的该位为0
            {   
                //则当且仅当与其异或的二进制位为1时，异或后的比特位才为1，才会产生贡献 
                sum += cnt[j][1] << j;
            }
        }
        ans = max(sum,ans);
    }
    cout << ans << endl;
}