1
$\begingroup$

Recently I encountered an interview question related to XOR and I have no idea how to figure it out. The question is as below:

The algorithm is: $A\oplus B$ (operation) $C = D$

We have the value of $A$, $B$ and $D$. Please figure out the value of $C$ and the (operation). The $C$ is being dump as per the interviewer.

Is there a way to figure out the value of $C$ and the operation as in the question?

$\endgroup$
  • 1
    $\begingroup$ Do you have example values? $\endgroup$ – mikeazo Jan 30 '18 at 3:02
  • $\begingroup$ In general, no, there is clearly no way to identify the operation from a single equation: suppose you are given A = B = C = D = 0, then "operation" can be XOR, OR, or even AND, the equation will be satisfied every time. It's even worst if you are not given C. $\endgroup$ – Geoffroy Couteau Jan 30 '18 at 9:48
6
$\begingroup$

First of all I'll have to disagree with fkraiem that there are many possibilities. In fact there are exactly four. I'm going to assume that $A$, $B$, $C$, and $D$ are bits. (Or equivalently I'm assuming that they are bit-strings and the operation we are looking for a is a bitwise boolean operation.) Then I'll make my life a bit easier and define $E=A\oplus B$, since it does not matter what $E$ actually is.

Now, there are exactly 16 possible binary boolean operations. Not all of those actually have their own name, but they technically do exist and we could come up with a symbol for them. Assuming that we are supposed to find an operation and a description of $C$ in terms of $D$ and $E$ such that the equation is satisfied for all possible values of $E$ and $D$.

Then this leaves us with exactly 4 possibilities.

Namely

  1. XOR as the operator and $C=E\oplus D$.
  2. XNOR as the operator and $C= \neg(E\oplus D)$.
  3. The operator that always evaluates to the second value and $C=D$.
  4. The operator that always evaluates to the negation of the second value and $C=\neg D$.

The reason for this can be seen in the following table. For an operation to be viable, we need that it allows us to force any value of $D$ irrespective the value of $E$. This means we require that in the following table the operation has both a $0$ and a $1$ in each pair of columns in the following table. Otherwise there is always at least one combination of values for $E$ and $D$ that makes the equation unsatisfiable. It is easy to see that there are only 4 viable operations.

Table of all binary boolean operations.

$\endgroup$
  • 2
    $\begingroup$ "I'm going to assume that A, B, C, and D are bits." And what makes you think this assumption is reasonable? $\endgroup$ – fkraiem Jan 30 '18 at 5:00
  • $\begingroup$ @fkraiem Well, that doesn't really matter as long as we're talking about a bitwise boolean operation. It just makes thing simpler. $\endgroup$ – Maeher Jan 30 '18 at 5:22
  • 1
    $\begingroup$ And also: Because boolean values are generally what we apply boolean operation to. $\endgroup$ – Maeher Jan 30 '18 at 5:30
1
$\begingroup$

I could see that determining the operation and C is somewhat possible if the operation is bitwise operator. If other operations are allowed on group of bits together then all bets are off.

Furthermore, I don't see how you can distinguish between C and ~C (the negation of C) and a operator that performs the negation internally.

And to precisely determine the operator and C (besides the issues above) it may be required to see all the different values of A, B and D combined. This is not what is stated in the question.

This is reflected by the answer of Maeher, where 4 candidate sets are filtered out, assuming bitwise operations only and a single known set of values.

$\endgroup$
0
$\begingroup$

There are many possibilities; one is that the operation is XOR and C = A XOR B XOR D.

$\endgroup$
0
$\begingroup$

This appears to be an exercise in crypto breaking.

You work out the possible solutions by brute-force testing of every possible operation and every possible value of C in the equation, and the candidate correct answers are the ones where the equation works out correctly.

If the word size of the variables is relatively small (e.g. 8 to 16 bits), then a small program can generate all the possible answers reasonably quickly. As the word size gets bigger (64 bits or more), it takes longer & longer to do this within reasonable timescales.

$\endgroup$

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.