Binary XOR—Understanding

One question that needs to be considered for bitwise XOR of two numbers is: Is the result after XOR greater or smaller than the original two?

Next look at a question: 2018 ACM-ICPC Asia Qingdao Regional Competition

K XOR Clique

BaoBao has a sequence a​1​​,a​2​​,...,a​n​​. He would like to find a subset S of {1,2,...,n} such that ∀i,j∈S, a​i​​⊕a​j​​<min(a​i​​,a​j​​) and ∣S∣ is maximum, where ⊕ means bitwise exclusive or.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n (1≤n≤10​5​​), indicating the length of the sequence.

The second line contains n integers: a​1​​,a​2​​,...,a​n​​ (1≤a​i​​≤10​9​​), indicating the sequence.

It is guaranteed that the sum of n in all cases does not exceed 10​5​​.

Output

For each test case, output an integer denoting the maximum size of S.

Sample Input

3
3
1 2 3
3
1 1 1
5
1 2323 534 534 5

Sample Output

2
3
2

分析: Two numbers XOR, XOR result is greater than or less than. In fact, it only needs to look at the maximum position and it is OK. How to understand it and look down.

(1) Let a=7 b=5, the binary writing of 7 is: a=0111

5 The binary writing method is: b=0101

We find that the binary of 5 and 7 is the highest The bits are all 4, the difference or the natural highest position becomes 0, and the result will appear smaller than 5 and 7. 2.

(2) Set a=7 b=3, 7 binary writing Yes: a=0111

3 binary writing is: b=0011

We found that the best bits of 7 and 3 are different, 7 is 4, 3 is 2, so the difference or the result The highest position will be 4, 7^3=4 is greater than 3.

. Therefore, when the two numbers are different, the highest digit is the same, then the number after XOR will be the same as the original one. A small number. Applying this conclusion will make it easy to solve this problem.

#include<bits/stdc++.h>
int ans[32];
int n,m,maxn,num;
int main()
{
    cin>>n;
    while(n--){
        cin>>m;
        maxn=0;
        memset(ans,0,sizeof ans);
        for(int j=1;j<=m;j++){
            cin>>num;
            for(int i=30;i>=0;i--){
                if((1<<i)&num){
                    ans[i]++;
                    break;
                }
            }
        }
        for(int i=0;i<=30;i++)maxn=max(maxn,ans[i]);
        cout<<maxn<<endl;
    }
    return 0;
}