Есть ли возможность восстановить A в «A & B = C» с данными B и C?

Question

Я хотел бы спросить: с A, B и C - любое двоичное число. После получения C = A & B (& - AND оператор), есть ли возможность для восстановления A от B и C?

Я знаю, что информация A будет потеряна в результате операции. Можем ли мы сформировать такую ​​функцию, как B <...> C = A, и насколько она может быть сложной?

Например:

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

2-й бит C является 1, т.е. второй бит A и B должны быть 1. Однако другим битам не хватает информации для восстановления.

Заранее спасибо.

Answer 1

Вы не можете восстановить A, но напишите A = (X & ~B)^C. Здесь X может быть любым (и он дает все A).

Конечно, это будет работать только для B и C таких, что C & ~B == 0.

Это параметризованное решение. Пример в 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

Нет, это невозможно. Вы можете увидеть это из таблицы истинности для И:

A B C (A & B) 

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

Предположим, вы знаете, что B = 0 и C равен 0. может быть 1 или 0, поэтому он не может быть выведено из B и C.

Answer 3

Вы можете восстановить только биты A, которые имеют 1 s в соответствующих битах B. Для битов B, которые имеют нули не имеет значения, что A имеет в соответствующем положении, потому что бит в C будет равен нулю в любом случае:

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

Положения A отмеченные x могут быть нули или единицы; информация в них будет потеряна в любом случае.

Answer 4

Предполагая, что вы просто говорите двоичную логику, а не переменные C, то нет.

Рассмотрим: a=0111, b=1010 поэтому c=0010

Итак, вы b=1010, c=0010 так как теперь вы можете найти a?

Самый левый бит в c является 0, в b это 1, поэтому мы знаем a должно быть 0 Второй бит в c является 0, в b это 0, так что вы не можете сказать, что это было в a (либо 1, либо 0 приводит к 0 в c)

На этом этапе мы доказали, что вы не можете этого сделать.

Answer 5

Нет, потому что нет единственного решения. Любое значение A, которое имеет те же биты, что и B, удовлетворяет уравнению независимо от других бит.

Answer 6

Это вопрос об уравнениях. Это невозможно, так как степень свободы не равна нулю. Это то же самое, что и запрос a + b = 10 - что такое a и что такое b?