Given an integer $N$. Consider set $S=\{0, 1,…, 2^N−1\}$. How many subsets $A\subset S$ with Xor of all elements of $A$ as zero are there ?
Note : The Xor sum of an empty set is zero and Xor here is a bit wise operation.
Example : Let $N=2$ then answer is $4$
Here are $4$ subsets : empty set, $\{0\}$, $\{1,2,3\}$, $\{0,1,2,3\}$ as all have Xor sum as zero.
How to find this count for given $N$?
Best Answer
Any subset of $S$ must have a XOR-sum in $S$. Also, if you consider the subset $T=\{1=2^0,2^1,\ldots,2^{N-1}\}$ of $S$, given any element $s$ of $S$, there is a unique subset of $T$ with XOR-sum $s$, which is given by choosing the elements of $T$ corresponding to the bits in the binary expansion of $s$ which are $1$. Therefore, to find a subset $S'$ of $S$ with XOR-sum zero, you can choose the intersection of $S'$ with $S\setminus T$ freely, and then there is a unique way to choose $S'\cap T$ which will make the overall XOR-sum zero. The number of ways to choose a subset of $S$ with XOR-sum zero is then the number of subsets of $S\setminus T$, which is $$2^{\#(S\setminus T)}=2^{2^N-N}.$$