[comp.lang.c] "logical" xor

marcus@illusion.UUCP (Marcus Hall) (01/11/88)

In article <2946@zeus.TEK.COM> dant@tekla.UUCP (Dan Tilque) writes:
>>...I've often
>>needed and have had to kludge ((a != 0) ^ (b != 0)).

>It's not really a kludge so you can stop thinking of as such.  It is a bit
>verbose but you can just use (a ^ b) and it will do the same thing (*).
>...  The "bitwise" xor does exactly what you would want
>a "logical" xor to do.
>(*) Possibly it won't work where a and b are floats on a machine where
>(float) 0 does not have an all null bit pattern.  But in that case, neither
>will (a ^^ b).

Sorry, there is a difference.  Suppose that a==2 and b==3?  a ^ b == 1, which
is considered true.  ((a != 0) ^ (b != 0)) gives (1) ^ (1) == 0, which is
false.

> And there's no way to optimize an exclusive-or operation.

True, which is why there wasn't a "short circuiting" operator for exclusive
or.  The compiler could perhaps generate better code if a or b were simple
values already in registers in a limited number of cases, but a good optimizer
could probably spot these cases and turn out the same code anyway.  (If the
time spent looking for this optimization was considered worth the small gain
made by the optimization.)  It ends up being just a convenience for the
programmer, but since this construct isn't used nearly as often as && and
|| is, that isn't too bad.

