所有对按位或求和

Question

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

假设如果数组是{1,2,3}那么所有pair sum 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 的条目数。在您的示例中，您有 2 个条目（1 和 3）设置了个位，2 个条目设置了二进制位集（2 和 3）。
对于每个数字，通过单独查看每个位并使用缓存的总和来计算该数字与数组中所有其他数字的按位或的总和。例如，考虑总和 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（三个位) + 2*2 (两个二进制位) = 7.
对每个元素重复此过程可以计算数组中所有有序元素对的所有按位或的总和。因此，在您的示例中，将计算 1|2 和 2|1，以及 1|1。因此，您必须减去所有情况，例如 1|1，然后除以 2 以计算重复计数。

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

用二进制写出数字，{1,2,3} = {01, 10, 11}。有 2 个数字设置了一个位，2 个设置了二进制位。
对于 01，我们得到 3*1 + 2*2 = 7 的总和。
对于 10，我们得到 2*1 + 3*2 = 8 的总和。
对于 11，我们得到 3*1 + 3*2 = 9 的总和。
对这些求和，7+8+9 = 24。我们需要减去 1|1 = 1、2|2 = 2 和 3|3 = 3，因为我们在求和中计算了这些。 24-1-2-3 = 18.
最后，由于我们数了两次像 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);
}

所有对按位或求和

All pair Bitwise OR sum

bit-manipulation

bit

bitwise-or