XOR of Binary Numbers to Reach a Given Number

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

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

• IOW, the subset sum problem is much, much harder. – Jyrki Lahtonen Apr 14 '13 at 13:04
• Thank You! Can I get a reference link on how to find whether the augmented matrix is solvable ? The size of the set S can be upto 1000. I just need to find whether a solution exists or not. – Kyuubi Apr 14 '13 at 13:13
• It is the row reduction algorithm from Linear Algebra. Transform the matrix into a row echelon form. The system is solvable, if and only if you don't get a row of the form $(0\ 0\ 0\ \cdots\ 0\ |\ 1)$. – Jyrki Lahtonen Apr 14 '13 at 13:18
• I tried reducing the matrix to a row echelon form. But with the modulo 2 arithmetic operations, the row echelon form seems to be unreachable. (eg) if the set S = {0010, 1001, 1010, 0101, 1110, 1100 } and X = {0001}, how do I follow the reduction procedure ? I have to develop a c++ implementation for a 1000x200 matrix. – Kyuubi Apr 14 '13 at 14:55
• @Kyuubi: I added an example run solving your example case. – Jyrki Lahtonen Apr 14 '13 at 19:14