时间戳

首页 > 解决方案 > 具有给定 OR 值的对数

algorithm - 具有给定 OR 值的对数

问题描述

是否可以编写一个函数，该函数接受一个由n 个整数组成的数组和一个整数k ，并在比 O( n 2 ) 时间更好的时间内返回具有 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 .****

标签： algorithmbit-manipulation

解决方案

假设时间单位是对跨越k的字长的基本操作，那么 O( n + k 2 ) 是可能的：

#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 2 )，其中p是在k中设置的位数，通过将每个数组元素压缩到仅这些位（删除不在k中的位并将剩余位移动为连续的）。此外，可以改进计算组合的主循环，但我认为这不会影响 O() 时间。

推荐阅读