# Finding XOR of all subsets

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.

• it works well if any number in set is even but if set consists of only odd numbers like 3 ,5 then it fails
– user136278
Mar 18, 2014 at 15:46

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.

• So basically the solution for a given set x1,x2,x3,x4...xn is : (x1 | x2 | x3 |x4 |...xn ) * ( 2^N-1) ; But this is not working for all the test cases in a challenge ..?? Any suggestion why Mar 16, 2014 at 22:24
• @prateeak: Yes, that's what the answer ought to be. What do you men by "not working" -- are you using too small ints to hold the result, perhaps? Mar 16, 2014 at 22:57
• Temporarily deleting this answer as it is from an on-going programming contest. Mar 21, 2014 at 10:01
• Hi Henning Makholm, thanks for detailed explanation, however I have a doubt ....ORing the number will give you all possible 1 positions in that column so you get all possible 1 positions in all the columns. I also got that only half of the subsets will have some particular bit position set to 1, but why multiplying this OR of all numbers with half the number of subsets will give you answer? Sep 5, 2015 at 5:26
• @codeomnitrix: Because you're adding the XORs from each subset. Half of the subsets will contribute one copy of that bit to the final sum. Sep 5, 2015 at 13:48