Compatible Numbers

**题目描述:**
Two integers x and y are compatible , if the result of their bitwise "AND" equals zero, that is, a & b = 0 . For example, numbers 90 (1011010 ) and 36 (100100 ) are compatible, as 1011010 & 100100 = 0 , and numbers 3 (11 ) and 6 (110 ) are not compatible, as 11 & 110 = 10 .

You are given an array of integers a1 , a2 , ..., an . Your task is to find the following for each array element: is this element compatible with some other element from the given array? If the answer to this question is positive, then you also should find any suitable element.

**Input**
The first line contains an integer n ( 1 ≤ n ≤ 10^6 ) — the number of elements in the given array. The second line contains n space-separated integers a1 , a2 , ..., an ( 1 ≤ ai ≤ 4·10 ^6 ) — the elements of the given array. The numbers in the array can coincide.

**Output**
Print n integers ans i . If a i isn't compatible with any other element of the given array a1 , a2 , ..., an , then ans i should be equal to -1. Otherwise ans i is any such number, that a i & ans i = 0 , and also ans i occurs in the array a1 , a2 , ..., an .

**题目大意**

给你n个数字,分别为a1,...,an,输出每个ai对应的x,使得ai^x==0(x是n个数中的任意一个)

**解题思路**

首先,我们知道 0 ^ 1=1, 1 ^ 1=0.对于题目中的每一个数字都小于1<<22.设N=(1<<22)-1,则对于每一个ai,令x=ai^N,x就相当于把ai上的每一个二进制位取反,所以 x ^ ai = 0.并且对于ai来说,去掉ai中任意一个二进制1得到y,有x ^ y=0.具体看代码吧,写不下去了......

**代码**

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
typedef pair<int,int>pii;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=100+5;
const int N=1<<22;
int dp[1<<22];
int a[1000000+5];
int main()
{
    int n;
    scanf("%d",&n);
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        dp[a[i]]=a[i];
    }
    for(int i=0;i<(1<<22);i++)
    {
        if(dp[i]==-1)
        {
            for(int j=0;j<22;j++)
            {
                if(i&(1<<j)&&dp[i^(1<<j)]!=-1)
                {
                    dp[i]=dp[i^(1<<j)];
                    break;
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        printf("%d ",dp[(N-1)^a[i]]);
    }
    puts(""); 
}