Logical XOR

Discussion in 'C Programming' started by Martin Wells, Sep 21, 2007.

  1. Martin Wells

    Martin Wells Guest

    Just wondering how you all go about performing a logical XOR in C. At
    the moment I'm doing:

    !!a != !!b

    , which is quicker to write than:

    (!a && b) || (a && !b)

    If we were to write it as a macro, how would we go about seeking the
    shortest execution time?

    Martin
     
    Martin Wells, Sep 21, 2007
    #1
    1. Advertising

  2. Martin Wells

    Martin Wells Guest


    > !!a != !!b



    About three seconds after I sent that post I realised I cuda written:

    !a != !b

    Martin
     
    Martin Wells, Sep 21, 2007
    #2
    1. Advertising

  3. Martin Wells

    Guest

    On Sep 21, 11:30 am, Martin Wells <> wrote:
    > > !!a != !!b

    >
    > About three seconds after I sent that post I realised I cuda written:
    >
    > !a != !b
    >
    > Martin


    If a and b are always boolean values (0 or 1), just use
    a^b
    --
    Fred
     
    , Sep 21, 2007
    #3
  4. Martin Wells

    Martin Wells Guest


    > If a and b are always boolean values (0 or 1), just use
    > a^b


    NO WAY, YOU'RE SUCH A GENIUS.

    If only I wanted a bitwise XOR, I'd be sorted.

    Martin
     
    Martin Wells, Sep 21, 2007
    #4
  5. > On Sep 21, 11:30 am, Martin Wells <> wrote:
    >> > !!a != !!b

    >>
    >> About three seconds after I sent that post I realised I cuda written:
    >>
    >> !a != !b


    writes:
    > If a and b are always boolean values (0 or 1), just use
    > a^b


    If they are not you can join those two techniques to form !a ^ !b which
    is probably faster then !a != !b because no branching is used (at least
    on some architectures).

    But, I assume that if at least one of the values (say a) is boolean the
    following will be even faster: ((unsigned)(((signed)a)-1)) & b. Not
    sure if it's not implementation specific though. (If neither is boolean
    replace a with !a). Disadvantage is that if b is not boolean this will
    not produce a boolean value.

    --
    Best regards, _ _
    .o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o
    ..o | Computer Science, Michal "mina86" Nazarewicz (o o)
    ooo +--<mina86*tlen.pl>---<jid:mina86*chrome.pl>--ooO--(_)--Ooo--
     
    Michal Nazarewicz, Sep 21, 2007
    #5
  6. writes:
    > On Sep 21, 11:30 am, Martin Wells <> wrote:
    >> > !!a != !!b

    >>
    >> About three seconds after I sent that post I realised I cuda written:
    >>
    >> !a != !b
    >>
    >> Martin

    >
    > If a and b are always boolean values (0 or 1), just use
    > a^b


    Boolean values aren't necessarily 0 or 1 (unless you're restricting
    yourself to the C99-specific type _Bool or bool); any non-zero value
    of any scalar type is treated as true.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Sep 21, 2007
    #6
  7. Martin Wells

    Tor Rustad Guest

    Martin Wells wrote:
    >
    > Just wondering how you all go about performing a logical XOR in C. At
    > the moment I'm doing:
    >
    > !!a != !!b
    >
    > , which is quicker to write than:
    >
    > (!a && b) || (a && !b)
    >
    > If we were to write it as a macro, how would we go about seeking the
    > shortest execution time?


    !a ^ !b

    --
    Tor <torust [at] online [dot] no>
     
    Tor Rustad, Sep 21, 2007
    #7
  8. Martin Wells

    Army1987 Guest

    On Fri, 21 Sep 2007 11:28:43 -0700, Martin Wells wrote:

    >
    >
    > Just wondering how you all go about performing a logical XOR in C. At
    > the moment I'm doing:
    >
    > !!a != !!b
    >
    > , which is quicker to write than:
    >
    > (!a && b) || (a && !b)
    >
    > If we were to write it as a macro, how would we go about seeking the
    > shortest execution time?

    If the second one is written as a macro, you can't know how many
    times a and b are evaluated unless you know their truth value
    beforehand. Beware of side effects. Go for (!(a) ^ !(b)).
    --
    Army1987 (Replace "NOSPAM" with "email")
    If you're sending e-mail from a Windows machine, turn off Microsoft's
    stupid “Smart Quotes†feature. This is so you'll avoid sprinkling garbage
    characters through your mail. -- Eric S. Raymond and Rick Moen
     
    Army1987, Sep 21, 2007
    #8
  9. Martin Wells

    CBFalconer Guest

    Keith Thompson wrote:
    > writes:
    >

    .... snip ...
    >>
    >> If a and b are always boolean values (0 or 1), just use a^b

    >
    > Boolean values aren't necessarily 0 or 1 (unless you're restricting
    > yourself to the C99-specific type _Bool or bool); any non-zero value
    > of any scalar type is treated as true.


    If you are operating on !(expression) the values are always 0 or
    1.

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>


    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Sep 21, 2007
    #9
  10. Martin Wells

    pete Guest

    Martin Wells wrote:
    >
    > > !!a != !!b

    >
    > About three seconds after I sent that post I realised I cuda written:
    >
    > !a != !b


    That's how I write it.
    Take a look at the controling expression in the if statement:

    unsigned char bit_rev(unsigned char byte)
    {
    unsigned hi_mask = ((unsigned char)-1 >> 1) + 1;
    unsigned lo_mask = 1;

    do {
    if (!(byte & hi_mask) != !(byte & lo_mask)) {
    byte ^= hi_mask | lo_mask;
    }
    hi_mask >>= 1;
    lo_mask <<= 1;
    } while (hi_mask > lo_mask);
    return byte;
    }

    --
    pete
     
    pete, Sep 21, 2007
    #10
  11. Martin Wells

    Martin Wells Guest

    Army:

    > If the second one is written as a macro, you can't know how many
    > times a and b are evaluated unless you know their truth value
    > beforehand. Beware of side effects. Go for (!(a) ^ !(b)).



    The problem of multiple evaluation can be solved by simply making the
    macro name all uppercase.

    Martin
     
    Martin Wells, Sep 21, 2007
    #11
  12. > Army:
    >> If the second one is written as a macro, you can't know how many
    >> times a and b are evaluated unless you know their truth value
    >> beforehand. Beware of side effects. Go for (!(a) ^ !(b)).


    Martin Wells <> writes:
    > The problem of multiple evaluation can be solved by simply making the
    > macro name all uppercase.


    It doesn't solve the problem. It only gives a hint to programmer.

    --
    Best regards, _ _
    .o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o
    ..o | Computer Science, Michal "mina86" Nazarewicz (o o)
    ooo +--<mina86*tlen.pl>---<jid:mina86*chrome.pl>--ooO--(_)--Ooo--
     
    Michal Nazarewicz, Sep 22, 2007
    #12
  13. Martin Wells

    Martin Wells Guest

    Michal:

    > Martin Wells <> writes:
    > > The problem of multiple evaluation can be solved by simply making the
    > > macro name all uppercase.

    >
    > It doesn't solve the problem. It only gives a hint to programmer.



    It explicitly indicates to the programmer that they're dealing with a
    macro. Just like how we put a "THIS IS BLEACH" label on a container of
    bleach.

    Let them drink the bleach if they're really that incompetant.

    Or, if you *really* wanna spoonfeed them, write a compiler that warns
    when you pass a "side-effect expression" as an argument to a function
    macro.

    Martin
     
    Martin Wells, Sep 22, 2007
    #13
  14. "Martin Wells" <> wrote in message
    news:...
    > Michal:
    >
    >> Martin Wells <> writes:
    >> > The problem of multiple evaluation can be solved by simply making the
    >> > macro name all uppercase.

    >>
    >> It doesn't solve the problem. It only gives a hint to programmer.

    >
    >
    > It explicitly indicates to the programmer that they're dealing with a
    > macro. Just like how we put a "THIS IS BLEACH" label on a container of
    > bleach.
    >
    > Let them drink the bleach if they're really that incompetant.
    >
    > Or, if you *really* wanna spoonfeed them, write a compiler that warns
    > when you pass a "side-effect expression" as an argument to a function
    > macro.
    >

    It shouts.
    The problem is that most time is spent reading code, not writing it, and the
    shout is almost always a false warning. So people will mentally filter it
    out.

    It is like putting a red skull and crossbones on every single chemical in
    the lab that might be slightly toxic if ingested. The really nasty stuff
    then gets no emphasis.

    --
    Free games and programming goodies.
    http://www.personal.leeds.ac.uk/~bgy1mm
     
    Malcolm McLean, Sep 22, 2007
    #14
  15. On Fri, 21 Sep 2007 21:17:57 +0200, Michal Nazarewicz <>
    wrote:

    > > On Sep 21, 11:30 am, Martin Wells <> wrote:
    > >> > !!a != !!b
    > >>
    > >> About three seconds after I sent that post I realised I cuda written:
    > >>
    > >> !a != !b

    >
    > writes:
    > > If a and b are always boolean values (0 or 1), just use
    > > a^b

    >
    > If they are not you can join those two techniques to form !a ^ !b which
    > is probably faster then !a != !b because no branching is used (at least
    > on some architectures).
    >

    I don't know of any architecture where ! doesn't need conditional
    branching (the kind that usually matters here) but != does.

    > But, I assume that if at least one of the values (say a) is boolean the
    > following will be even faster: ((unsigned)(((signed)a)-1)) & b. Not
    > sure if it's not implementation specific though. (If neither is boolean
    > replace a with !a). Disadvantage is that if b is not boolean this will
    > not produce a boolean value.


    Doesn't do XOR for a==1 b==0. You can do & but I'm pretty sure you
    can't get nonboolean ^ to work because it's (algebraically) linear.

    The casts aren't needed if either a or b is unsigned (and not stricly
    narrower than int). unsigned_a - 1 wraps around safely. signed_a - 1
    gives an in-range signed value which automatically converts to
    unsigned when it meets unsigned_b across & . If both are signed using
    a -1U is enough to force (everything) unsigned (unless strictly wider
    than int, then you need -1UL or even -1ULL). Using the casts is
    arguably clearer, but if any of your nonbooleans are (or may be) wider
    than int you have to specify appropriately wide typenames.

    I think the only way to do this for XOR is to fully smear the/each
    nonboolean operand e.g.
    aa = a; aa |= aa >> 1; aa |= aa >> 2; aa |= aa >> 4; etc.
    bb = b similarly if necessary
    aa ^ bb
    You can shorten the dependency chain (which is limiting on some
    (most?) modern architectures) by doing somewhat more computation:
    aa = a; aa |= aa >> 1 | aa >> 2; aa |= aa >> 3 | aa >> 6; etc.

    - formerly david.thompson1 || achar(64) || worldnet.att.net
     
    David Thompson, Oct 8, 2007
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Buck Turgidson

    XOR Boolean

    Buck Turgidson, Apr 5, 2004, in forum: Java
    Replies:
    9
    Views:
    9,156
    Kristoffel
    Apr 5, 2004
  2. cryptogirl

    How can you xor ArrayLists?

    cryptogirl, Feb 24, 2006, in forum: Java
    Replies:
    8
    Views:
    943
    Shreyas Kothari
    Oct 28, 2014
  3. evan
    Replies:
    1
    Views:
    1,118
    John Harrison
    Jun 28, 2003
  4. Christopher Benson-Manica

    Why isn't there a logical XOR operator?

    Christopher Benson-Manica, Feb 3, 2004, in forum: C Programming
    Replies:
    80
    Views:
    3,419
    CBFalconer
    Feb 6, 2004
  5. Michael W. Ryder

    Logical XOR of strings

    Michael W. Ryder, May 30, 2006, in forum: Ruby
    Replies:
    9
    Views:
    439
    Martin DeMello
    May 31, 2006
Loading...

Share This Page