Xor of all subsets of a given set of size n

/* Xor of all subsets of a given set of size n */

/* Understand like this. Consider ith bit of all inputs. Count the number of 1's and the number of 0's. So suppose at the ith bit we have K 1's and N-K 0's. Then out of all 2^n subsets, those subsets which have odd number of 1's will give 1 as XOR output at the ith bit and the other subsets will give zero. Now you can prove that independent of K, exactly 2^(n-1) subsets will have odd number of ones. (provided K>0)

Proof : KC1*2^(N-K) + KC3*2^(N-K) + ... = 2^(K-1) * 2^(N-K) = 2^(N-1)

   (KC1 is the usual Combinatoric i.e. K!/1!(K-1)!)*/

/*Solution: Find the OR of all the elements and multiply it with 2^(n-1) where n is the total number of elements. This gives us the answer.

Idea:

There will be a total of 2^n subsets.
If ith bit of any element is set, then that bit will be set in the xor of half of the total subsets which is 2^(n-1).
To find out all of the set bits in all of the numbers we find the OR of all of the numbers.
Since each set bit appears in half of the total subsets, we multiply the OR of all of the numbers with 2^n-1 to get the final result */