所有数对的异或和的总和

Question

所有数对的异或和的总和

8

我们有一个数组A（比如[1, 2, 3]）。我们需要找出数组中所有整数对的XOR(^)SUM。尽管可以轻松地在O(n^2)时间复杂度内完成它，但我该如何改进解决方案的复杂性呢？例如，对于上面的数组A，答案将是(1^2)+(1^3)+(2^3)=6 谢谢。

- pranay

我认为您所说的“sum”是指按位或。 - Matt

将所有不同的数对进行异或操作，并计算所有这些值的总和。 - pranay

在这种情况下，我得到了 1^2+1^3+2^3 = 3 + 2 + 1 = 6。 - Matt

谢谢Matt，问题已更新。 - pranay

1

对于 [1,2,2] 应该是什么答案呢？是 (1^2)+(1^2)=6，还是 1^2=3？如果是前者，则在问题中指定“不同的一对”是不必要的，因为 2^2=0 无论如何都不会对总和产生贡献。 - Matt

在这种情况下，答案将是6。 - pranay

3个回答

1

这里有一个jsFiddle，证实了interjay的答案，使用了O(N^2)和O(Nk)两种方法进行计算。

var list = [1,2,2,3,4,5]

function xorsum_on2( a )
{
    var sum = 0
    for( var i=0 ; i<a.length ; ++i )
        for( var j=i+1 ; j<a.length ; ++j )
            sum += a[i]^a[j]
    return sum
}

// This sets all elements of a to 0
function xorsum_onk( a )
{
    var allzeroes;
    var sum = 0;
    var power = 0;
    do {
        allzeroes = true;
        var bitcount = [0,0];
        for( var i=0 ; i<a.length ; ++i )
        {
            bitcount[a[i]&1]++;
            a[i] >>= 1;
            if( a[i] ) allzeroes = false;
        }
        sum += (bitcount[0]*bitcount[1]) << power++;
    } while( !allzeroes );
    return sum;
}


var onk = document.getElementById("onk")
var on2 = document.getElementById("on2")

on2.innerHTML = xorsum_on2(list)
onk.innerHTML = xorsum_onk(list)

- Matt

0

#include <iostream>
using namespace std;

int main() {
    long long int n,i,j,k;

    cin>>n; // number of elements in array 
    long long int arr[n],ans=0;

    for(i=0;i<n;i++)
        cin>>arr[i];

    // iterate through all the bits
    for(i=0;i<32;i++)
    {
        k=0; // k is the number of set bits in the array at ith psotion
        for(j=0;j<n;j++)
            if((arr[j] & (1<<i)))
                k++;
        /* there are k set bits and n-k unset bits.
            therefore number of pairs with one set bit and one unset bit is kC1 and n-kC1
            Every pair adds 2^i in the answer.
        */
        ans+= (1<<i)*(k*(n-k));     
    }
    cout<<ans<<endl;
    return 0;
}

- coderbhai

这个答案有什么补充？（如果Matt的答案只包含位运算方法，我认为它是边缘的。） - greybeard

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- interjay · Accepted Answer

您可以将计算分解为一次只计算一个位。

例如，查看数组中所有数字的最右边一位。假设有 a 个数字的右边有一个 0 位，还有 b 个数字的右边有一个 1 位。那么在这些数对中，a*b 个数对将在 XOR 的最右边一位上有一个 1。这是因为有 a*b 种方法来选择一个具有 0 位和一个具有 1 位的数字。这些位将对所有 XOR 的总和贡献 a*b。

一般而言，当查看第 n 位（最右边的位为第 0 位）时，请计算有多少个数字是 0（称之为 a_n），有多少个数字是 1（称之为 b_n）。它们对最终结果的贡献将是 a_n*b_n*2ⁿ。您需要对每个位进行这个操作，并将所有这些贡献相加。

这可以在 O(kn) 的时间内完成，其中 k 是给定值中的位数。