Maximum XOR of Two Numbers in an Array and Bitmasking

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;
    }

Could someone explain what is going on when we apply the AND operator on nums[i] with what seems like a progressively smaller mask(Beginning with 2^31, 2^30...)

int left = num & mask

I know from the comments it's supposed to keep the left bits while ignoring the right bits but I'm still not sure what's happening behind this code.

Answer 1

Given input [3,10,5,25,2,8], the output is 28 (given by 5^25):

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

Note that xor operation gives 1 when two bits are dissimilar, 0 otherwise. So with that consideration, we start from the left (most significant bit, given by i=31 in your code).

With

mask = mask | (1 << i);

we calculate the mask in each iteration. In the first iteration the mask is 100...000, then 1100...000 in the next and so on. If you are unsure how, please refer this answer.

Note that we are using a greedy approach - when you are working on the ith bit you are just concerned with the bits at that position; those to the left have already been taken care of previously and what follows to the right will be taken care of, in the subsequent iterations. With that in mind, in the next step, we create a hashset set and put all the num & mask values in it. For instance, our mask is 110...000 when i=30, so at that point, we are only looking at i=30th bits in 5 and 25 (MSBs to the left, at i=31, have been taken care of already, and since we do &, those to the right are ignored as our mask has all 0s there).

Next, with:

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

we set our 'expectation' for the current iteration. Ideally, we want a 1 at the ith position, as we want to find the maximum xor. With this set, we look at all the elements in the set and see if any one meets our expectations. If we find one, then we update our max accordingly, otherwise our max remains unchanged.