>The only reason to add ^^ is esthetic.  That is, we have || and && as well
>as | and & so let's have ^^ along with ^.  However, that's a good reason
>not to use ^^ as exponentiation: people will get it mixed up with xor too
>easily.  (Of course, that didn't stop them from the = and == syntax :-)

Here I tend to agree with you, but there is a slight gain in not having to
optimize as much for the rare use of the ^^ operator.

>Dan Tilque

Marcus Hall
..!{ihnp4,mcdchg}!illusion!marcus

ljz@fxgrp.UUCP (Lloyd Zusman, Master Byte Software) (01/11/88)

In article <2946@zeus.TEK.COM> dant@tekla.UUCP (Dan Tilque) writes:
> ...
>Tell me, what is the ^^ supposed to add that is not already done by ^ ?
>The answer is nothing.  The "bitwise" xor does exactly what you would want
>a "logical" xor to do.  In fact, the terms "bitwise" and "logical" are
>misnomers.  They should be "unoptimized" and "optimized".  And there's no
>way to optimize an exclusive-or operation.
>
>The only reason to add ^^ is esthetic.  ...
> ...

I'm sorry, but I disagree.  Try running this program:

#include <stdio.h>

main()
{
    int a = 2;
    int b = 0;
    int c = 7;

    printf("a = %d, b = %d, c = %d\n", a, b, c);
    printf("a & b = %d\n", a & b);
    printf("a && b = %d\n", a && b);
    printf("a & c = %d\n", a & c);
    printf("a && c = %d\n", a && c);
    printf("a | b = %d\n", a | b);
    printf("a || b = %d\n", a || b);
    printf("a | c = %d\n", a | c);
    printf("a || c = %d\n", a || c);
}

The results that printed out on my machine are:
a = 2, b = 0, c = 7
a & b = 0
a && b = 0
a & c = 2
a && c = 1
a | b = 2
a || b = 1
a | c = 7
a || c = 1

In my opinion, this illustrates the *exact* reason for the two versions
of the 'and' and 'or' operators.  The 'bitwise' versions are needed for
bit testing, etc.  The 'logical' versions are guaranteed to result in
1 or 0.



-------------------------------------------------------------------------
 Lloyd Zusman
 Master Byte Software
 Los Gatos, California	    	    	Internet:   fxgrp!ljz@ames.arpa
 "We take things well in hand."	    	UUCP:	    ...!ames!fxgrp!ljz

dant@tekla.TEK.COM (Dan Tilque;1893;92-789;LP=A;60aC) (01/11/88)

I wrote about ((a != 0) ^ (b != 0)) not being a kludge and how ^ is the
same as ^^.

EVERTHING I WROTE WAS WRONG.  

Sorry, but every once in a while my brain goes out to lunch and I stop
thinking before posting.  NEVER MIND.

---
Dan Tilque

blm@cxsea.UUCP (Brian Matthews) (01/12/88)

Dan Tilque (dant@tekla.UUCP) writes:
|Doug Gwyn writes:
|>>>      a ^^ b
|>>I think this is about as good a notation as we can get [for exponentiation]
|>
|>However, as Karl pointer out, this would make a good logical exclusive-or
|>operator also, and I can see that the "strong argument" for exponentiation
|>would also apply, somewhat more weakly, to exclusive-or, which I've often
|>needed and have had to kludge ((a != 0) ^ (b != 0)).
|It's not really a kludge so you can stop thinking of as such.  It is a bit
|verbose but you can just use (a ^ b) and it will do the same thing (*).

No it won't.  Consider a == 1 and b == 2.  (a ^^ b) will result in 0,
(a ^ b) will result in 3, which aren't quite the same thing.  And, as
you point out later, (a ^ b) probably doesn't give anywhere near the
expected results that (a ^^ b) give when a and b are float types.

-- 
Brian L. Matthews                               "A power tool is not a toy.
...{mnetor,uw-beaver!ssc-vax}!cxsea!blm          Unix is a power tool."
+1 206 251 6811
Computer X Inc. - a division of Motorola New Enterprises

dlnash@ut-emx.UUCP (01/12/88)

In article <20153@teknowledge-vaxc.ARPA>, mkhaw@teknowledge-vaxc.ARPA (Mike Khaw) writes:
> 1^0 = 1; 0^0 = 0; 1^1 = 0 => logical xor should mean "does not equal",
> for which C has a perfectly good symbol, "!="
> 

Yes, but "logically" speaking, 1 == 2, since both are non-zero and hence
are both true.  Therefore 1 ^^ 2 should be false, but 1 != 2 is true. 
If you are dealing with non-canonical true-false values, this will hurt
you.  Of course, you can always use !x != !y to translate x and y into
canonical true-false values (or !!x != !!y if you want to be picky), but
that just makes things a little bit harder to understand. 


				Don Nash

UUCP:    ...!{ihnp4, allegra, seismo!ut-sally}!ut-emx!dlnash
ARPA:    dlnash@emx.utexas.edu                 ^^|^^^
                ^^^------------------------------+-- note new address
BITNET:	 CCEU001@UTADNX, DLNASH@UTADNX
TEXNET:  UTADNX::CCEU001, UTADNX::DLNASH

mkhaw@teknowledge-vaxc.ARPA (Mike Khaw) (01/12/88)

1^0 = 1; 0^0 = 0; 1^1 = 0 => logical xor should mean "does not equal",
for which C has a perfectly good symbol, "!="

Mike Khaw
-- 
internet:  mkhaw@teknowledge-vaxc.arpa
usenet:	   {uunet|sun|ucbvax|decwrl|uw-beaver}!mkhaw%teknowledge-vaxc.arpa
USnail:	   Teknowledge Inc, 1850 Embarcadero Rd, POB 10119, Palo Alto, CA 94303

pardo@uw-june.UUCP (01/12/88)

[ use "!=" for "^^" (logical xor) ]

Only works if the values you have are already 1/0 valued.  As with "^"
(bitwise xor)

int	x = 3,  y = 4;

	assert( x ^^ y == 0);
	assert( (x != y) == 1);


[ somebody else: logical xor is hard to optimize ]

True, in general, but the compiler (say, through flow analysis) may be
able to determine that one or both of the "^^" operands has just been
set by something that guarantees the result to be 0 or 1, in which case
the compiler can (safely!) reduce "^^" to "^".

I vote that

	if (a ^^ b) ...

is clearer than

	if ((a == 0) != (b == 0)) ...

or whatever the equivalent xor expression of choice happens to be.

	;-D on  (My favorite sintax: switch(x+=*a+++*b){...})  Pardo

gwyn@brl-smoke.UUCP (01/12/88)

In article <20153@teknowledge-vaxc.ARPA> mkhaw@teknowledge-vaxc.ARPA (Mike Khaw) writes:
>1^0 = 1; 0^0 = 0; 1^1 = 0 => logical xor should mean "does not equal",
>for which C has a perfectly good symbol, "!="

Although C doesn't enforce it, it is good style to maintain a careful
distinction between Boolean expressions and arithmetic expressions.
!= would best be considered an arithmetic operator.  This apart from
the fact that 2 XOR 1 would be 3 arithmetically but 0 as a Boolean
(not that I think one should be treating 2 as a Boolean value!).

By the way, I don't think a logical XOR is important enough to bother
adding to C.  It should be in the next conventional language you
design, however (Ada++?).

jfh@killer.UUCP (The Beach Bum) (01/12/88)

In article <195@fxgrp.UUCP>, ljz@fxgrp.UUCP (Lloyd Zusman, Master Byte Software) writes:
> In article <2946@zeus.TEK.COM> dant@tekla.UUCP (Dan Tilque) writes:
> > ...
> >Tell me, what is the ^^ supposed to add that is not already done by ^ ?
> >The answer is nothing.  The "bitwise" xor does exactly what you would want
> >a "logical" xor to do.  In fact, the terms "bitwise" and "logical" are
> >misnomers.  They should be "unoptimized" and "optimized".  And there's no
> >way to optimize an exclusive-or operation.

Only half true.  Actually, not true at all.  | and & operate on bits.  Calling
boolean operators an "optimized" version of a bit operator is a lot like
calling a type definition an "optimized" procedure call.

> >The only reason to add ^^ is esthetic.  ...
> > ...

True here.  The correct result can be had with little effort.  I would say
leaving out ^^ is at most being incomplete.

> I'm sorry, but I disagree.  Try running this program:
> 
[ eaten by the line eater ]
>  Lloyd Zusman

Here is the macro for you impatient people:

#define	XOR(a,b)	(((a)==0)!=((b)==0))

Unless I am missing something very subtle in the casting that will go on
if the macro is call with floating point expressions, this thing should
work like a dream.  The != operator has the same truth table as ^^ would,
if handed boolean values (ie, 0 and 1).

Proof:

	a	b	^^	!=
	0	0	0	0
	0	1	1	1
	1	0	1	1
	1	1	0	0

Testing a and b for equality against 0 should produce two boolean values,
or, given a good compiler, a couple of test and branch statements.  My only
question is about the casting.

- John.
-- 
John F. Haugh II                  SNAIL:  HECI Exploration Co. Inc.
UUCP: ...!ihnp4!killer!jfh                11910 Greenville Ave, Suite 600
"Don't Have an Oil Well? ...              Dallas, TX. 75243
 ... Then Buy One!"                       (214) 231-0993 Ext 260

richardh@killer.UUCP (Richard Hargrove) (01/12/88)

In article <195@fxgrp.UUCP>, ljz@fxgrp.UUCP (Lloyd Zusman, Master Byte Software) writes:
> In article <2946@zeus.TEK.COM> dant@tekla.UUCP (Dan Tilque) writes:
> > ...
> >Tell me, what is the ^^ supposed to add that is not already done by ^ ?
> >The answer is nothing.  The "bitwise" xor does exactly what you would want
> >a "logical" xor to do.  In fact, the terms "bitwise" and "logical" are
> 
> I'm sorry, but I disagree.  Try running this program:

 { code and text deleted...}

> bit testing, etc.  The 'logical' versions are guaranteed to result in
> 1 or 0.

This topic came up about a year ago. I had found a need for a logical xor
operator a couple of times and added my _naive_ voice to the clamor to add 
it to C. A number of folks graciously pointed out that logical xor operator
(and its complement, logical equivalence) already exist in C: they are != 
and == used with pure "boolean" operands (canonical TRUE and FALSE, 1 and 0) 
and that any numeric operand can be converted to canonical "boolean" form 
with the != operator. Therefore 

	((x != 0) != (y != 0))

is the logical xor of x and y.

richard hargrove
...!killer!richardh
-------------------

tainter@ihlpg.ATT.COM (Tainter) (01/13/88)

In article <20153@teknowledge-vaxc.ARPA>, mkhaw@teknowledge-vaxc.ARPA (Mike Khaw) writes:
> 1^0 = 1; 0^0 = 0; 1^1 = 0 => logical xor should mean "does not equal",
> for which C has a perfectly good symbol, "!="
> Mike Khaw
No.  Logical xor should mean "not logically equal" for which != does not work.
You would still need to do an equivalent of ((A!=0) != (B!=0)).
Note: (!A ^ !B) and (!A != !B) work fine.

--j.a.tainter

karl@haddock.ISC.COM (Karl Heuer) (01/13/88)

Fact 1: "^" is a bitwise XOR operator.  When restricted to normalized boolean
operands, it is equivalent to logical XOR.

Fact 2: "!=" compares two integers.  When restricted to normalized boolean
operands, it is equivalent to logical XOR.

Fact 3: "^^" is a hypothetical logical XOR operator.  It would return 0 if its
operands are both zero or both nonzero, and 1 otherwise.  Unlike the "&&" and
"||" operators, there is no short-circuit possible; both operands are
evaluated.


Conclusion 1: In most applications (and in all applications written by those
of us who distinguish between booleans and integers), "^^" is unnecessary;
one or both of the alternatives will suffice.

Conclusion 2: If the compiler knows that both operands are normalized
booleans, then "x^y" and "x!=y" can generate the same code.  Depending on the
hardware, the best code might be the machine's equivalent of "x^y", "x!=y", or
"x ? !y : y".  Would any compiler-writers out there care to comment on
whether they've implemented this optimization?

Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint

hydrovax@nmtsun.nmt.edu (M. Warner Losh) (01/13/88)

In article <170@illusion.UUCP>, marcus@illusion.UUCP (Marcus Hall) writes:
>
> Here I tend to agree with you, but there is a slight gain in not having to
> optimize as much for the rare use of the ^^ operator.
> 

I wasn't even aware that it was in the language (^^), so how can you tell
if it's usage would be "rare" or "common".  You can't.  The ^ operator
is rare because it is almost useless (except for doing bit twiddling
in operating systems) in most applications.

From a personal experience point of view (FORTRAN mostly), I find that I
have used .XOR. (or .NEQV. for you 8x fans) on the VMS FORTRAN compiler
about a half a dozen times in about 50K lines of code.  Then again, I
usually don't think in terms of XORs.

-- 
bitnet:	lush@nmt.csnet			M. Warner Losh
csnet:	warner%hydrovax@nmtsun
uucp:	...{cmcl2, ihnp4}!lanl!unmvax!nmtsun!warner%hydrovax
	...{cmcl2, ihnp4}!lanl!unmvax!nmtsun!hydrovax
Warning:  Hydrovax is both a machine, and an account, so be careful.

bright@Data-IO.COM (Walter Bright) (01/14/88)

In article <2237@haddock.ISC.COM> karl@haddock.ima.isc.com (Karl Heuer) writes:
>Conclusion 2: If the compiler knows that both operands are normalized
>booleans, then "x^y" and "x!=y" can generate the same code.
>Would any compiler-writers out there care to comment on
>whether they've implemented this optimization?

It is not implemented in my compiler, nor in any that I've seen. In general,
flow analysis in optimizers is limited to determining things like:
	. x is/isn't always 3 at this point
	. x is/isn't always the same value as y at this point
I have seen many postings to the effect that the compiler should be able
to determine things like:
	. x is/isn't never the same value as y at this point
	. (x > 3 && x < 74) at this point
	. (some expression of arbitrary complexity) defines the possible
	  values of x at this point
Performing the flow analysis to gather the above types of information about
a variable is a research topic. I saw a paper on it once, but no actually
implemented algorithms. A compiler that implemented such analysis would
probably use an order of magnitude more memory than a conventional optimizer
and would run for an order of magnitude longer time. In other words, it's
not commercially practical currently.

Compilers do, however, make use of range information based on the variable's
type. To implement the optimization (x!=y) => (x^y), a new built-in boolean
type would have to be introduced (I am NOT proposing this). Also, a
conventional compiler could do ((a || b) != !c) => ((a || b) ^ !c), though
the number of cases where this appears is insufficient to warrant the overhead
of the test for it.

arnold@apollo.uucp (Ken Arnold) (01/14/88)

In article <170@illusion.UUCP> Marcus Hall writes:
>((a != 0) ^ (b != 0)) gives (1) ^ (1) == 0, which is false.

Not even true yet.  All (a != 0) is guaranteed to generate (if a is
not 0) is a non-zero value, *any* non-zero value, which just *usually*
is 1.  It could be 7.  So you *could* have ((a != 0) ^ (b != 0)) giving
((7) ^ (5)) or something.  There is no guarantee, therefore, that ^
will even solve the problem this way.  To be *sure*, you have to write

	((a != 0 ? 1 : 0) ^ (b != 0 ? 1 : 0))

Do you wonder why some of us have always wanted a ^^ operator?  Not
often, mind you, but when I need one, I *really* need it, 

		Ken Arnold

pardo@uw-june.cs.washington.edu (David Keppel) (01/14/88)

[Ken Arnold says: (a != b) could evaluate to 7 ]

Unless this has been changed from K&R in ANSI, (a != b) must evaluate to 0
or 1.  Check K&R Appendix A, Sections 7.6, 7.7, 7.11, 7.12.  Relational,
equality, and logical AND and OR are guaranteed by this section to return
only 0 and 1.

	;-D on  (And it isn't even my copy of K&R!)  Pardo

rsalz@bbn.com (Rich Salz) (01/14/88)

>Not even true yet.  All (a != 0) is guaranteed to generate (if a is
>not 0) is a non-zero value ...
Nope.  8/3/87 draft, page 43, lines 43-45
	Each of the operators [ < > >= ] shall yield 1 if the specified
	relation is true and 0 if it is false.
...page 44, lines 15-16
	[ == and != ] are analogous to the relational operators except
	for their lower precedence.
K&R, in the first sentence of the last paragraph on page 189 and in the
first paragraph of page 190 say almost the exact same thing.

In short, doing thinks like
	#define TRUE	(1 == 1)
	#define FALSE	(1 == 0)

	if ((a == b) == TRUE) ...

Is silly, and often a sign that the writer is confusing the interpretation
within conditionals with the result of relationals. :-)

	/r$
-- 
For comp.sources.unix stuff, mail to sources@uunet.uu.net.

gwyn@brl-smoke.ARPA (Doug Gwyn ) (01/14/88)

In article <39a83409.ae48@apollo.uucp> arnold@apollo.UUCP (Ken Arnold) writes:
>All (a != 0) is guaranteed to generate (if a is not 0) is a non-zero value,
>*any* non-zero value, which just *usually* is 1.  It could be 7.

I don't know why Ken says this.  In fact the value of a relational or
(in)equality expression is 1 if the condition is true and 0 if the
condition is false.  That's why my example ((x != 0) ^ (y != 0)) works.

djg@nscpdc.NSC.COM (Derek J. Godfrey) (01/15/88)

In article <7046@brl-smoke.ARPA>, gwyn@brl-smoke.ARPA (Doug Gwyn ) writes:
> 
> By the way, I don't think a logical XOR is important enough to bother
> adding to C.  It should be in the next conventional language you
> design, however (Ada++?).

logical XOR (or logical equivalence) has always been part of Algol 68.
So much for adding a new feature to a new language
 .. 

karl@haddock.ISC.COM (Karl Heuer) (01/15/88)

In article <2237@haddock.ISC.COM> karl@haddock.ima.isc.com (Karl Heuer) writes:
>Conclusion 2: If the compiler knows that both operands are normalized
>booleans, then "x^y" and "x!=y" can generate the same code.

I should mention that the situation I was considering was the logical xor of
two "boolean expressions", a boolean expression being one in which the last
operator is one which is guaranteed to return 0 or 1 ("==", "!", "&&", etc.).
I sometimes find myself wanting to say "if ((x0 < y0) XOR (x1 < y1))", and
there's that moment of hesitation while I decide whether XOR should be written
"^" or "!=".  If I knew that the compiler would generate the same code either
way, this would be as much a non-issue as whether to write "*p" or "p[0]".

Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.ima.com), The Walking Lint

