1. ## XOR Logic Help

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.

2. Truth table - Wikipedia, the free encyclopedia
Try to derive the answer using truth tables, not by writing random expressions to see what works.

3. Meanwhile, elsewhere on the interwebs
XOR help - Dev Shed

4. 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?)

5. 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.

6. Originally Posted by quzah
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?

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
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 ?```
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).

7. Originally Posted by Yabssato
That was pretty confusing.
Do it longhand ... pencil and paper
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 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;
}```

8. 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.

9. Originally Posted by Yabssato
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.

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.