1
$\begingroup$

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
$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ IOW, the subset sum problem is much, much harder. $\endgroup$ – Jyrki Lahtonen Apr 14 '13 at 13:04
  • $\begingroup$ 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. $\endgroup$ – Kyuubi Apr 14 '13 at 13:13
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Jyrki Lahtonen Apr 14 '13 at 13:18
  • $\begingroup$ 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. $\endgroup$ – Kyuubi Apr 14 '13 at 14:55
  • $\begingroup$ @Kyuubi: I added an example run solving your example case. $\endgroup$ – Jyrki Lahtonen Apr 14 '13 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.