异或最大值

最大异或值

题目描述

给定一些数，求这些数中两个数的异或值最大的那个值

输入

多组数据。第一行为数字个数n，1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

输出

任意两数最大异或值

样例输入

3
3
7
9

样例输出

14

解题想法

1. 暴力过不了
2. 解题分为插入和查找两个步骤
3. 建一棵字典树，把每一个数字拓展到32位，因此不能使用int类型进行存储，会溢出
4. 插入时，从数字二进制的高位到低位进行建树，从根节点开始，0则左子节点赋值，1则右子节点赋值
5. 查找时需要走与当前位反的节点，若与当前位反的节点为NULL，才走位同节点，走完以后获取走过的位组成的数，这个数就是当前查找的数的最大的异或值，接下来只需要查找所有的数的最大异或值，取最大即可

代码

#include<iostream>
#include<cmath>
#define ll long long
using namespace std;

class Node{
public:
    Node *lc;
    Node *rc;
    Node(){
        lc = NULL;
        rc = NULL;
    }
};
Node *root = NULL;
ll maxn = 0;
ll num[1000000];

void getmaxn(ll num){
    maxn = maxn > num ? maxn : num;
}
void init(){
    root = NULL;
    maxn = 0;
}
void buildTree(){
    root = new Node();
}
void insert(ll num){
    Node *now = root;
    ll xcount = 32;
    ll x = 1ll<<31; //1ll实质时表示1这个数据是long long类型的，防止溢出
    while(xcount--){
        if((num & x)){
            if(now->rc == NULL){
                Node *c = new Node();
                now->rc = c;
                now = now->rc;
            }
            else{
                now = now->rc;
            }
        }
        else{
            if(now->lc == NULL){
                Node *c = new Node();
                now->lc = c;
                now = now->lc;
            }
            else{
                now = now->lc;
            }
        }
        x >>= 1; 
    }
}
void Search(ll num){
    Node *now = root;
    ll temp = 0;
    ll xcount = 32;
    ll x = 1ll<<31;
    while(xcount--){
        if((x & num)){
            if(now->lc != NULL){
                now = now->lc;
                temp += x;
            }
            else if(now->rc != NULL){
                now = now->rc;
            }
        }
        else{
            if(now->rc != NULL){
                now = now->rc;
                temp += x;
            }
            else if(now->lc != NULL){
                now = now->lc;
            }
        }
        x >>= 1;
    }
    getmaxn(temp);
}

int main()
{
    int  n;
    while(cin >> n){
        init();
        buildTree();
        for(int i = 0; i < n; i++){
            cin >> num[i];
            insert(num[i]);
        }
        for(int i = 0; i < n; i++){
            Search(num[i]);
        }
        cout << maxn << endl;
    }
}