/*

  Gray code in Picat.

  From Rosetta Code:
  http://rosettacode.org/wiki/Gray_code
  """
  Gray code

  Gray code is a form of binary encoding where transitions between consecutive numbers 
  differ by only one bit. This is a useful encoding for reducing hardware data hazards 
  with values that change rapidly and/or connect to slower hardware as inputs. 
  It is also useful for generating inputs for Karnaugh maps in order from left to 
  right or top to bottom.

  Create functions to encode a number to and decode a number from Gray code. Display the 
  normal binary representations, Gray code representations, and decoded Gray code values 
  for all 5-bit binary numbers (0-31 inclusive, leading 0's not necessary).

  There are many possible Gray codes. The following encodes what is called "binary 
  reflected Gray code."

  Encoding (MSB is bit 0, b is binary, g is Gray code):

    if b[i-1] = 1
       g[i] = not b[i]
    else
       g[i] = b[i]

  Or:

    g = b xor (b logically right shifted 1 time)

  Decoding (MSB is bit 0, b is binary, g is Gray code):

    b[0] = g[0]

  for other bits:
    b[i] = g[i] xor b[i-1]
  """

  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.
import cp.


main => go.

go => 
   foreach(I in 0..2**5-1)
      G = gray_encode1(I),
      E = gray_decode1(G),
      println([I,I.to_binary_string(), G, G.to_binary_string(),E.to_binary_string(), E])
   end,
   nl,
   N2=2**300,
   G2=gray_encode1(N2),
   E2=gray_decode1(G2),
   println([N2,G2,E2,cond(N2==E2,same,not_same)]),
   nl.


gray_encode1(N) = N ^ (N >> 1).
gray_decode1(N) = P =>
    P = N,
    N := N >> 1,
    while (N != 0)
      P := P ^ N,
      N := N >> 1
    end.