How to reverse a bitwise OR operation?

Question

Here's what I've done:

93 | 199

which returns

223

I understand that this is because 0b1011101 | 0b11000111 is 0b11011111

However, suppose I want to do the reverse operation. How do I get 0b1011101 from a bitwise operation between 0b11000111 and 0b11011111?

Interval

You could generate all possible answers, there may be exponentially many of them though (3 to the power of the number of 1's) – Electrical

Answer 1

You can't get an unambiguous answer in the general case. If C=A|B, then wherever you have a 1 in C and a 1 in B, the corresponding bit of A could have been either 0 or 1.

In your example, 93|199=223, but 92|199 is also 223. So, given 223 and 199 there's no single answer (in fact, in this example there are 32 possible answers).

Merrygoround

Answer 2

Keep Bit Frequency Table

Although there is no deterministic way to get other operand back using only bit-wise operation, this may help.

You can keep a table to store the bit frequency. Then the number you want to remove from the OR result, decrease frequency of bits where the bit is 'set'(1) for this number. The places where the frequency is greater than zero, 'set' those bits in the answer.

Example:

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.

This process can be extended to set of N numbers, where you have bit-wise OR of N numbers and you want to know what the OR would be 'without' some number X from the set.

Complexity

Time Complexity: For a number N, time complexity for a single operation is log(N), since there are log(N) number of bits to iterate.

Space Complexity: For M amount of numbers with size N, space complexity is Mlog(N), since there are log(N) bits to store for all M numbers.

Thanks @hussein-hammoud for mentioning the complexity.

Tedford

perfect answer. was looking for it :). Don't forget to mention the complexity which is log(size_of_n) – Heavy

Answer 3

As pointed out here, both OR and AND are destructive operations. Reversing OR operation is a lossy operation and as mentioned by 'jez' can have more than one answer. So, it is not possible

Only reverse operation possible is for XOR as it is non-destructive.

Geddes

what are the benefits of xor being non destructive? – Concrescence