Printable View
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.
Meanwhile, elsewhere on the interwebs
XOR help - Dev Shed
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.
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?Quote:
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 paperQuote:
Originally Posted by Yabssato
Same answer...PHP Code:4 = 00000100
5 = 00000100
Not 4 = 11111011 (~ operator)
And 5 00000101 (& operator)
========
00000001
4 = 00000100
xor 5 00000101
========
00000001
Quote:
here is the function, i am supposed to change the return to make it work
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 (~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.
Your original equation is Or(And(Not(A),B),And(A,Not(B)))Quote:
Originally Posted by Yabssato
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.