最快和最有效的方式找到最​​没有。这可以通过执行按位与上排列的2个不同的元素来获得 [英] Fastest and most efficient way to find the maximum no. that can be obtained by performing bitwise and on 2 DISTINCT elements of array

问题描述

由于非负整数数组，什么是找到最大无最快和最有效的方式。这可以通过执行按位与得到？;在阵列的2个不同的元素（即，＆放大器操作者）

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?

这是我的code到现在为止：

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.

也许像使用特里（实际上是一个二叉树）找到数组的元素的最大XOR。为最大XOR解决方案的描述可以在找到http://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems?share=1

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

推荐答案

我希望我已经得到了问题的权利。这里是我的解决方案，以它：

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

您有一个整数数组，说他们是无符号整数，因为我们正在处理的位操作。让我们把它们当作自己的二进制重新presentation的0和1的字符串，然后把它们放在彼此顶部。

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.

我们现在有自己对应的位垂直对齐。让我们画垂直线，从最左边的列开始。如果我们曾经在一列遇到大于或等于两个 1 s，则排除不具有 1 秒。我们不顾排除那些同时提请我们进一步的垂直线。

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.

您看到这是在回事？

直到我们只有准确和左2尚未排除该行应继续下去。如果我们永远结束了比任何其他2，那么就意味着出事了：

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:

• 小于2意味着我们只有不到2线最初


• 更超过2指...
  
  
  
  • 如果有低于我们最初有，然后离开都应该是相同的那些
  
  
  • 如果有完全符合我们最初有尽可能多的，那么它可以是所有的都一样，或者每个可能的对是按位不同，这意味着每一个对产生 0
  
  
  • 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

    这里的code我已经写了下面我上面所描述的逻辑：

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

    下面的行动中是相同的： http://ideone.com/hRA8tn

    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.

    这篇关于最快和最有效的方式找到最​​没有。这可以通过执行按位与上排列的2个不同的元素来获得的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！