所有对按位或总和

Question

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

假设如果数组是 {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/

Answer 1

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

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

2. 对于每个数字，通过单独查看每个位并使用缓存的总和，计算该数字与数组中所有其他数字的按位 OR 的总和。例如，考虑总和 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 个数字设置了 1 位，2 个数字设置了 2 位。

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

3. 对于 10，对于 ors 的总和，我们得到 2*1 + 3*2 = 8。
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);
}