Path: utzoo!attcan!uunet!yale!wald-david
From: wald-david@CS.YALE.EDU (david wald)
Newsgroups: comp.lang.misc
Subject: Re: Clever programming tricks wanted
Message-ID: <47378@yale-celray.yale.UUCP>
Date: 12 Jan 89 18:45:02 GMT
References: <4061@hubcap.UUCP>
Sender: root@yale.UUCP
Reply-To: wald-david@CS.YALE.EDU (david wald)
Organization: Yale University Computer Science Dept, New Haven CT  06520-2158
Lines: 77

In article <4061@hubcap.UUCP> mcvax!etive.ed.ac.uk!gvw@uunet.UU.NET (MOBY) writes:
>I'm looking for "clever" programming tricks.

[modified version of (x &= x-1) trick for clearing lsb deleted]

>I would like to hear about similar tricks that people have invented/
>discovered.  In particular,...[I'm] trying to find a description of a
>mythical technique for creating doubly-linked lists using single
>pointers and XOR operations.

I've divided this up for clarity:

======================================================================
The doubly-linked list technique simply consists of storing the
exclusive-or of the back and front pointers for each node.  When
searching, you always keep a trailing pointer, which allows you to
decode the XORed pointers.  Thus, your structure might be (pardon my
C.  This requires a language with either no typing or capability for
type punning.  Or, I suppose, exclusive or for pointers, but that's a
good deal more unusual.):

struct node {
    int data;
    struct node *ptr;  /* contains XOR of back & front pointers */
    };


then, assuming "pointer" points to a node and "trailer" to the
previous node (or NULL if you're at the beginning of the list), you
can move the pointers forward in the list is done as follows:

  struct node *temp;

  temp = pointer;
  pointer = (struct node *)((long)(pointer->ptr) ^ (long)trailer);
  trailer = temp;


Similarly, to go backward:

  struct node *temp;

  temp = trailer;
  trailer = (struct node *)((long)(trailer->ptr) ^ (long)pointer);
  pointer = temp;

======================================================================
This technique is similar to one for swaping two values without using
a temporary variable.  Simply do as follows, for two variables a and
b:

	a = a ^ b;
	b = a ^ b;
	a = a ^ b;

to see that this does the right thing, let A and B be the initial
values of a and b.  This is then equivalent to:

	a = A ^ B;
	b = (A ^ B) ^ B    /* which equals A ^ (B ^ B), or A */
	a = (A ^ B) ^ A    /* which similarly equals B */

======================================================================
In fact, I suppose we could combine the two techniques, and come up
with a pointer advancement that looks like (type punning omitted):

	trailer = pointer ^ trailer ^ pointer->ptr;
	pointer = pointer ^ trailer;
	trailer = pointer ^ trailer;

Well, presumably XOR is fast.

============================================================================
David Wald                                              wald-david@yale.UUCP
waldave@yalevm.bitnet                                 wald-david@cs.yale.edu
"A monk, a clone and a ferengi decide to go bowling together..."
============================================================================