最大化 AND

Question

给定一个由 n 个非负整数组成的数组：A1, A2, ..., AN。如何找到一对整数 Au, Av (1 ? u < v ? N) 使得 (Au 和 Av) 尽可能大。

示例：让 N=4 和数组为 [2 4 8 10] 。这里的答案是 8

解释

2 and 4 = 0
2 and 8 = 0
2 and 10 = 2
4 and 8 = 0
4 and 10 = 0
8 and 10 = 8

如果 N 可以达到 10^5，该怎么办。我有 O(N^2) 解决方案。但效率不高

代码 ：

for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
        if(arr[i] & arr[j] > ans)
        {
            ans=arr[i] & arr[j];
        }
    }
}

Answer 1

您可以加快速度的一种方法是利用以下事实：如果任何高位设置为任意两个数字，那么这两个数字的 AND 将始终大于使用低位的任何组合。

因此，如果您按设置的位数对数字进行排序，则可能会大大减少操作次数。

为了有效地找到最重要的位，GCC 有一个内置的内在函数：__builtin_clz(unsigned int x)它返回最重要的设置位的索引。（其他编译器具有类似的内在函数，至少在 x86 上转换为单个指令）。

const unsigned int BITS = sizeof(unsigned int)*8; // Assuming 8 bit bytes.

// Your implementation over.
unsigned int max_and_trivial( const std::vector<unsigned int> & input);    

// Partition the set.
unsigned int max_and( const std::vector<unsigned int> & input ) {
    // For small input, just use the trivial algorithm.
    if ( input.size() < 100 ) { 
        return max_and_trivial(input);
    }        

    std::vector<unsigned int> by_bit[BITS];

    for ( auto elem : input ) {
         unsigned int mask = elem;
         while (mask) { // Ignore elements that are 0.
             unsigned int most_sig = __builtin_clz(mask);
             by_bits[ most_sig ].push_back(elem);
             mask ^= (0x1 << BITS-1) >>  most_sig;
         }
    }

    // Now, if any of the vectors in by_bits have more 
    // than one element, the one with the highest index 
    // will include the largest AND-value.

    for ( unsigned int i = BITS-1; i >= 0; i--) {
        if ( by_bits[i].size() > 1 ) {
             return max_and_trivial( by_bits[i]);
        }
    }

    // If you get here, the largest value is 0.
    return 0;
}

该算法的最坏情况运行时间仍然为 O(N*N)，但平均而言它应该表现得更好。您还可以通过在搜索较小的向量时重复分区步骤来进一步提高性能（请记住忽略分区步骤中的最高有效位，这样做应该将性能提高到 O(N) 的最坏情况）。

保证输入数据中没有重复将进一步提高性能。