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

Question

The question looks pretty well worded

I have a virtual machine that implements only AND, XOR, SHL and SHR, but I have to perform the operation "OR 0x01".

Answer 1

First of all, the correct bitwise calculation for the following two variables is enough, since 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

therefore, if we connect them to xor, we are done.

(A xor B) xor (A and B)

Answer 2

I would start with

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

and untie some Boolean algebra on it until it looks like

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

Admittedly, this is probably more work than actually than moving on to “trying every conceivable bit combination,” but then you came up with ideas for solving homework. :)

Answer 3

The truth table summarized on Wikipedia here and a sigh, basic material CS 101, De Morgan Law ....

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


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


 Xor
 0 ^ 0 0
 0 ^ 1 1
 1 ^ 0 1
 1 ^ 1 0

A Left shift involves moving 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 actions on the truth table above ...

Answer 4

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