如何反转位或操作？

Question

这是我所做的：

93 | 199

返回

223

我知道这是因为0b1011101 | 0b11000111等于0b11011111

但是，如果我想进行反向操作，如何从0b11000111和0b11011111的按位操作中获取0b1011101？

- dopatraman

---

你可以生成所有可能的答案，但它们可能会呈指数级增长（1的数量的3次方）。 - harold

Answer 1

在一般情况下，您无法得到明确的答案。如果C = A | B，那么无论您在C和B中哪里有一个1，在A相应的位上，它可能是0或1都有可能。

以您的示例为例，93|199=223，但92|199也等于223。因此，对于给定的223和199，没有单一的答案（实际上，在这个示例中有32个可能的答案）。

- jez

Answer 2

正如这里所指出的那样，OR和AND都是破坏性操作。反转OR操作是一种有损失的操作，正如“jez”所提到的，可能会有多个答案。因此，不可能实现。

唯一可逆操作是XOR，因为它是非破坏性的。

- Aseem Yadav

---

XOR 不破坏性的好处是什么？ - gyuunyuu

Answer 3

保留位频表

虽然仅通过位运算无法确定性地获取其他操作数，但这可能会有所帮助。

您可以保留一张表来存储位频率。然后，您想要从OR结果中删除的数字，需要减少该数字中“设置”（1）为1的位的频率。在答案中，“设置”那些频率大于零的位。

示例：

A   :   0101  
B   :   1110  

------------  
OR :    1111 

[frequency]
+-+-+-+-+  
|1|2|1|1|  
+-+-+-+-+

Now, you have the OR and B, you want to get A back. 
Decrease the frequency table in indices where B has set bits.

[frequency-updated]
+-+-+-+-+  
|0|1|0|1|  
+-+-+-+-+
As you can see, the non-zero indices indicates where the A's bits were set.

这个过程可以扩展到N个数字的集合，其中你有N个数字的按位OR，并且你想知道如果从集合中'去掉'某个数字X，那么OR会是什么。

- Sojal

---

完美的答案。我一直在寻找它：）。不要忘记提到复杂度，即log（size_of_n）。 - Hussein Hammoud