找到最大编号的最快且最有效的方法。可以通过对数组的 2 个不同元素执行按位与来获得

给定一个非负整数数组，找到最大数的最快、最有效的方法是什么。可以通过对数组的 2 个不同元素执行按位与（即 & 运算符）来获得？

到目前为止，这是我的代码：

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

当然，这是一种简单的方法。我正在寻找更有效的解决方案。

也许类似于使用 trie（实际上是二叉树）来查找数组元素的最大异或。最大异或解决方案的描述可以在以下位置找到：http://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems?share=1 http://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems?share=1

我希望我的问题是正确的。这是我的解决方案：

您有一个整数数组，假设它们是无符号整数，因为我们正在处理按位运算。让我们将它们视为二进制表示形式的一串零和一，然后将它们放在一起。

现在我们已经将它们对应的位垂直对齐了。让我们从最左边的列开始绘制垂直线。如果我们遇到超过或等于两个1s 在一列中，然后排除没有 s 的每一行1s。在绘制进一步的垂直线时，我们要忽略那些被排除的因素。

你明白这是怎么回事吗？

这将继续下去，直到我们只剩下两行未被排除的行。如果我们最终得到的不是 2，那么就意味着出了问题：

• 小于 2 意味着我们最初的行数少于 2 条
• More than 2 means that...
  • 如果少于我们最初的数量，那么剩下的应该都是相同的
  • 如果与我们最初的数量完全相同，那么可能所有的都是相同的，或者每个可能的对都是按位不同的，这意味着每个对都会产生0

这是我编写的代码，遵循上面描述的逻辑：

#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 http://ideone.com/hRA8tn

我不确定这是否是最好的，但它应该比全部测试更好。