nobody@ism780c.UUCP (Unprivileged user) (01/16/88)

In article <39a83409.ae48@apollo.uucp> arnold@apollo.UUCP (Ken Arnold) writes:
>In article <170@illusion.UUCP> Marcus Hall writes:
>>((a != 0) ^ (b != 0)) gives (1) ^ (1) == 0, which is false.
>
>Not even true yet.  All (a != 0) is guaranteed to generate (if a is
>not 0) is a non-zero value, *any* non-zero value, which just *usually*
>is 1.  It could be 7.

From K&R page 198
-----------------
  "The operators < (less than), > (greater than) , <= (less than or equal
  to), and >= (greater than or equal to) all yield 0 if the specified
  relation is false and 1 if it is true."

A simiilar statement appears on page 190 for == and !=.  There is similar
wording in the proposed standard but I loaned out my only copy so I cannot
quote it.

     Marv Rubinstein -- Interactive Systems

pardo@june.cs.washington.edu (David Keppel) (01/21/88)

( From: Ken Arnold <apollo!arnold@beaver> )
<3986@uw-june.cs.washington.edu> pardo@uw-june.UUCP (David Keppel) writes:
>
>[Ken Arnold says: (a != b) could evaluate to 7 ]
>
>Unless this has been changed from K&R in ANSI, (a != b) must evaluate to 0
>or 1.  Check K&R Appendix A, Sections 7.6, 7.7, 7.11, 7.12.  Relational,
>equality, and logical AND and OR are guaranteed by this section to return
>only 0 and 1.
>
>	;-D on  (And it isn't even my copy of K&R!)  Pardo

Pardon me.  I should have been clearer.  I have *used* compilers where this
was the case.  It is not K&R; I was picking a real-world nit, not an ansii
nit, and should have said so clearly.  My mistake.

		Ken Arnold

gwyn@brl-smoke.ARPA (Doug Gwyn ) (01/22/88)

In article <4026@june.cs.washington.edu> Ken Arnold writes:
>>[Ken Arnold says: (a != b) could evaluate to 7 ]
>I have *used* compilers where this was the case.

I sure hope you reported this bug to the vendor.