数组中两个数字的最大 XOR 和位掩码

Question

LC：https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

public int findMaximumXOR(int[] nums) {
        
     int max = 0, mask = 0;
        
     for (int i = 31; i >= 0; i--){
            mask = mask | (1 << i);
            
            Set<Integer> set = new HashSet<>();
            
            for(int num : nums){
                int left = num & mask
                set.add(left);
            }
            int greed = max | (1 << i);
            
            for (int prefix : set){
                if (set.contains(greed ^ prefix)) {
                    max = greed;
                    break;
                }
            }
        }
        return max;
    }

有人可以解释当我们在 nums[i] 上应用 AND 运算符时发生了什么，掩码看起来越来越小（从 2^31、2^30... 开始）

int left = num & mask

我从评论中知道它应该保留左边的位而忽略右边的位，但我仍然不确定这段代码背后发生了什么。

Answer 1

我发现最容易将其视为递归算法。

基本情况是所有数字都为零。那么最大异或显然为零。

递归地，我们trim去掉每个数字的最低有效位并解决子问题。现在，假设我们知道这个子问题的最大值，称它为 submax，答案是 submax<<1 或 (submax<<1)|1，因为数字的最低有效位只影响最低有效位的最大异或。我们可以通过测试任意两个数字是否具有此异或来检查答案是否为(submax<<1)|1。

此代码倾向于屏蔽低位而不是移位。循环打开 mask 的每个连续位，从最高位到最低位，对应于当前递归调用中数字的增加长度。 num & mask 将当前忽略的低位清零。

Answer 2

给定输入 [3,10,5,25,2,8]，输出为 28（由 5^25 给出）：

   Num   Binary
    5     00101
 ^ 25     11001
   ------------
 = 28     11100

请注意，当两个位不相似时，xor 操作给出 1，否则为 0。因此，考虑到这一点，我们从左边开始（最高有效位，由代码中的 i=31 给出）。

有

mask = mask | (1 << i);

我们在每次迭代中计算 mask。在第一次迭代中，掩码是 100...000，然后是下一次 1100...000，依此类推。如果您不确定如何操作，请参考 this answer.

请注意，我们使用的是贪婪方法——当您处理第 i 位时，您只关心该位置的位；左边的那些之前已经被处理过，右边的那些将在随后的迭代中得到处理。考虑到这一点，在下一步中，我们创建一个哈希集 set 并将所有 num & mask 值放入其中。例如，当 i=30 时，我们的掩码是 110...000，所以此时，我们只查看 5 和 25 中的第 i=30 位（左侧的 MSB ，在 i=31，已经被处理了，因为我们 &，右边的那些被忽略了，因为我们的掩码在那里有所有 0s）。

接下来，与：

int greed = max | (1 << i);

我们为当前迭代设置 'expectation'。理想情况下，我们希望在第 i 个位置有一个 1，因为我们想要找到最大的异或。有了这个集合，我们查看 set 中的所有元素，看看是否有一个符合我们的期望。如果我们找到一个，那么我们相应地更新我们的 max，否则我们的 max 保持不变。

数组中两个数字的最大 XOR 和位掩码

Maximum XOR of Two Numbers in an Array and Bitmasking

algorithm

bit-manipulation

bitmask

bitwise-and