Path: utzoo!utgpu!water!watmath!clyde!rutgers!umd5!brl-adm!brl-smoke!gwyn
From: gwyn@brl-smoke.ARPA (Doug Gwyn )
Newsgroups: comp.lang.c
Subject: Re: (really about xor)
Message-ID: <7257@brl-smoke.ARPA>
Date: 13 Feb 88 07:33:10 GMT
References: <3819@sigi.Colorado.EDU> <5080013@hpfcdc.HP.COM> <7120@brl-smoke.ARPA> <3476@ihlpf.ATT.COM> <564@cresswell.quintus.UUCP> <131@puivax.UUCP> <2701@mmintl.UUCP> <7220@brl-smoke.ARPA> <2712@mmintl.UUCP>
Reply-To: gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>)
Organization: Ballistic Research Lab (BRL), APG, MD.
Lines: 89

In article <2712@mmintl.UUCP> franka@mmintl.UUCP (Frank Adams) writes:
>In article <7220@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
>>What in the world are you two talking about?? ...
>... The pairs A^B,A and A^B,B must each contain the same information
>as the pair A,B.

I don't think this is right; it is only one of those pairs that
must contain the same information, since you can only perform
one transformation per step.  See the detailed discussion below.

>... Strictly speaking, of course, the information
>preserving operation is not A,B -> A^B, but A,B -> A^B,B.

Let me revert to Polish notation since I need a tiny amount of
operator algebra in what follows.  Lower-case will be used for
variable (bit) operands, 0 and 1 for constants, and upper-case
for Boolean operators.

Since the original setting was the old XOR swap trick, we must
have available precisely two operand variables, call them a & b.
It is clear that the interesting questions arise for sequential
processing, not parallel processing, because in the latter case
the swap could be attained directly in a single step:
	(a,b) => (b,a)
(The notation means the simultaneous replacement of the left
ordered set of information by the right set.)

For purposes of discussing a single step, it is simplest to
arbitrarily decide which of the two storage locations will
remain invariant for the step (at least one must, since
we're discussing sequential processing).  Following your
lead, let's have the second of the input variables (b) be
invariant for the step.  So the issue is, what transformations
	(a,b) => (?,b)
preserve all the information originally contained in the
(unordered) set (a,b).  (Obviously in the total picture there
will be the symmetric case where the first variable is
invariant under the transformation.)

First, let's deal with 0-ary transformations.  There is only
one (4^0) possible:
0.	(a,b) => (a,b)
which obviously preserves information but makes no progress
toward swapping the original variables.

On to unary operations.  There are four (4^1) possibilities:
1.	(a,b) => (1,b)
2.	(a,b) => (0,b)
3.	(a,b) => (a,b)
4.	(a,b) => (Na,b)
where N is the logical-negation operator.  Obviously cases 1
and 2 lose information (basically they project into lower
dimensionality) and cases 3 and 4 preserve information.
(They are their own inverse transformations, actually.)
Because in no case does any information from b play a role
in determining the new first variable's contents, obviously
no combination of unary operations will ever achieve a swap
of the original variables.

Binary operations are more interesting.  There are sixteen
(4^2) possibilities, most of which I won't enumerate, but
the following are the only four that do not lose information
(i.e. that are reversable by an additional transformation
of the same type; in fact they are again their own inverses):
5.	(a,b) => (a,b)
6.	(a,b) => (Na,b)
7.	(a,b) => (Eab,b)
8.	(a,b) => (NEab,b)
where E is the equivalence operator (NE is usually called
"exclusive or").  This corrects the misstatement that there
are only two information-preserving combinations.  However,
in cases 5 and 6 again no information from b has entered
into the first variable, so that a sequence of transformations
involving only 0-ary, unary, and binary operators excluding
E and NE cannot accomplish a swap of the original variables.

There is no point in trying n-ary operators for n > 2,
since there are only two variables available to be
operated on.  (You might think that the same variable
could be used for more than one operand, but that is no
good, because that limits you to effectively binary
operators.)

Therefore E (EQV) and NE (XOR) are useful in swapping two
variables by a sequence of bitwise Boolean operations
using no additional storage, and the task cannot be achieved
(under the bitwise Boolean sequential constraint) without
using at least one of them.  I presume this was the intended
point of the earlier discussion.