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

Question

Hi

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.

Answer 1

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)

Answer 2

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