Gray code (idea)

Encoding a binary value to a Gray code value is accomplished by the following C function:

unsigned long binary_to_gray(unsigned long n)
{
  return (n ^ (n >> 1));
}

Decoding is slightly more tricky, the following function will do it:

unsigned long gray_to_binary(unsigned long n)
{
  unsigned long sh;
  unsigned long nn;
  sh = 1;
  nn = (n >> sh);
  while (nn > 0) {
    n ^= nn;
    sh <<= 1;
    nn = (n >> sh);
  }
  return (n);
}

It is very interesting to note that binary_to_gray is the same transformation as changing a binary string from fully coherent to differentially coherent (change on 1), and gray_to_binary is the same transformation as changing from differentially-coherent (change on 1) to fully-coherent.

So, to change from binary to Gray: write out the binary string one one line of a page. Copy the leftmost bit to the line below (assuming the most significant bit is on the left, which it usually is). Repeat for all following bits on the top line: if it's the same as the previous bit, add a '0' to the Gray code; otherwise, add a '1' to the Gray code. (A proof by induction can show that two successive numbers encoded in this manner will have precisely one bit changed after the Gray code transformation.)

To change from Gray to binary: write out the Gray string. Copy the leftmost bit to the line below. Repeat for all following bits: if it's a '0', copy the previous bit of the binary string; if it's a '1', write the inverse of the previous bit.

The grey code can be padded on the left with 0s just like binary values, or 0s on the left can be ignored just like with binary.

Another interesting property of Gray codes is that (binary_to_gray(x ^ y) == (binary_to_gray(x) ^ binary_to_gray(y)) and (gray_to_binary(x ^ y) == (gray_to_binary(x) ^ gray_to_binary(y)).