# 题目描述

De 在早八神游之中获得了一串传说中的异或数组。

​该数组由 $n$ 个元素 $x_i$ 组成，De 需要通过该数组在白日梦境中找到一个长度同样为 $n$ 的数组，其中每个数 $a_i$ 满足 $0 \le a_i \le x_i$，同时需要使 $a_1 \oplus a_2 \oplus \cdots \oplus a_n$ 尽可能大才能得到仙人指路。

​De 找到了认真上早八的你，希望你可以帮助他找到修仙之路。

# 输入格式

多组输入，每组输入两行。

第一行一个整数 $n$，满足 $1 \le n \le 50$。

第二行输入 $n$ 个整数 $x_i$ 满足 $0 \le x_i \le 10^9$。

# 输出格式

对于每组输入，输出一个整数表示满足条件的最大数。

# 输入样例

3

2 2 2

8

7 4 12 33 6 8 3 1

# 输出样例

3

47

# 题解：位运算 + 贪心

还是同样的套路，对于位运算使结果最大的问题，我们从高位到低位依次考虑，尽可能地让高位为 $1$。

从最高位开始，我们统计所有数中这一位是 $1$ 的数的个数。如果没有数这一位是 $1$，那么我们答案取不到 $1$ 了，否则就会有某个 $a_i > x_i$。如果只有一个数这一位是 $1$，那么显然 $a_i$ 这一位取 $1$，答案这一位能保证是 $1$，但我们还要接着往下看，因为我们还不能保证某个 $a_i$ 后面的所有取法都能使 $a_i < x_i$。如果这一位有多个数是 $1$，那很显然，让其中一个数的 $a_i$ 这一位取 $1$，其余数这一位取 $0$，对于接下来的所有位，令其余数中的一个数的所有位全部取 $1$，显然这个 $a_i < x_i$，再让其余 $n - 1$ 个数之后的所有位全部取 $0$，也一定不会超出 $x_i$，同时我们的答案也保证了最大。

时间复杂度：$O(T n \log x)$，其中 $T$ 为数据组数。

参考代码：

#include <stdio.h>

int n, x[55];

int main()

{

    // freopen("C.in", "r", stdin);

    // freopen("C.out", "w", stdout);

    while (~scanf("%d", &n))

    {

        for (int i = 1; i <= n; ++ i)

            scanf("%d", &x[i]);

        int ans = 0;

        for (int i = 29; ~i; -- i)

        {

            int cnt = 0;

            for (int j = 1; j <= n; ++ j)

                if (x[j] >> i & 1)

                    ++ cnt;

            if (cnt == 1)

                ans |= 1 << i;

            else if (cnt > 1)

            {

                ans |= (1 << i + 1) - 1;

                break;

            }

        }

        printf("%d\n", ans);

    }

    return 0;

}