Logical XOR

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

1. Martin WellsGuest

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

2. Martin WellsGuest

> !!a != !!b

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

!a != !b

Martin

Martin Wells, Sep 21, 2007

3. 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
4. Martin WellsGuest

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

> 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
6. Keith ThompsonGuest

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

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>

8. Army1987Guest

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
9. CBFalconerGuest

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
10. peteGuest

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;

do {
}
return byte;
}

--
pete

pete, Sep 21, 2007
11. Martin WellsGuest

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
12. Michal NazarewiczGuest

> 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
13. Martin WellsGuest

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
14. Malcolm McLeanGuest

"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
15. David ThompsonGuest

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