如何反转按位或运算？

Question

这是我所做的：

93 | 199

返回

223

我明白这是因为

0b1011101 | 0b11000111

是

0b11011111

但是，假设我想做相反的操作。如何从

0b1011101

和

0b11000111

之间的按位运算得到

0b11011111

？

Answer 1

一般情况下你无法得到明确的答案。如果

C=A|B

，那么只要 C 中有 1，B 中有 1，A 的相应位就可以是 0 或 1。

在您的示例中，93|199=223，但 92|199 也是 223。因此，给定 223 和 199，没有单一答案（事实上，在本示例中，有 32 个可能的答案）。

Answer 2

正如here所指出的，OR和AND都是破坏性的运算。反转 OR 运算是一种有损运算，正如“jez”提到的，可以有多个答案。 所以，这是不可能的

仅可进行反向操作XOR，因为它是非破坏性的。

Answer 3

保留比特频率表

虽然没有确定的方法可以仅使用按位运算来获取其他操作数，但这可能会有所帮助。

您可以保留一个表来存储位频率。然后，您要从 OR 结果中删除的数字，降低该数字的“设置”(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 个数字进行按位或，并且您想知道“没有”集合中的某个数字 X 时，OR 会是什么。

复杂性

时间复杂度：对于数字 N，单个操作的时间复杂度为 log(N)，因为有 log(N) 需要迭代的位数。

空间复杂度：对于 M 个大小为 N 的数字，空间复杂度为 Mlog(N)，因为有 log(N) 位可存储所有 M 数字。

感谢@hussein-hammoud 提到复杂性。