Hey guys, I am working some logic problems and it is just not clicking. I am supposed to write the expression x^y (xor) using only ~ and &.
I think (~x&y)|(x&~y) is what the answer would be if we were allowed to use the | operator, but since we can't I am not sure how its done.
any pointers? Thanks in advance
Truth table - Wikipedia, the free encyclopedia
Try to derive the answer using truth tables, not by writing random expressions to see what works.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
Meanwhile, elsewhere on the interwebs
XOR help - Dev Shed
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
I checked out the truth tables but i cant figure out how to apply them to this situation to find the answer.
say x=4 and y=5, how would you construct that table? i know you would convert to binary but I am not sure how to draw the table out.
and yea, i was looking thru Dev Shed forums for help too so i figured i would post it there as well... bad form? (if so... why?)
00000000
There's a byte. Pick one end of it and use it for 1
10000000 or 00000001
Now you wanted four and five:
00100000 or 00000100
10100000 or 00000101
Now using & and ~ see what you can figure out. You may as well read this while you are at it: Cprogramming.com FAQ > Bit shifting and bitwise operations
Quzah.
Hope is the first step on the road to disappointment.
That was pretty confusing. I am not sure if you are shifting or what, either way I am not allowed to use the shift operator. what do you mean pick one end of the byte and use it for 1?Originally Posted by quzah
four and five would be
01000000 or 00000100
10100000 or 00000101, right?
i did ~4 & 5 and got 00010000. but i am not sure what to do with that info
here is the function, i am supposed to change the return to make it work
as you can see the example returns 1 so i feel like I am on the right track but it looks like i am supposed to be using way more operators than just 2 so the answer cant just be (~x&y).Code:/* * bitXor - x^y using only ~ and & * Example: bitXor(4, 5) = 1 * Legal ops: ~ & * Max ops: 14 * Rating: 1 */ int bitXor(int x, int y) { return ?
Do it longhand ... pencil and paper
Same answer...PHP Code:4 = 00000100
5 = 00000100
Not 4 = 11111011 (~ operator)
And 5 00000101 (& operator)
========
00000001
4 = 00000100
xor 5 00000101
========
00000001
here is the function, i am supposed to change the return to make it workCode:/* * bitXor - x^y using only ~ and & * Example: bitXor(4, 5) = 1 * Legal ops: ~ & * Max ops: 14 * Rating: 1 */ int bitXor(int x, int y) { return (~x) & y; }
No. The "or" there means you can pretend the 1 is on the left:
10000000
or on the right:
00000001
It doesn't actually matter, it's just whatever you prefer to show it as. If you will notice, everything on each side was a complete mirror. That should have clued you in.
Quzah.
Hope is the first step on the road to disappointment.
Your original equation is Or(And(Not(A),B),And(A,Not(B)))
You've only got one disallowed operation, an Or which has to change to some set of And and/or Not.
Let And(Not(A),B) = X and And(A,Not(B)) = Y, so you can simplify down to Or(X,Y) to save me some typing.
Applying two Nots to any function leaves it unchanged so do : Or(X,Y) = Not(Not(Or(X,Y)))
Apply DeMorgan's theorem. Change Not(Or(X,Y)) = And(Not(X),Not(Y)). Substitute this back into the equation above and expand out X and Y again - they haven't changed.
There you go, you changed your only Or operation to an And so you're all set. And you're way under the limit for operations.
