# 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$?

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}.$$

• How to find this formula (2^2^N − N) MOD m where m is a prime number ? – user3804397 Feb 21 '15 at 8:48

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.

• @JykriLahtonen How to find this formula (2^2^N − N) MOD m where m is a prime number ? – user3804397 Feb 21 '15 at 8:47