Path: utzoo!utgpu!water!watmath!clyde!rutgers!husc6!linus!philabs!pwa-b!mmintl!franka
From: franka@mmintl.UUCP (Frank Adams)
Newsgroups: comp.lang.c
Subject: Re: (really about xor)
Message-ID: <2722@mmintl.UUCP>
Date: 20 Feb 88 01:50:24 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> <7257@brl-smoke.ARPA>
Reply-To: franka@mmintl.UUCP (Frank Adams)
Organization: Multimate International, E. Hartford, CT.
Lines: 35

We are considering performing an exchange of two variables A and B via a
function f, using the steps:

	A := f(A,B)
	B := f(B,A)
	A := f(A,B)

I asserted that in order for this to work, the functions f1: x,y -> x,f(x,y)
and f2: x,y -> f(x,y),y must both be invertible.  I will now prove this.

In what follows, a and b are the initial values of A and B, respectively.
This means, in particular, that the final value of A is b, and the final
value of B is a.  Since B is last updated at the second assignment, we get

	a = f(b, f(a,b))

This demonstrates that f2 is invertible -- the inverse is x,y -> f(y,x),y.

Substituting the final value of B into the last assignment, we conclude that:

	b = f(f(a,b), a)

This shows that the inverse of f1 is x,y -> x,f(y,x).  Q.E.D.

The same result will follow if we switch the order of the arguments in any
or all of the assignments.

The invertibility of f1 and f2 is not, in general, sufficient to make this
procedure perform a swap.  However, it turns out that for Boolean values,
the only two functions with this property are exclusive or and equivalence,
and both of these do, in fact, work.
-- 

Frank Adams                           ihnp4!philabs!pwa-b!mmintl!franka
Ashton-Tate          52 Oakland Ave North         E. Hartford, CT 06108