Is there any possibility to recover A in "A & B = C" with given B and C?

Question

I would like to ask: with A, B, and C are any binary number. After getting C = A & B (& is AND operator), is there any possibility to recover A from B and C?

I know that the information of A will be lost through the operation. Can we form a function like B <...> C = A, and how complexity it can be?

For example:

A = 0011
B = 1010
C = A & B = 0010

The 2nd bit of C is 1, i.e. 2nd bit of A and B must be 1. However, the other bits lack information to be recovered.

Thank you in advance.

Answer 1

You can't recover A, but you can write A = (X & ~B) ^ C. Here, X can be anything (and it gives all the A's).

Of course this will work only for B and C such that C & ~B == 0.

This is a parametrized solution. Example in python

>>> A = 32776466
>>> B = 89773888
>>> C = A & B
>>> C
22020352
>>> X = 1234567890    # arbitrary value
>>> U = (X & ~B) ^ C
>>> U
1238761874
>>> U & B     # same result as A & B
22020352

Answer 2

This is a question about equations. It is not possible as the degree of freedom is not zero. It is the same as asking a+b = 10 -- what is a and what is b?

Answer 3

No, it's not possible. You can see this from the truth table for AND:

A  B  C (A & B)

0  0  0
0  1  0
1  0  0
1  1  1

Suppose you know that B is 0 and C is 0. A could be either 1 or 0, so it cannot be deduced from B and C.

Answer 4

You can recover only bits of A that have 1s in the corresponding bits of B. For bits of B that have zeros it does not matter what A has in the corresponding position, because the bit in C would be zero anyway:

A = 1xx0x011x0
B = 1001011101
    ----------
C = 1000001100

Positions of A marked with x can be zeros or ones; the information in them is going to be lost either way.

Answer 5

Assuming you are just talking binary logic not C variables, then no.

Consider: a=0111, b=1010 therefore c=0010

So you have b=1010, c=0010 so now how can you find a?

The left most bit in c is a 0, in b it is 1 so we know a it must be 0 The second bit in c is 0, in b it is 0 so you can't tell what it was in a (either 1 or 0 leads to a 0 in c)

At this point we've proven you can't do it.

Answer 6

No, because there isn't a unique solution. Any value of A that has the same bits set as B would satisfy the equation, regardless of the other bits.