# How the xor sum algorithm is connected with or?

I was searching for a solution to the problem: For a given array of numbers find the sum of xor of all possible subsets. Here xor of a subset is the value comes from xoring all the elements of that subset

Answer of this question gives a solution. But didn't understand how the or comes in the solution [see the last line of the accepted answer].

Can you explain?

## 1 Answer

I suggest you follow through the example using the set $\{1,4,5\}$. There are eight subsets. Four of them have their XOR odd, so the $2^0$ bit is set and four have their XOR even, so the $2^0$ bit is cleared. When we add these up, we get $2^{3-1}$ times the value of the bit. None of the subsets have the $2^1$ bit set in their XOR because none of the original numbers have their $2^1$ bit set. The bitwise OR you are asking about is saying to find all the bits that are set in at least one of the original numbers. For our set $\{1,4,5\}$, that bitwise OR is $101_2=5$ and the sum will be $2^{3-1}\cdot 5=20$