E.位运算-异或：2317. 操作后的最大异或和

题目链接：2317. 操作后的最大异或和（中等）

算法原理：

解法：位运算

1ms击败100.00%

时间复杂度O(N)

这题很考验推理能力~~

下面一步一步推出来结论👇

①题述操作在干什么？

设原数某一位是b（0或1），x的对应位是c（0或1）

当b=0时：0&（0^c）=0→原来是0位，永远只能是0，没法变成1

当b=1时：1&（1^c）

若c=0：1&1=1→保持1不变

若c=1：1&0=0→把1变成0

因此这个操作的本质：只能把数的二进制位里的1改成0，绝不能把0改成1

而x是我们能选的任意非负整数，这就意味着：

b=0时，该位只能还是0

b=1时，我们可以将其保持1或改为0

②最大异或和本质

对于数位上的每一位来说，最终异或的结果取决于所有数该位1的个数，当1的个数为奇数时，这一位还是1，否则就是0（异或操作：相同为0，相异为1）

③只需保证每个比特位有一个1即可

我们想让结果最大，那么只需要保证各个二进制位只有一个1即可，其余的我们都可以通过题述操作，让其变成0

怎么实现？举个例子：
假设数组有 3 个数，某一位分别是 1、1、0：
我们可以把第一个数的这一位「保留为 1」（不修改它）
把第二个数的这一位「改成 0」（利用操作把 1 变成 0）
第三个数的这一位本来就是 0，不用管
这样操作后，这一位上的 1 的个数变成了 1（奇数），异或和的这一位就是 1！
再举个反例：如果原数组某一位全是 0，那不管怎么操作，所有数的这一位都只能是 0，异或和的这一位永远是 0

④这就是或运算！

把③翻译过来，那么就是数组中所有的数全或在一起

Java代码：

class Solution { //2317. 操作后的最大异或和 public int maximumXOR(int[] nums) { int ret=0; for(int x:nums) ret|=x; return ret; } }