CODEWITHSUNDEEP
bit-manipulation
Flavius
Flavius

Reputation: 13816

how to calculate bitwise OR using AND, XOR and shift?

The question seems pretty well formulated

I have a virtual machine which implements only AND, XOR, SHL and SHR, yet I have to do a "OR 0x01" operation.

Upvotes: 5

Views: 14139

Answers (4)

Chris Dodd
Chris Dodd

Reputation: 126185

I would just expand DeMorgan's law: A or B = not(not A and not B). You can compute not by XORing with all 1 bits.

Upvotes: 0

ndim
ndim

Reputation: 37767

I would just start with

a xor b = ((not a) and b) or (a and (not b))

and unleash some boolean algebra on that until it looks like

a or b = <expression using only and, xor>

Admittedly, this is probably more work to actually do than going the "try every conceivable bit combination" route, but then you did ask for homework solution ideas. :)

Upvotes: 2

t0mm13b
t0mm13b

Reputation: 34592

The truth table as summarized on Wikipedia here and gasp, basic CS 101 stuff, De Morgan's Law....

AND
0 & 0   0
0 & 1   0
1 & 0   0
1 & 1   1


OR
0 | 0   0
0 | 1   1
1 | 0   1
0 | 0   1


XOR
0 ^ 0   0
0 ^ 1   1
1 ^ 0   1
1 ^ 1   0

A Shift Left involves shifting the bits across from right to left, suppose:

+-+-+-+-+-+-+-+-+
|7|6|5|4|3|2|1|0|
+-+-+-+-+-+-+-+-+
|0|0|0|0|0|1|0|0| = 0x4 hexadecimal or 4 decimal or 100 in binary
+-+-+-+-+-+-+-+-+

Shift Left by 2 places becomes
+-+-+-+-+-+-+-+-+
|7|6|5|4|3|2|1|0|
+-+-+-+-+-+-+-+-+
|0|0|0|1|0|0|0|0| = 0x10 hexadecimal or 16 decimal or 10000 in binary
+-+-+-+-+-+-+-+-+

Shift Right by 1 places becomes
+-+-+-+-+-+-+-+-+
|7|6|5|4|3|2|1|0|
+-+-+-+-+-+-+-+-+
|0|0|0|0|1|0|0|0| = 0x8 hexadecimal or 8 decimal or 1000 in binary
+-+-+-+-+-+-+-+-+

Then it is a matter of combining the bit-wise operations according to the truth table above...

Upvotes: 1

user282727
user282727

Reputation: 674

First of all having a correct bitwise computation for the following two variables is sufficient, because they cover all combinations:
A=0101
B=0011

We want
0101
0011
A or B
0111

for xor we get

0101
0011
A xor B
0110

for and we get

0101
0011
A and B
0001

so if we connect them with an xor we are done.

(A xor B) xor (A and B)

Upvotes: 6

Related Questions