2317. Maximum XOR After Operations

Question

You are given a 0-indexed integer array nums. In one operation, select any non-negative integer x and an index i, then update nums[i] to be equal to nums[i] AND (nums[i] XOR x).

Note that AND is the bitwise AND operation and XOR is the bitwise XOR operation.

Return the maximum possible bitwise XOR of all elements of nums after applying the operation any number of times.

Solution

异或运算相当于不进位的加和。
和运算相当于掩码操作。
或运算相当于保留该位上的1。

由于我们要对所有数字进行异或运算，因此只要能改变某一位对应的数字，我们就可以确保这一位在进行异或运算时结果可以为1。（当不改变时改为的异或运算结果为0，则我们只需要改变改为即可得到1）

将所有我们可以操作的位置变为1，就可以得到最大值。

因此，我们只需要确定哪些位是我们可以操作的即可：

• nums[i]与任意正整数进行异或运算可以得到任意整数。在这个条件下我们可以得到任意的32位整数。
• 然而和运算相当于掩码操作，如果nums[i]对应二进制的某一位上位0，则我们无法通过和运算将这一位改变为1。

只要该位出现过1，则我们可以控制这个位。因此我们可以通过或运算所有数字，保留所有可控制的位。

Code

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