与最大值 AND 值配对

Question

给定一个非常大的整数数组，其中的元素可以达到 10^9，我如何找到具有最大值 AND 值的对。我目前的方法是计算所有可能的对并遍历它并找到最大值，但是它非常慢。还有其他方法吗？

Answer 1

只要你能找到至少两个最高有效位设置相同的数字，解决方案将涉及其中两个。

接下来，舍弃所有其他元素，并移除此MSB剩余的所有未舍弃数字，并解决同样的问题。直到你只剩下两个数字或没有什么可做的。

例如：

 input  || first iteration | second iteration
=================================================================
1110010 ||       x         |        x
0110111 ||   discarded     |    discarded        
1000000 ||       x         |    discarded
1000010 ||       x         |        x
=================================================================
=> solution: first and last

这是O(n log max_element)。

Answer 2

查看两个连续数字n - 1 和n 的位模式不同的第一个位置。片刻的反思表明，对于 n，该位必须为 1，对于 n - 1，该位必须为 0。否则不能。在那个位的左边，一切都相等，在那个位的右边，两者中较大的只有 0，较小的只有 1。不然就不行了。

因此我们有：

n           -> (common prefix) 1 0*
n - 1       -> (common prefix) 0 1*
-----------------------------------
n & (n - 1) -> (common prefix) 0 0*

示例：

88          -> 101 1 000
87          -> 101 0 111
------------------------
88 & 87     -> 101 0 000

共享前缀可以为空，带重复位（0*和1*的东西）的星尾可以为空。

尾部总是变成全零，所以如果它存在，则 (n - 1) & (n - 2) 必须大于 n & (n - 1)，因为 (n - 1) 全为 1在那个地方并且 (n - 2) 只缺少最后一位。它还必须大于 n 以内范围内的所有其他对 AND。

如果尾部不存在 - 也就是说，如果 n 是奇数 - 那么 n & (n - 1) 具有 n 之前整个范围的最大 AND 值。如果不是很明显：'the tail is present' 的另一个表达式是 'n is even'。

需要特殊处理的一种情况是 B = A + 1，即如果范围具有尽可能短的长度。在那种情况下，如果 B 是偶数，就没有 (B - 2) 可以依靠。

因此，对于范围 [A, B] 且 A < B 的最大 AND 的计算变为；

if ((B & 1) == 1 || A > B - 2)
    return B & (B - 1);
else
    return (B - 1) & (B - 2);

要获得完整的 Monty，请查看 my submission HackerEarth。

只有在发布答案后，我才发现本主题中讨论的问题与 HackerEarth 上的 Maximum AND 略有不同，因为处理是针对给定的输入向量而不是连续范围进行的的数字。

如果在排序序列的向下扫描过程中发现合适的连续值，上述方案仍然可以提供早出条件，但有用的可能性可以忽略不计。

这是一个函数，可以通过从末尾向后扫描来识别排序序列中的最高共享位。它通常只需要扫描很少的元素就可以完成。由于最多 B 位的 select 多于 B + 1 个值而不共享任何位，因此该函数必须通过仅检查其上端的对数少数值来找到已排序序列的共享高位。

static int common_high_bit (int[] v, int lo, int hi)
{
    int shared = 0;

    for (int seen = 0, i = hi - 1; i >= lo && v[i] >= shared; --i)
    {
        int m = shared | seen & v[i];

        if (m > shared)  // discovered a higher shared bit
        {
            m |= m >>  1;
            m |= m >>  2;
            m |= m >>  4;
            m |= m >>  8;
            m |= m >> 16;

            shared = m;
        }

        seen |= v[i];
    }

    return shared - (shared >> 1);
}

虽然没有必要对整个序列进行排序。执行堆排序的 'heapify' 步骤（可以在 O(n) 中完成）然后将最大值一个一个地提取并输入上述算法就足够了，直到它退出或输入耗尽.

一旦确定了高位，就需要从序列中提取所有设置了该位的值，第k位及其左侧的所有内容都归零，结果进行相同的处理。一旦候选集缩小到可管理的大小，简单的二次算法就可以比大型机器更有效地处理其余部分。

注意：共享高位不一定是 IVlad 的回答所暗示的 MSB。例如。考虑：

101xxxxx
 11xxxxx

可以看出，最高共享位不是任何一个数的MSB。

出于类似的原因，在屏蔽掉共享高位及其剩余部分之后，我们不能对剩余候选集中值的顺序进行大量假设。

然而，情况并不黯淡，因为异常的、不方便的星座不可能很多，一旦我们在序列中如此之低以至于共享的高位是那里值的 MSB，只有对数的几个值需要从中抽取出来完成下一步的候选集

与最大值 AND 值配对

Pair with Maximum AND value

algorithm

bitwise-operators

bitwise-and