Finding XOR of All Subsets – Algorithm and Explanation

algorithms

Moderator's note: this is an on going contest problem. Per usual protocol the answers have been hidden and the question is locked until the end date of the contest. (21.03.2014)

Given a list containing N integers, How to find the XOR_SUM of all the non-empty subsets of the list.

E.g. XOR_SUM of list A having three elements {X1, X2, X3} can be given as follows.
All non-empty subsets will be {X1, X2, X3, (X1,X2), (X2,X3), (X1,X3), (X1,X2,X3)}

XOR_SUM(A) = X1 + X2 + X3 + X1^X2 + X2^X3 + X1^X3 + ((X1^X2)^X3)

EXAMPLE : Let N=3 and list be [1,2,3] then here answer will be 12 as Their will be 7 non-empty subsets whose XOR is given below

1 = 1
2 = 2
3 = 3
1^2 = 3
2^3 = 1
3^1 = 2
1^2^3 = 0

So sum of all such XORs will 12.

Best Answer

Consider one bit position at a time. How many of the terms have bit $i$ set? The terms that have bit $i$ set are exactly those that correspond to a subset that contains an odd number of inputs that have bit $i$ set.

  • If there is any input that has bit $i$ set, then exactly half of the $2^N$ possible subsets will be of this form, and so they will contribute $2^{N-1+i}$ to the final sum.

  • On the other hand, if no input has bit $i$ set, then of course no terms will have that bit set either.

Summing these contributions of $2^{N-1+i}$ per bit position is easy enough -- the final sum will simply be $2^{N-1}$ times the bitwise OR of all the inputs.

Related Question