Count subsets with zero sum of xors 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$?
 A: 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}.$$
A: Combine the following bits:


*

*All the possible subset sums occur.

*They all occur equally often, because the subset $S$ XOR-sums to zero if and only if the symmetric difference of $S$ and $\{k\}$ XOR-sums to $k$.


Therefore the fraction of subsets with zero sum is $1/2^N$ of all the subsets. In other words

$2^{2^N-N}$.


This could also be written using the language of vector space over the field $\Bbb{F}_2$. Essentially you are counting the number of words in a Hamming code.
