How to find Maximum AND XOR value of two elements in array?

I always feel confused when I face bit manipulation algorithm problems. Even the solution post in discussion forum is hard for me to understand.

When I was trying to figure out the daily challenge, ofc it is a bit manipulation problem, I do more research because I still can’t understand the solution post in discussion which everyone think it is a amazing code. Fortunately, now I think I could understand the problem well from the article I read from geeksforgeeks. So I want to write this blog to deepen my impression.

AND

For AND problem, first we should check the bit pattern as 10000…0000, from MSB to LSB. For example, if the biggest number in array is 5 bit, we should start the pattern as 10000. Then we should find how many elements in array could get the MSB bit, 5th bit. If we could find more than one elements, which means at least two elements in array we could set the target bit as 1 after AND operation, then we could save the set bit as our temporarily resolution. The sample code as below:

// Java Program to find maximum 
// XOR value of a pair 
import java.util.*; 
import java.lang.*; 

public class GfG{ 

// Utility function to check number of elements 
// having set msb as of pattern 
static int checkBit(int pattern, int arr[], int n) 
{ 
    int count = 0; 
    for (int i = 0; i < n; i++) 
        if ((pattern & arr[i]) == pattern) 
            count++; 
    return count; 
} 

// Function for finding maximum and value pair 
static int maxAND (int arr[], int n) 
{ 
    int res = 0, count; 

    // iterate over total of 30bits 
    // from msb to lsb 
    for (int bit = 31; bit >= 0; bit--) 
    { 
        // find the count of element 
        // having set msb 
        count = checkBit(res | (1 << bit), arr, n); 

        // if count >= 2 set particular 
        // bit in result 
        if ( count >= 2 )     
            res |= (1 << bit);     
    } 

    return res; 
} 

// driver function 
public static void main(String argc[]) 
{ 
    int arr[] = {4, 8, 6, 2}; 
    int n = arr.length; 
    System.out.println("Maximum AND Value = " + 
                    maxAND(arr, n)); 
} 
} 

// This code is contributed by Prerna Saini 

XOR

To find the largest XOR value of two number in array, we could use a similar way as above. We need a mask bit string to filter the no need bit string from our numbers, which means we should use this mask to gain a prefix bit string of number for store and ignore the post-fix. Now in our set, we should get some bit string like, 10100..000, 11100…000, 01000..000… Then we will update our max, the max will be added one more 1 bit set because that will be the current or next max bit string we will get. Then we will go over the previous set and check if it contains prefix ^ max. Here the prefix from set and the prefix as contains result could be seen as two number in array, eg. a^b = c, c ^ b = a. The solution code as below:

// C++ implementation of the above approach 

#include <bits/stdc++.h> 
using namespace std; 

// Function to return the 
// maximum xor 
int max_xor(int arr[], int n) 
{ 
    int maxx = 0, mask = 0; 

    set<int> se; 

    for (int i = 30; i >= 0; i--) { 

        // set the i'th bit in mask 
        // like 100000, 110000, 111000.. 
        mask |= (1 << i); 

        for (int i = 0; i < n; ++i) { 

            // Just keep the prefix till 
            // i'th bit neglecting all 
            // the bit's after i'th bit 
            se.insert(arr[i] & mask); 
        } 

        int newMaxx = maxx | (1 << i); 

        for (int prefix : se) { 

            // find two pair in set 
            // such that a^b = newMaxx 
            // which is the highest 
            // possible bit can be obtained 
            if (se.count(newMaxx ^ prefix)) { 
                maxx = newMaxx; 
                break; 
            } 
        } 

        // clear the set for next 
        // iteration 
        se.clear(); 
    } 

    return maxx; 
} 

// Driver Code 
int main() 
{ 

    int arr[] = { 25, 10, 2, 8, 5, 3 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 

    cout << max_xor(arr, n) << endl; 

    return 0; 
} 

LeetCode

Finally let’s see the problem in No.421 in LeetCode.