CODEWITHSUNDEEP
pythonbit-manipulationbitwise-operatorsbitwise-or
dopatraman
dopatraman

Reputation: 13908

How to reverse a bitwise OR operation?

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?

Upvotes: 15

Views: 24795

Answers (3)

Sojal
Sojal

Reputation: 161

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.

Upvotes: 12

jez
jez

Reputation: 15349

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).

Upvotes: 28

Aseem Yadav
Aseem Yadav

Reputation: 778

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.

Upvotes: 3

Related Questions