Fastest and most efficient way to find the maximum no. that can be obtained by performing bitwise and on 2 DISTINCT elements of array

Question

Given an array of non-negative integers, what is the fastest and most efficient way to find the maximum no. that can be obtained by performing bitwise and (i.e, & operator) on 2 DISTINCT elements of the array?

This is my code until now :

max = 0
for(i=0; i<n; i++)
{
    for(j=i+1; j<n; j++)
    {
        temp = a[i] & a[j];
        if(temp > max)
            max = temp
    }
 }

This, of course, is the naive method. I am looking for a more efficient solution.

Maybe something like using a trie(actually a binary tree) to find max XOR of elements of array. The description for the max XOR solution can be found at http://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems?share=1

Answer 1

I hope I have got the question right. Here's my solution to it:

You have an array of integers, say that they are unsigned integers since we are dealing with bitwise operations. Let's think of them as a string of zeroes and ones in their binary representation and then put them on top of each other.

We now have their corresponding bits aligned vertically. Let's draw vertical lines, starting from the leftmost column. If we ever encounter more than or equal to two 1s in a column, then rule out every row that does not have the 1s. We are to disregard the ruled out ones while drawing our further vertical lines.

You see where this is going at?

This shall go on until we have only and exactly 2 lines left that hasn't been ruled out. If we ever end up with anything else than 2, then it means something went wrong:

• Less than 2 means we had less than 2 lines initially
• More than 2 means that...
  • If there are less than what we had initially, then the ones left should all be identical
  • If there are exactly as many as we had initially, then it can be that all are the same, or every possible pair is bitwise distinct, meaning that every single pair produces 0

Here's the code I've written that follows the logic I've described above:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>

#define bit(_x_) (1U << (_x_))

void randomfillarray( unsigned int * arr, size_t size ) {
    srand( time( NULL ) );
    for ( int i = 0; i < size; i++ )
        arr[i] = rand( );
}

int main( ) {
    unsigned int arr[10];
    size_t size = sizeof arr / sizeof * arr;
    randomfillarray( arr, size );

    unsigned int * resultantcouple = malloc( sizeof arr );
    memcpy( resultantcouple, arr, sizeof arr );

    for ( int i = 0; i < size; i++ )
        printf( i ? " %u" : "%u", arr[i] );
    putchar( '\n' );

    int success = 0;

    for ( unsigned int thebit = bit( sizeof( int ) * 8 - 1 ); thebit; thebit >>= 1 ) {
        int count = 0;
        int * indices = NULL;
        for ( int i = 0; i < size; i++ ) {
            if ( resultantcouple[i] & thebit ) {
                indices = realloc( indices, ++count * sizeof * indices );
                indices[count - 1] = i;
            }
        }
        if ( count >= 2 ) {
            size = count;
            for ( int i = 0; i < size; i++ )
                resultantcouple[i] = resultantcouple[indices[i]];
            resultantcouple = realloc( resultantcouple, size * sizeof * resultantcouple );
        }
        if ( size == 2 ) {
            success = 1;
            break;
        }
        free( indices );
    }

    if ( success )
        printf( "Success! %u and %u are the ones.", resultantcouple[0], resultantcouple[1] );
    else
        printf( "Failure! Either all pairs are bitwise distinct, or there are less than 2 elements, or something else..." );


    putchar( '\n' );
    return 0;
}

Here's the same during action: http://ideone.com/hRA8tn

I'm not sure if this is the best, but it should be better than testing all out.