Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

sum of xor values of all pairs

Tags:

algorithm

xor

We have an array A (say [1,2,3]) . We need to find the XOR(^)SUM of all pairs of integers in the array. Though this can easily be done in O(n^2) but how can i improve the complexity of the solution ? E.g for the above array , A, the answer would be (1^2)+(1^3)+(2^3) = 6 Thanks.

like image 444
pranay Avatar asked Jan 27 '14 18:01

pranay


People also ask

How do you find the sum of XOR?

The XOR sum of a list is the bitwise XOR of all its elements. If the list only contains one element, then its XOR sum will be equal to this element. For example, the XOR sum of [1,2,3,4] is equal to 1 XOR 2 XOR 3 XOR 4 = 4 , and the XOR sum of [3] is equal to 3 .

How do you find the XOR of all elements in a list?

Approach: In order to find the XOR of all elements in the array, we simply iterate through the array and find the XOR using '^' operator.


2 Answers

You can separate the calculation to do one bit at a time.

For example, look at the rightmost bit of all the numbers in the array. Suppose that a numbers have a rightmost 0-bit, and b numbers have a 1-bit. Then out of the pairs, a*b of them will have 1 in the rightmost bit of the XOR. This is because there are a*b ways to choose one number that has a 0-bit and one that has a 1-bit. These bits will therefore contribute a*b towards the total of all the XORs.

In general, when looking at the nth bit (where the rightmost bit is the 0th), count how many numbers have 0 (call this an) and how many have 1 (call this bn). The contribution towards the final sum will be an*bn*2n. You need to do this for each bit and sum all these contributions together.

This can be done in O(kn) time, where k is the number of bits in the given values.

like image 100
interjay Avatar answered Sep 22 '22 15:09

interjay


Here is a jsFiddle confirming interjay's answer which does the calculation using both methods O(N^2) vs 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)
like image 36
Matt Avatar answered Sep 22 '22 15:09

Matt