CODEWITHSUNDEEP
vb.netvb6bit-manipulationbitwise-operators
Wynx
Wynx

Reputation: 13

Realize XNOR gate using AND, OR and NOT gates

As the title says, I'm trying to realize an XNOR gate using the following three gates: AND, OR, NOT.

Here's the way I did it: TextBox1.Text = (a And b) Or (Not a And Not b)

The following code gives me an output of -5, when the expected output is 11 for the input a = 10, b = 14.

I'm trying to understand what I'm doing wrong - my XOR gate works fine, XNOR doesn't.

Upvotes: 1

Views: 1428

Answers (1)

Joel Coehoorn
Joel Coehoorn

Reputation: 415690

Let's work through this by hand. For simplicity I'll start with a "reduced" 4-bit integer. So let's look at our initial bits:

a = 10 = 1010
b = 14 = 1110

And now substitute in the parts of the full expression:

a AND b 
1010 & 1110 = 1010

Not a = 0101
Not b = 0001

Not a And Not b
0101 & 0001 = 0001

The full thing:

(a And b) Or (Not a And Not b)

1010 | 0001 = 1011

So we have 1011 as the result.

This looks like an 11 at first, but we're forgetting something important: we're not using unsigned integers. We need to allow for negative values and answer the important question whether this is a negative or a positive value.

For negative values, we represent the bits using information from this guide (short version: invert the bit pattern and add 1 to convert a positive number to negative, invert the process -- subtract one first -- to convert negative to positive).

The result is if it's positive, it's 11. But if it's negative, it's -5. Hmm.... wait a minute. Those values look familiar! But which is correct?

To find out, let's try this again with a five-bit integer.

a = 10 = 01010
b = 14 = 01110

Substitute in the parts of the full expression:

a AND b 
01010 & 01110 = 01010

Not a = 10101
Not b = 10001

Not a And Not b
10101 & 10001 = 10001

The full thing:

(a And b) Or (Not a And Not b)

01010 | 10001 = 11011

This is a new bit pattern! 11 no longer makes sense at all (we'd have 27 instead). However, treated as a negative value, we still get -5. Moreover, as we keep adding bits to our integer the bits will always result in 1s added to left in the final bit pattern. However, this pattern will still always produce -5 no matter how many bits we add, where the original 11 will keep getting larger. Finally, there is this excerpt from my earlier link:

How you can be sure this number is negative? ... If the first bit is a 1, the number is negative.

Because we have a leading 1, the number should be treated as negative, meaning -5 is the correct result of the code.

What happened is the 4-bit value hid this by effectively overflowing our integer. If we have to allow for negative values, 4 bits only goes to ±7. But I wanted to show the 4-bit version first, to show the 11/-5 split.

Finally, let's look at the correct expression (using a 5-bit integer again):

(a And b) Or (Math.Abs(Not a) And Math.Abs(Not b))

a = 10 = 01010
b = 14 = 01110

Substitute in the parts of the full expression:

a AND b 
01010 & 01110 = 01010

Not a = 10101
Not b = 10001

Math.Abs(Not a) = 01011 ' Subtract 1, invert pattern
Math.Abs(Not b) = 01111

Math.Abs(Not a) And Math.Abs(Not b) 
01011 & 01111 = 01011

The full thing:

(a And b) Or (Not a And Not b)

01010 | 01011 = 01011

And this finally produces the expected 11.

Upvotes: 5

Related Questions