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.

score 1 · Answer 1 · answered Mar 26 '21 at 12:57

1

I find it easiest to view this as a recursive algorithm.

The base case is when all of the numbers are zero. Then the max XOR is obviously zero.

Recursively, we trim away the least significant bit of each number and solve the subproblem. Now, given that we know the maximum from this subproblem, call it submax, the answer is either submax<<1 or (submax<<1)|1, because the least significant bits of the numbers only affect the least significant bit of the max XOR. We can check whether the answer is (submax<<1)|1 by testing whether any two numbers have this XOR.

This code prefers to mask off the low order bits instead of shifting. The loop turns on each successive bit of mask from most significant to least, corresponding to the increasing length of the numbers in the current recursive call. num & mask zeroes out the currently ignored low order bits.

answered Mar 26 '21 at 12:57

David Eisenstat

64,237
7
60
120

Thanks for the response! On LC, the poster says that the mask will progress from 100..000 , 110..000, 111..000, then 1111...111 But when I console log it out it seems that the map will progressively half each pass from 2^31 all the way until 1. Just wondering, which approach is correct? – Mike Chan Mar 26 '21 at 13:36
1

@MikeChan the first one. – David Eisenstat Mar 26 '21 at 14:33
Thank you for all the help! Just wanted to ask one last thing: Just wondering when we calculate left as below: int left = num & mask What is the intuition/reasoning behind this particular or just the code that at some point, we know for sure that a certain nums[i] XOR left will === greed? (Which is why we keep amending it and putting 1 at the i'th place) – Mike Chan Mar 26 '21 at 17:02
@MikeChan we don't know. What we know is that the answer is either `max` or `greed`. The answer is `greed` if and only if we find two numbers whose XOR is `greed` (i.e., `greed` XOR one masked number is contained in the set of other masked numbers), in which case we update `max` to greed and reveal another bit position. – David Eisenstat Mar 26 '21 at 17:16

score 1 · Accepted Answer · 2021-03-26T18:19:06.510

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.

Thank you! Given your above input array of [3,10,5,25,2,8] We KNOW THAT at some point, we will calculate a greed value = 28 since that is the maximum XOR within the array. At some point, Greed(28) ^ left(4) = 24 which already exists in the Set which is why we set max = 28. By using the AND Operator in num & mask we are given a number that can be used to XOR with greed to determine if that resulting number exists within the Set. What I’m having trouble grasping is conceptually how and why does ```num & mask``` (left) work the way it does? — Mike Chan, Mar 27 '21 at 10:46
@MikeChan, if I understand you correctly, we don't know beforehand that we will calculate a greed value of 28. We just set our expectations and try to see if our expectations are met. All `num&mask` is doing is setting our focus on the current bit - those to the left have been taken care of, while the following ones are looked into, on the following iterations. — , Mar 27 '21 at 20:38

Maximum XOR of Two Numbers in an Array and Bitmasking

2 Answers2