Manipulating Bit-wise Operations

Question

There is this puzzle question of creating an equivalent bit-wise & with only | and ~ operators.

I've been doing brute force combinations of | and ~ using 6 (0110) and 5 (0101) trying to get 4 (0100), but I still cannot get the answer.

The maximum number of operation can be used is 8.

Can someone please give me hints?

Answer 1

What helps you here is De Morgan's Law, which basically says:

~(a & b) == ~a | ~b

Thus we can just negate this and get:

a & b == ~(~a | ~b)     //4 operations

And looking at the truth table (and in fact, god bless the simplicity of binary logic, there are only four possible combintations of inputs to generate the appropriate outputs for) we can see that both are equivalent (last two columns):

a | b | ~a | ~b | ~a OR ~b | ~(~a OR ~b) | a AND b
--|---|----|----|----------|-------------|--------
0 | 0 |  1 |  1 |     1    |      0      |    0
1 | 0 |  0 |  1 |     1    |      0      |    0
0 | 1 |  1 |  0 |     1    |      0      |    0
1 | 1 |  0 |  0 |     0    |      1      |    1

Answer 2

Truth table time...

A B A&B !A !B !A|!B !(!A|!B)
0 0  0   1  1   1       0
0 1  0   1  0   1       0
1 0  0   0  1   1       0
1 1  1   0  0   0       1