Conference noted::hackers_v1

    It swaps R1 and R0!  I learned that in CS 101...  I am not trying
    to bragg, or put down anyone.  As a side, I have known that for 90%
    of my career, and I am yet to use it!
    
    FJBlando

    Yes, in most architectures it is slower, but has the single advantage
    that it does not require an extra storage space.
    
    --  Barry

    Another method of swapping values without using an extra storage
    location:
    
    	a = a + b
    	b = a - b
    	a = a - b
    
    tom_p

I first heard of this hack used on an IBM 360.  Their XOR instruction is a
character string instruction.  Thus one could use this hack to easily exchange
the contents of two buffers.  In the days when 256Kb was a large memory, and
all of your program had to fit into memory, (along with OS and HASP), saving the
need for a 256 byte buffer might have been useful.

I have never actually seen this hack used in any code.

Another way to use this trick is to design a logic circuit without any
crossed wires that routes the signal A to A' and B to B':

                                                +-----+
--------> A ---+------------------------------->|     |
               |                                | XOR |------> B' ------------->
               |  +-----+           +---------->|     |
               +->|     |           |           +-----+
                  | XOR |-----------+
               +->|     |           |           +-----+
               |  +-----+           +---------->|     |
               |                                | XOR |------> A'------------->
--------> B ---+------------------------------->|     |
                                                +-----+

(Equally interesting and useless)

> design a logic circuit without any crossed wires that routes the 
> signal A to A' and B to B':
>(Equally interesting and useless)

	Not to a flatlander.  In a 2 dimensional universe, it's the
	only way to cross wires!
			-John A. Wasser

re: your tricks for swapping two cells without a third:


	Be careful that the two cells aren't ever the same cell.
	If so, the methods don't work !


re:  logic circuits, a harder one


	Design a circuit that uses and's, or's, and up to 2 not's, that
	takes boolean signals A, B, and C as inputs, and produces boolean
	signals -A, -B, and -C as outputs.

	In order to get credit for this one, you have to draw it like
	that previous reply drew the swap circuit.

/Eric

    re .5:
    
    And no doubt they use it extensively!
    
    	Jon

Challenge:  You are given a one-way linked list; you need to be able to
traverse it both forward and backward.  Implement this so that (a) you
need a fixed amount of extra memory, independent of the number of items
in the list; (b) the amount of time to move either forward or backward
by one step is independent of the number of items in the list; (c) there
can be any number of independent pieces of code traversing the list,
in either direction, at the same time.  (In fact, they can be running
truely in parallel.  Note that this access is for READ - even for the
one-way list, you need to do something else to allow for writes.)

Hint:  .0.
							-- Jerry

    Re .8:
    
    Unless you've left something out, a fixed array of fixed-size elements
    meets this requirement.
    
    --  Barry

    Re: .9:
    No, that won't work.. you would need to allocate a massive "fixed
    size" array; since this is a linked list, I presume that elements
    can be allocated and deallocated "on the fly".
    (I'm still working on a solution..)
    	-Rick

    re .8:
    
    Here's the Gordian Knot solution:
    
    Rewrite the program so that it uses a two-way linked list.
    
    		Jon

    Solution follows...
    
    
    Each "link" stores the offset from the previous element to the next
    element, and you keep two pointers, one to the current node and
    one to either the next or the previous.
    
    ie: Using the Ada syntax FOO'address to mean the address of FOO...
    
    		A(I-1).LINK 	:= 	A(I)'address   - A(I-2)'address;
    		A(I).LINK	:=	A(I+1)'address - A(I-1)'address;
    		A(I+1).LINK	:=	A(I+2)'address - A(I)'address;
                                     
    
    Position is stored as A(I-1)'address and A(I)'address.
    To move forward
    
    		A(I+1)'address = A(I-1)'address + A(I).LINK 
    
    To move backward
    
    		A(I-2)'address = A(I)'address - A(I-1).LINK
    
    /Bevin

The think that the solution wanted is another creative use of XOR.

Each node in the linked list only has storage for one pointer.  In
that pointer slot, store the XOR of the address of the previous element
in the list with the address of the next element of the list.

To walk forward in the list, you XOR the contents of the pointer word
of the current element with the address of the previous element to give
the pointer to the next element.  To walk backwards in the list, you XOR
the pointer word in the current element with the address of the next
element in the list to yield the address of the previous element.

Thus, the use of one pointer variable (used to keep track of where you
were) saves you one pointer member in all your list nodes.

I have never had need to use this trick, but I do think it is cute.

    .12 and .13 are equivalent but the xor won't generate integer
    overflows.
    
    
    Extra credit:  How can you do this atomically?

    Answer: 
    
    You can't on a Vax, but the IBM 370 has this nifty instruction "Compare
    Double and Swap" that reads 2 longwords, compares them against
    specified values and, if they match, writes new valued back into the
    longwords.  The instruction is atomic, even in the case of
    multiprocessors.  There's also a "compare and swap" for singly linked
    lists. 
    
    Steveg

.13 was what I had in mind; .12 will also work (I've never worked out the
details, but in principle you need not lose any information on overflow -
2's complement arithmetic is just arithmetic mod 2^n, which is a well-behaved
goup; but you have to be careful).

The fact that this seemd to give you "something for nothing" bothered me for
a while, until I thought of the trick mentioned above of reversing the pointers
as you move along.  This trick is basic to good garbage-collection algorithms.
The neat thing about the XOR hack is that it doesn't change the list.

A nice way to look at what is going on here is to imagine that rather than
holding on to a "current NODE" pointer, you are holding on to a "current
EDGE" pointer.
							-- Jerry