CODEWITHSUNDEEP
algorithmbit-manipulationbitmaskbitwise-and
Mike Chan
Mike Chan

Reputation: 337

Maximum XOR of Two Numbers in an Array and Bitmasking

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.

Upvotes: 1

Views: 796

Answers (2)

anon
anon

Reputation:

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.

Upvotes: 1

David Eisenstat
David Eisenstat

Reputation: 65458

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.

Upvotes: 1

Related Questions