2

是否有一种算法可以找到按位或求和或线性时间复杂度的数组？

假设如果数组是 {1,2,3}，那么所有对的和 id 为 1|2 + 2|3 + 1|3 = 9。

我可以使用以下算法在 O(n) 中找到所有对 AND 总和....如何更改它以获取所有对 OR 总和。

int ans = 0;  // Initialize result

// Traverse over all bits
for (int i = 0; i < 32; i++)
{
    // Count number of elements with i'th bit set
    int k = 0;  // Initialize the count
    for (int j = 0; j < n; j++)
        if ( (arr[j] & (1 << i)) )
            k++;

    // There are k set bits, means k(k-1)/2 pairs.
    // Every pair adds 2^i to the answer. Therefore,
    // we add "2^i * [k*(k-1)/2]" to the answer.
    ans += (1<<i) * (k*(k-1)/2);
}

从这里：http ://www.geeksforgeeks.org/calculate-sum-of-bitwise-and-of-all-pairs/

4

1 回答 1

6

您可以在线性时间内完成。思路如下：

  1. 对于每个位位置，记录数组中将该位设置为 1 的条目数。在您的示例中，您有 2 个条目（1 和 3）设置了个位，2 个条目设置了二进制位（2和 3)。

  2. 对于每个数字，通过单独查看每个位并使用缓存的总和，计算该数字与数组中所有其他数字的按位或的总和。例如，考虑总和 1|1 + 1|2 + 1|3 = 1 + 3 + 3 = 7。

    因为 1 的最后一位是 1，所以按位或与 1 的结果将最后一位设置为 1。因此，所有三个数字 1|1、1|2 和 1|3 的最后一位都将等于 1 . 其中两个数字的二进制位设置为 1，这恰好是二进制位设置为 1 的元素的数量。通过将这些位组合在一起，我们可以得到总和 3*1（三个 1 位）+ 2 *2（两个二进制位）= 7。

  3. 对每个元素重复此过程可让您计算数组中所有有序元素对的所有按位或的总和。因此，在您的示例中，将计算 1|2 和 2|1，以及 1|1。因此，您必须减去 1|1 之类的所有情况，然后除以 2 以解决重复计算的问题。

让我们为您的示例尝试此算法。

  1. 以二进制形式写入数字，{1,2,3} = {01, 10, 11}。有 2 个数字设置了一个位，2 个数字设置了二进制位。

  2. 对于 01，我们得到 3*1 + 2*2 = 7 作为 ors 的总和。

  3. 对于 10，我们得到 2*1 + 3*2 = 8 作为 ors 的总和。
  4. 对于 11，我们得到 3*1 + 3*2 = 9 作为 ors 的总和。
  5. 将这些相加，7+8+9 = 24。我们需要减去 1|1 = 1、2|2 = 2 和 3|3 = 3，因为我们将这些计算在总和中。24-1-2-3 = 18。
  6. 最后，当我们两次计算 1|3 之类的东西时，我们需要除以 2。 18/2 = 9，正确的和。

该算法是 O(n * 任何数组元素中的最大位数)。

编辑：我们可以通过简单地从所有对中减去所有 0-0 对的计数来修改您发布的算法，以获得每个位位置的所有 0-1 或 1-1 对。像这样：

int ans = 0;  // Initialize result

// Traverse over all bits
for (int i = 0; i < 32; i++)
{
    // Count number of elements with i'th bit not set
    int k = 0;  // Initialize the count
    for (int j = 0; j < n; j++)
        if ( !(arr[j] & (1 << i)) )
            k++;

    // There are k not set bits, means k(k-1)/2 pairs that don't contribute to the total sum, out of n*(n-1)/2 pairs.
    // So we subtract the ones from don't contribute from the ones that do.

    ans += (1<<i) * (n*(n-1)/2 - k*(k-1)/2);
}
于 2016-08-25T17:36:44.833 回答