Logical XOR

M

Martin Wells

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
 
F

fred.l.kleinschmidt

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
 
M

Michal Nazarewicz

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

Keith Thompson

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

Tor Rustad

Martin said:
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
 
A

Army1987

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)).
 
C

CBFalconer

Keith said:
(e-mail address removed) writes:
.... snip ...

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

pete

Martin said:
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;
}
 
M

Martin Wells

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
 
M

Michal Nazarewicz

Army:
Martin Wells said:
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.
 
M

Martin Wells

Michal:
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
 
M

Malcolm McLean

Martin Wells said:
Michal:



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

David Thompson

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top