2317-操作后的最大异或和

给你一个下标从 0 开始的整数数组 nums 。一次操作中，选择 任意 非负整数 x 和一个下标 i ， 更新
nums[i] 为 nums[i] AND (nums[i] XOR x) 。

注意，AND 是逐位与运算，XOR 是逐位异或运算。

请你执行 任意次 更新操作，并返回 nums 中所有元素 最大 逐位异或和。

示例 1：

**输入：** nums = [3,2,4,6]
**输出：** 7
**解释：** 选择 x = 4 和 i = 3 进行操作，num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2 。
现在，nums = [3, 2, 4, 2] 且所有元素逐位异或得到 3 XOR 2 XOR 4 XOR 2 = 7 。
可知 7 是能得到的最大逐位异或和。
注意，其他操作可能也能得到逐位异或和 7 。

示例 2：

**输入：** nums = [1,2,3,9,2]
**输出：** 11
**解释：** 执行 0 次操作。
所有元素的逐位异或和为 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11 。
可知 11 是能得到的最大逐位异或和。

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 108

Problem: 2317. 操作后的最大异或和

[TOC]

思路

1. 想要获取nums[i] XOR nums[i+1] XOR nums[…]的最大值，那么就需要保留更多逐位XOR后1的个数。

2. nums[i] AND (nums[i] XOR x) <= nums[i] , nums[i] AND (nums[i] XOR x)这个操作只会使nums[i]减小或者不变。

---

问 :

为什么题目要给出nums[i] AND (nums[i] XOR x)这个操作？

答：

首先题目需要求的是逐位XOR后的最大结果，多位数XOR会出现1抵消的情况，什么情况下会抵消？ 那就是出现偶数位1时会出现抵消，奇数情况下不会出现抵消的情况。所以nums[i] AND (nums[i] XOR x)的目的就是让我们把在偶数情况下抵消的1补回去，最大化的保留1的个数。既然是最大化保留1的个数，那么我们为什么不直接把逻辑转换为OR操作呢？

复杂度

• 时间复杂度:

  O(n)

• 空间复杂度:

  O(1)

Code

[]

class Solution {
    public int maximumXOR(int[] nums) {
      int max = 0;
      for (int num : nums) {
        max |= num;
      }
      return max;
    }
}