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?
$\begingroup$
$\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
Add a comment
|
$\begingroup$
$\endgroup$
8
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.
-
$\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 = 011111001101101010010111111111011111111111111011011011010111101110111101000000111110011010101110 Y= 011011000101001010010101111010011101010111010001011000010101100010101000000000111100000000001010 Is it possible to get X value which is equal to : 010110001000101000010010101111011111101010111010001011000010101100010101000000000110011010100100 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
