CSU 1216: 异或最大值

题目：

Description

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

Input

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

Output

任意两数最大异或值

Sample Input

3
3
7
9

Sample Output

14

代码：

#include<iostream>
#include<string.h>
using namespace std;

const int m = 3000000;
int ans[m][2], key;

int f(int x)
{
	for (int i = 29, k = 0; i >= 0; i--)
	if (ans[k][1 - (x >> i) % 2] == 0)
	{
		k = ans[k][(x >> i) % 2];
		if ((x >> i) % 2)x ^= (1 << i);
	}
	else
	{
		k = ans[k][1 - (x >> i) % 2];
		if ((x >> i) % 2 == 0)x ^= (1 << i);
	}
	return x;
}

int main()
{
	int n, m, r;
	while (scanf("%d",&n)!=EOF)
	{
		r = 1 << 31;
		memset(ans[0], 0, sizeof(ans[0]));
		key = 0;
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &m);
			if (f(m) > r)r = f(m);
			for (int k = 29, j = 0; k >= 0; k--)
			{
				if (ans[j][(m >> k) % 2] == 0)
				{
					ans[j][(m >> k) % 2] = ++key;
					memset(ans[key], 0, sizeof(ans[key]));
				}
				j = ans[j][(m >> k) % 2];
			}
		}
		printf("%d\n", r);
	}
	return 0;
}
/**********************************************************************
	Problem: 1216
	User: 3901140225
	Language: C++
	Result: AC
	Time:140 ms
	Memory:25460 kb
**********************************************************************/