3
$\begingroup$

Suppose that $Z = X \vee Y$, where $X$, $Y$ and $Z$ are 96-bit binary numbers. If I'm given the values of $Z$ and $Y$, is it possible to work out what $X$ is?

I know this is possible with XOR but can it be done with OR?

$\endgroup$
1
  • $\begingroup$ For each 0 bit in Z you know that corresponding bit in X and Y have to be 0. For each 1 bit in Z, X and Y can be any of (1,1) (0,1) (1,0). Now if Y bit is 0 then you can infer X bit as 1 BUT if the Y bit 1 then X bit can be 1 or 0 and there is no way to figure out which one it is. $\endgroup$ – Ankur Oct 19 '15 at 12:52
7
$\begingroup$

It is easy to find out that there can be more than one value, used as $X$, to satisfy $Z = X \vee Y$. When a specific bit of $Y$ is $1$, there are two possibilities for such bit in $X$, i.e., $0$ or $1$.

Let's make a simple example with a 2-bit number:

$Y$ = $10$ and $Z$ = $11$

The possible values of $X$ are:

  • $11$
  • $01$

because:

  • $11 \vee 10 = 11$
  • $01 \vee 10 = 11$

In short, you don't have the certainty that the end result of the reverse operation of $\vee$ will be a unique result.

$\endgroup$
8
  • $\begingroup$ X, Y, Z are 96 bits binary numbers. EX: Z = 001100010001010000100101011110111111010101110100010110000101011000101010000011100001111000000000 $\endgroup$ – SHdotCom Oct 19 '15 at 4:08
  • 1
    $\begingroup$ It does not matter how many is the number of bits of $Z$. You can save 96-bit numbers in two 64-bit integers: long long in C++, and Long in Java, or you can preserve it in a string data type. Then, let us assume that $Z = 1111$ and $Y = 1111$. $X$ could be from $0000$ to $1111$; therefore there is no a single value for $X$ to obtain. $\endgroup$ – beginner1010 Oct 19 '15 at 4:49
  • $\begingroup$ @beginner1010's point is that the problem is the same whether you are talking about 1 bit or 96 bits, as the bits in two 96 bit number are treated independently by $\lor$. $\endgroup$ – Dave Clarke Oct 19 '15 at 8:37
  • $\begingroup$ @Dave Clarke if I have Z = 01111100110110101001011111111101111111111111101101101101011110111011110100000011‌​1110011010101110 Y= 01101100010100101001010111101001110101011101000101100001010110001010100000000011‌​1100000000001010 Is it possible to get X value which is equal to : 01011000100010100001001010111101111110101011101000101100001010110001010100000000‌​0110011010100100 From Z and Y ?? $\endgroup$ – SHdotCom Oct 19 '15 at 8:45
  • 8
    $\begingroup$ @SHdotCom: First, think about whether you can do this for a 1-bit number. It's the same problem for a 96-bit number, just 96 times. $\endgroup$ – Dave Clarke Oct 19 '15 at 8:56

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.