2
$\begingroup$

I have the following equations I need to solve for A and B:

       2A ⊕ B = 7
       A ⊕ B = 14

Note:
All variables are unsigned 32-bit integers
⊕ is the XOR operator for 32-bit integers.

$\endgroup$
  • $\begingroup$ $A=7, B=9$. Not known if answer is unique, though. $\endgroup$ – Zhuoran He Oct 24 '17 at 5:13
  • $\begingroup$ It's not unique at all. Take any integer of the form $m\cdot 2^4$ and add it to both of them, and the xor is unchanged. $\endgroup$ – Arthur Oct 24 '17 at 5:27
  • $\begingroup$ Hey, thanks for the answer,but what method do you use? $\endgroup$ – Berkane Brahim Oct 24 '17 at 5:46
2
$\begingroup$

XOR is the same as addition in the finite field $F_2$. Thus if we assume a solution exists with $A<8$ and $B<16$ (reasonable given the magnitudes of the right-hand sides) you can rewrite your equations as \begin{align*} \left[\begin{array}{cccc}0 & 1 & 0 & 0\\0 & 0& 1 & 0\\0 & 0& 0& 1\\0 & 0& 0&0\end{array}\right]\mathbf{A} + I_{4\times 4}\mathbf{B} &\equiv \left[\begin{array}{c}0\\1\\1\\1\end{array}\right]\\ I_{4\times 4}\mathbf{A} + I_{4\times 4}\mathbf{B}&\equiv\left[\begin{array}{c}1\\1\\1\\0\end{array}\right] \end{align*} in $F_2$, with the vector $\mathbf{A}$ containing the bits of $A$ (from most to least significant).

We thus have an $8\times 8$ linear system over $F_2$, which you can row-reduce to get $$\left[\begin{array}{cccccccc}1 & 0 &0 &0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\ 0 & 0 &0 &0 &1 & 1 & 0 &0\\ 0 & 0 &0 &0 &0 & 1 & 1 &0\\ 0 & 0 &0 &0 &0 & 0 & 1 &1\\ 0 & 0 &0 &0 &0 &0 &0 &1 \end{array}\right]\left[\begin{array}{c}\mathbf{A}\\\mathbf{B}\end{array}\right] \equiv \left[\begin{array}{c}1\\1\\1\\0\\0\\1\\0\\1\\1\end{array}\right]$$ and finally back-substitute to get $$\mathbf{A} = \left[\begin{array}{c}0\\1\\1\\1\end{array}\right], \mathbf{B}=\left[\begin{array}{c}1\\0\\0\\1\end{array}\right].$$

But wait, as pointed out in the comments, the answer isn't unique... that's right, notice that at the beginning we assumed that both $A$ and $B$ had at most 4 bits, and that $A<8$. If we allow larger $A$ or $B$ we get larger linear systems (which will be rank-deficient).

$\endgroup$
  • $\begingroup$ how about 32 bits? $\endgroup$ – Berkane Brahim Oct 24 '17 at 21:09
  • $\begingroup$ @BerkaneBrahim Sure? Just set up the exact same type of linear system (it will be 64 x 64). $\endgroup$ – user7530 Oct 24 '17 at 22:47

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.