具有给定OR值的对数

Question

是否可以编写一个函数，该函数接受n个整数和整数k的数组，并在比O（n ²）时间更好的情况下返回BITWISE 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的常数。****

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

This can be reduced to O(n + p²), where p is the number of bits set in k, by compressing each array element to just those bits (removing bits not in k and shifting the remaining bits to be contiguous). Also, the main loop that counts the combinations could be improved, but I do not think that affects the O() time.