1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.