[Gllug] XOR

[Pete Ryland]

On Thu, Apr 15, 2004 at 05:09:53PM +0100, Ashley Evans wrote:
> Afternoon,
> 
> Having spent the day working on various bits and bobs I came across some 
> info on wikipedia about XOR.
> 
> The two notable things I've discovered today are:
> 
> One can swap the contents two vars without using a tmp var.

Indeed, quite useful.  From an information point of view, replacing A with
(A xor B) loses no information.  This added to the fact that A xor B xor B
yields A gives us this nice algorithm.

> One can implement a doubely linked-list using .

Hmm.. I'll have to look into this one - sounds dodgy though, playing with
pointers like such.

> Then we have the good old xor "encryption". Which is fun to play with.

MS used to use this to set who a product is registered to.  I only know this
because I once noticed that the install diskette to an early version of VB
contained a recently-modified file whose contents were basically my name
XORed with 01 23 45 67 89 ab cd ef... which I recognised instantly.
Obscurity has come a long way since. ;-)

> As a newbie programmer I think xor is about a great as functions come.
> 
> So, what else can this bit of binary operator magic be used for?

In hardware, it's used to perform addition.

To add two one-bit numbers:

    X   Y
   / \ / \
  |   /   |
  |  / \  |
  AND   XOR
     \ /
     C R

where CR is the two bit result consisting of the carry, C, and the result, R.
These can be cascaded to add many-bit numbers.

It's also used in parity and error-recovery algorithms like ECC and RAID4/5,
which do a bit-wise XOR across the array and store the parity, meaning that
if one of the devices fails, its value can be calculated from the others by
simply XORing them.  Once again, this relies on the property that:

A xor B xor A = B

as well as the properties of commutation (A xor B = B xor A), etc.

Pete
-- 
Gllug mailing list  -  Gllug at gllug.org.uk
http://lists.gllug.org.uk/mailman/listinfo/gllug