Given a set
S = { s1, s2, s3, ... sn}
of Binary Numbers , I need to find if a given Binary Number X with only 1 bit position set as 1 (..00001000…), can be reached by doing bitwise XOR operation.That is ,I need to find out if there is a subset of S such that
X = si (+) sj (+) sk ....
where (+) is XOR
I have read the dp approach given here, but I am not sure if it is valid for XOR as well.
EDIT :
Under what conditions will there be no solution?
(eg)
1) If all of {s1,s2,s3…. ,sn} have even number of bits, there can be no solution to X.
2) If none of the elements in S satisfy the condition,
X BITWISE AND si = X
Best Answer
Bitwise XOR is equal to bitwise addition modulo two. So you can treat this as a problem in linear algebra, and Gaussian elimination will solve it with polynomial complexity.
As an example, if $S=\{11001_2, 10101_2, 00111_2\}$, and you are asking whether $b_4b_3b_2b_1b_0$ is a bitwise XOR of a subset, all you need to is to check, whether the linear system of equations corresponding to the augmented matrix $$ \left( \begin{array}{ccc|c} 1&1&0&b_4\\ 1&0&0&b_3\\ 0&1&1&b_2\\ 0&0&1&b_1\\ 1&1&1&b_0\end{array}\right) $$ is solvable. Just do all the arithmetic modulo two.
An example run with $S=\{0010, 1001, 1010, 0101, 1110, 1100\}$ and $X=0001$. The augmented matrix is $$ \left( \begin{array}{cccccc|c} 0&1&1&0&1&1&0\\ 0&0&0&1&1&1&0\\ 1&0&1&0&1&0&0\\ 0&1&0&1&0&0&1\\ \end{array}\right) $$ We first do some row swaps. Move the third row to the top (need to get that $1$ to top left corner), but keep the initial top row as the second: $$ \left( \begin{array}{cccccc|c} 1&0&1&0&1&0&0\\ 0&1&1&0&1&1&0\\ 0&0&0&1&1&1&0\\ 0&1&0&1&0&0&1\\ \end{array}\right). $$ The first column looks good. To clear the second we need to add (=bitwise XOR) the second row to the last. That gives us $$ \left( \begin{array}{cccccc|c} 1&0&1&0&1&0&0\\ 0&1&1&0&1&1&0\\ 0&0&0&1&1&1&0\\ 0&0&1&1&1&1&1\\ \end{array}\right). $$ Swap the two bottom rows to end with $$ \left( \begin{array}{cccccc|c} 1&0&1&0&1&0&0\\ 0&1&1&0&1&1&0\\ 0&0&1&1&1&1&1\\ 0&0&0&1&1&1&0\\ \end{array}\right). $$ This is already in the echelon form, and we can already declare the calculation a success in the sense that a solution exists. Let $x_1,x_2,\ldots,x_6$ be the (binary) unknown coefficient of the six numbers. The two last variable do not correspond to initial $1$s on any row, and we can arbitrarily assign them to have whatever value we please. Let's pick $x_5=x_6=0$. This leaves the equation of the bottom row to read $$x_4+1\cdot 0+1\cdot 0=0$$ allowing us to solve $x_4=0$.
Plugging in the known values for $x_4,x_5,x_6$ to the equation of the third row gives then $$ x_3+1\cdot0+1\cdot0+1\cdot0=1 $$ giving us $x_3=1$. Repeating the dose with the second row gives $$ x_2+1\cdot1+1\cdot0+1\cdot0=0 $$ telling us that $x_2=1$. Finally, the first row gives us that $$ x_1+x_3+x_5=0, $$ completing our solution with $x_1=1$.
We see that a solution is $x_1=x_2=x_3=1$, $x_4=x_5=x_6=0$. Let's look at the ones. They occur as multipliers of the first three numbers: $0010,1001,1010$. Indeed, bitwise XORring these gives what we want $$ 0010 \operatorname{XOR} 1001 \operatorname{XOR} 1010 = 0001. $$