Like Tree1Likes
  • 1 Post By Salem

XOR Logic Help

This is a discussion on XOR Logic Help within the C Programming forums, part of the General Programming Boards category; Hey guys, I am working some logic problems and it is just not clicking. I am supposed to write the ...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    3

    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.

    any pointers? Thanks in advance

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,420
    Truth table - Wikipedia, the free encyclopedia
    Try to derive the answer using truth tables, not by writing random expressions to see what works.
    CommonTater likes this.
    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 support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,420
    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 support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Sep 2011
    Posts
    3
    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. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.

  6. #6
    Registered User
    Join Date
    Sep 2011
    Posts
    3
    Quote Originally Posted by quzah View Post
    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. #7
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Yabssato View Post
    That was pretty confusing.
    Do it longhand ... pencil and paper
    PHP Code:
    00000100
    00000100

    Not 4 
    11111011  (~ operator)
    And 
    5   00000101  (& operator)
            ========
            
    00000001

    =   00000100
    xor 5 00000101
          
    ========
          
    00000001 
    Same answer...

    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. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.

  9. #9
    Registered User
    Join Date
    Mar 2009
    Posts
    343
    Quote Originally Posted by Yabssato View Post
    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
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logic help...
    By csharp100 in forum C Programming
    Replies: 8
    Last Post: 09-14-2010, 11:29 PM
  2. wat is the logic behind this?
    By vpshastry in forum C Programming
    Replies: 18
    Last Post: 12-10-2009, 12:55 PM
  3. Help with logic
    By Ducky in forum C++ Programming
    Replies: 5
    Last Post: 12-05-2009, 10:49 AM
  4. The Logic
    By reRanger in forum C++ Programming
    Replies: 1
    Last Post: 11-24-2004, 11:31 PM
  5. Logic?
    By planet_abhi in forum Game Programming
    Replies: 1
    Last Post: 01-18-2003, 02:46 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21