给定OR值的一对数字数量

Question

有没有可能编写一个函数，该函数接受n个整数的数组和一个整数k，并以比O（n ² ）更好的时间返回具有位OR值等于k的数组元素对的数量？

示例：如果我们有一个数组=[21，10，29，8]和k = 31，则函数应返回2，因为有效对是（21,10）和（10,29）。 * 为了清晰起见 * 21 OR 10 = 31，21 OR 29 = 29，21 OR 8 = 29，10 OR 29 = 31，10 OR 8 = 10，29 OR 8 = 29，所以答案是2。

**** k是一个恒定值，始终为31. ****

- Madfish

---

你能提供一个例子吗？ - David_Zizu

让我们有一个数组array = [21, 10, 29, 8] 和 k = 31，那么答案将会是2，有效的组合为(21, 10)和(10, 29)。 - Madfish

@GeeTransit：问题中提到了“按位或”。 - Eric Postpischil

你应该澄清关于如何考虑k对时间的影响的问题。正如我发布的答案所示，这项工作可以在O(n+k^2)的时间内完成。如果将k视为常数，则为O(n)。如果k不是常数，则可能存在比O(n+k^2)更快的解决方案。 - Eric Postpischil

@EricPostpischil，嗯，在我的情况下，k实际上是一个常数，其值为2^(给定数组的最大元素的二进制表示中的位数) -1。 - Madfish

Answer 1

假设时间单位是作用于跨越k的字长的基本操作，那么O（n + k²）是可能的：

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

#define NumberOf(a) (sizeof (a) / sizeof *(a))


static unsigned Count(size_t N, unsigned *A, unsigned k)
{
    //  Count number of elements with each pattern of bits in k.
    unsigned *C = calloc(k + 1, sizeof *C);
    if (!C) exit(EXIT_FAILURE);
    for (size_t n = 0; n < N; ++n)
        if ((A[n] & ~k) == 0) ++C[A[n]];

    //  Count number of solutions formed with different values.
    unsigned T = 0;
    for (size_t i = 0; i < k; ++i)
    for (size_t j = i+1; j <= k; ++j)
        if ((i | j) == k)
            T += C[i] * C[j];

    //  Add solutions formed by same value (only possible when both are k).
    T += C[k] * (C[k]-1) / 2;

    free(C);

    return T;
}


int main(void)
{
    unsigned A[] = { 21, 10, 29, 8 };
    printf("%u\n", Count(NumberOf(A), A, 31));
}

这可以简化为O(n + p²)，其中p是k中设置的位数，通过将每个数组元素压缩为仅包含这些位（删除不在k中的位并将剩余位移连续）来实现。此外，可以改进计算组合的主循环，但我认为这不会影响O()时间。

- Eric Postpischil

---

很棒的解决方案，大粉丝 :) - Madfish

在 for 循环中的 j 之前，可能值得添加一个检查 C[i] == 0 的语句吗？ - Alan Birtles

Answer 2

人们认为答案是否定的。 假设您的k是2^s - 1（因此在二进制中为111…111），并且所有数字最多为k。那么：

a or b = k <=> (~a) and (~b) = 0.

, where ~ is a "bitwise not". E.g.

110 or 101 = 111 <=> 001 and 010 = 0

这是一个一般的正交向量问题（OVP），普遍的猜想是它的解法速度不会比 O(n^2) 更快（有些细节我省略了）。

请参见此处的猜想1: https://arxiv.org/pdf/1510.02824.pdf。

- Reputation Farmer

---

不，Eric Postpischil的解决方案非常好，比O(n^2)快得惊人。 - Madfish

你是如何测试的？对于 k = (1 << 31) - 1，它需要很长时间。 - Reputation Farmer

@AdityaRoshan：我的回答和他的不同，因为它们回答了不同的问题，这取决于k是否被视为常数。 - Eric Postpischil

@AdityaRoshan，将来请在问题中说明您只对k = 31感兴趣。 - Reputation Farmer

@ReputationFarmer 好的，谢谢您的时间，非常抱歉，我在这里还是新手。 - Madfish