ANEW  --GRAYCODE--                            \  Wil Baden  2003-02-19

\  *******************************************************************
\  *                                                                 *
\  *  Wil Baden  2003-02-19                                          *
\  *                                                                 *
\  *          GRAYCODE                                               *
\  *                                                                 *
\  *  A Graycode is a representation of numbers such that the codes  *
\  *  for a number and its successor differ by one bit.              *
\  *                                                                 *
\  *******************************************************************

There are many ways to define a Graycode, but the following is the 
easiest and must common. 

	: Num>Gray                  ( n_1 -- n_2 )
	    dup 1 RSHIFT XOR ;
	   
The inverse is:

    : Gray>Num                  ( n_1 -- n_2 )
        dup 1 RSHIFT XOR
        dup 2 RSHIFT XOR
        dup 4 RSHIFT XOR
        dup 8 RSHIFT XOR
        dup 16 RSHIFT XOR
        ( etcetera )
        ;

Here are the usual Graycodes for numbers 0 through 15.

    0000     0110     1100     1010     
    0001     0111     1101     1011
    0011     0101     1111     1001
    0010     0100     1110     1000

Note that normal Graycodes reiterate for repeated sequences within a 
power of 2, just like the numbers they represent. 

    0
    1
    
    00
    01
    11
    10

    000
    001
    011
    010
    110
    111
    101
    100

If you take the same number of values from the beginning and end of a 
sequence of a power of 2, the cycle will also repeat. Here three 
numbers have been taken from the beginning and end of a normal 
sequence of 16.  This is one way that decimal integers have been 
shown in past computers. The values are Graycodes for 3 through 12, 
and are used for integers 0 through 9.  This is "excess 3 Graycode".

    0010  0110  0111  0101  0100  1100  1101  1111  1110  1010

Graycode can also be used to solve Tower of Hanoy and similar puzzles. 

Tower of Hanoy is solved by moving the disk corresponding to the 
changed bit one way in odd moves, and then the other way in even 
moves. 

\\   //   \\   //   \\   //   \\   //   \\   //   \\   //   \\   //   \\