Gray code

From Rosetta Code
Revision as of 11:33, 9 August 2015 by rosettacode>Brnikat (Initial implementation)
Task
Gray code
You are encouraged to solve this task according to the task description, using any language you may know.

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]
Reference

Ada

Demonstrates the use of shift operators. Code scalable to 6, 7 or 8 bits. Values are implemented with 8 bits according to representation clause of Unsigned_8 (check package Interfaces). <lang Ada>with Ada.Text_IO, Interfaces; use Ada.Text_IO, Interfaces;

procedure Gray is

  Bits : constant := 5; -- Change only this line for 6 or 7-bit encodings
  subtype Values is Unsigned_8 range 0 .. 2 ** Bits - 1;
  package Values_Io is new Ada.Text_IO.Modular_IO (Values);
  function Encode (Binary : Values) return Values is
  begin
     return Binary xor Shift_Right (Binary, 1);
  end Encode;
  pragma Inline (Encode);
  function Decode (Gray : Values) return Values is
     Binary, Bit : Values;
     Mask        : Values := 2 ** (Bits - 1);
  begin
     Bit    := Gray and Mask;
     Binary := Bit;
     for I in 2 .. Bits loop
        Bit    := Shift_Right (Bit, 1);
        Mask   := Shift_Right (Mask, 1);
        Bit    := (Gray and Mask) xor Bit;
        Binary := Binary + Bit;
     end loop;
     return Binary;
  end Decode;
  pragma Inline (Decode);
  HT : constant Character := Character'Val (9);
  J  : Values;

begin

  Put_Line ("Num" & HT & "Binary" & HT & HT & "Gray" & HT & HT & "decoded");
  for I in Values'Range loop
     J := Encode (I);
     Values_Io.Put (I, 4);
     Put (": " & HT);
     Values_Io.Put (I, Bits + 2, 2);
     Put (" =>" & HT);
     Values_Io.Put (J, Bits + 2, 2);
     Put (" => " & HT);
     Values_Io.Put (Decode (J), 4);
     New_Line;
  end loop;

end Gray;</lang> Check compactness of assembly code generated by GNAT :http://pastebin.com/qtNjeQk9

Output:
Num	Binary		Gray		decoded
   0: 	   2#0# =>	   2#0# => 	   0
   1: 	   2#1# =>	   2#1# => 	   1
   2: 	  2#10# =>	  2#11# => 	   2
   3: 	  2#11# =>	  2#10# => 	   3
   4: 	 2#100# =>	 2#110# => 	   4
   5: 	 2#101# =>	 2#111# => 	   5
   6: 	 2#110# =>	 2#101# => 	   6
   7: 	 2#111# =>	 2#100# => 	   7
   8: 	2#1000# =>	2#1100# => 	   8
   9: 	2#1001# =>	2#1101# => 	   9
  10: 	2#1010# =>	2#1111# => 	  10
  11: 	2#1011# =>	2#1110# => 	  11
  12: 	2#1100# =>	2#1010# => 	  12
  13: 	2#1101# =>	2#1011# => 	  13
  14: 	2#1110# =>	2#1001# => 	  14
  15: 	2#1111# =>	2#1000# => 	  15
  16: 	2#10000# =>	2#11000# => 	  16
  17: 	2#10001# =>	2#11001# => 	  17
  18: 	2#10010# =>	2#11011# => 	  18
  19: 	2#10011# =>	2#11010# => 	  19
  20: 	2#10100# =>	2#11110# => 	  20
  21: 	2#10101# =>	2#11111# => 	  21
  22: 	2#10110# =>	2#11101# => 	  22
  23: 	2#10111# =>	2#11100# => 	  23
  24: 	2#11000# =>	2#10100# => 	  24
  25: 	2#11001# =>	2#10101# => 	  25
  26: 	2#11010# =>	2#10111# => 	  26
  27: 	2#11011# =>	2#10110# => 	  27
  28: 	2#11100# =>	2#10010# => 	  28
  29: 	2#11101# =>	2#10011# => 	  29
  30: 	2#11110# =>	2#10001# => 	  30
  31: 	2#11111# =>	2#10000# => 	  31

Aime

Translation of: C

<lang aime>integer gray_encode(integer n) {

   return n ^ (n >> 1);

}

integer gray_decode(integer n) {

   integer p;
   p = n;
   while (n >>= 1) {
       p ^= n;
   }
   return p;

}</lang> Demonstration code: <lang aime>integer main(void) {

   integer i, g, b;
   i = 0;
   while (i < 32) {
       g = gray_encode(i);
       b = gray_decode(g);
       o_winteger(2, i);
       o_text(": ");
       o_fxinteger(5, 2, i);
       o_text(" => ");
       o_fxinteger(5, 2, g);
       o_text(" => ");
       o_fxinteger(5, 2, b);
       o_text(": ");
       o_winteger(2, b);
       o_byte('\n');
       i += 1;
   }
   return 0;

}</lang>

Output:
 0: 00000 => 00000 => 00000:  0
 1: 00001 => 00001 => 00001:  1
 2: 00010 => 00011 => 00010:  2
 3: 00011 => 00010 => 00011:  3
 4: 00100 => 00110 => 00100:  4
 5: 00101 => 00111 => 00101:  5
 6: 00110 => 00101 => 00110:  6
 7: 00111 => 00100 => 00111:  7
 8: 01000 => 01100 => 01000:  8
 9: 01001 => 01101 => 01001:  9
10: 01010 => 01111 => 01010: 10
11: 01011 => 01110 => 01011: 11
12: 01100 => 01010 => 01100: 12
13: 01101 => 01011 => 01101: 13
14: 01110 => 01001 => 01110: 14
15: 01111 => 01000 => 01111: 15
16: 10000 => 11000 => 10000: 16
17: 10001 => 11001 => 10001: 17
18: 10010 => 11011 => 10010: 18
19: 10011 => 11010 => 10011: 19
20: 10100 => 11110 => 10100: 20
21: 10101 => 11111 => 10101: 21
22: 10110 => 11101 => 10110: 22
23: 10111 => 11100 => 10111: 23
24: 11000 => 10100 => 11000: 24
25: 11001 => 10101 => 11001: 25
26: 11010 => 10111 => 11010: 26
27: 11011 => 10110 => 11011: 27
28: 11100 => 10010 => 11100: 28
29: 11101 => 10011 => 11101: 29
30: 11110 => 10001 => 11110: 30
31: 11111 => 10000 => 11111: 31

ALGOL 68

In Algol 68 the BITS mode is specifically designed for manipulating machine words as a row of bits so it is natural to treat Gray encoded integers as values of MODE BITS. The standard operator BIN (INT i) : BITS converts an INT value to a BITS value. The ABS (BITS b) : INT operator performs the reverse conversion, though it has not been needed for this task. It is also natural in the language for simple operations on values to be implemented as operators, rather than as functions, as in the program below. <lang algol68>BEGIN

  OP GRAY = (BITS b) BITS : b XOR (b SHR 1);	CO Convert to Gray code CO
  OP YARG = (BITS g) BITS :			CO Convert from Gray code CO
  BEGIN
     BITS b := g, mask := g SHR 1;
     WHILE mask /= 16r0 DO b := b XOR mask; mask := mask SHR 1 OD;
     b
  END;
  FOR i FROM 0 TO 31
  DO
     printf (($zd,": ", 2(2r5d, " >= "), 2r5dl$,i, BIN i, GRAY BIN i, YARG GRAY BIN i))
  OD

END</lang>

Output:
 0: 00000 >= 00000 >= 00000
 1: 00001 >= 00001 >= 00001
 2: 00010 >= 00011 >= 00010
 3: 00011 >= 00010 >= 00011
 4: 00100 >= 00110 >= 00100
 5: 00101 >= 00111 >= 00101
 6: 00110 >= 00101 >= 00110
 7: 00111 >= 00100 >= 00111
 8: 01000 >= 01100 >= 01000
 9: 01001 >= 01101 >= 01001
10: 01010 >= 01111 >= 01010
11: 01011 >= 01110 >= 01011
12: 01100 >= 01010 >= 01100
13: 01101 >= 01011 >= 01101
14: 01110 >= 01001 >= 01110
15: 01111 >= 01000 >= 01111
16: 10000 >= 11000 >= 10000
17: 10001 >= 11001 >= 10001
18: 10010 >= 11011 >= 10010
19: 10011 >= 11010 >= 10011
20: 10100 >= 11110 >= 10100
21: 10101 >= 11111 >= 10101
22: 10110 >= 11101 >= 10110
23: 10111 >= 11100 >= 10111
24: 11000 >= 10100 >= 11000
25: 11001 >= 10101 >= 11001
26: 11010 >= 10111 >= 11010
27: 11011 >= 10110 >= 11011
28: 11100 >= 10010 >= 11100
29: 11101 >= 10011 >= 11101
30: 11110 >= 10001 >= 11110
31: 11111 >= 10000 >= 11111

APL

Generate the complete N-bit Gray sequence as a matrix:run <lang apl>N←5 ({(0,⍵)⍪1,⊖⍵}⍣N)(1 0⍴⍬)</lang>

Output:
0 0 0 0 0
0 0 0 0 1
0 0 0 1 1
0 0 0 1 0
0 0 1 1 0
0 0 1 1 1
0 0 1 0 1
0 0 1 0 0
0 1 1 0 0
0 1 1 0 1
0 1 1 1 1
0 1 1 1 0
0 1 0 1 0
0 1 0 1 1
0 1 0 0 1
0 1 0 0 0
1 1 0 0 0
1 1 0 0 1
1 1 0 1 1
1 1 0 1 0
1 1 1 1 0
1 1 1 1 1
1 1 1 0 1
1 1 1 0 0
1 0 1 0 0
1 0 1 0 1
1 0 1 1 1
1 0 1 1 0
1 0 0 1 0
1 0 0 1 1
1 0 0 0 1
1 0 0 0 0

Encode and decode an individual integer:run <lang apl>N←5 grayEncode←{a≠N↑(0,a←(N⍴2)⊤⍵)} grayDecode←{2⊥≠⌿N N↑N(2×N)⍴⍵,0,N⍴0}

grayEncode 19</lang>

Output:
1 1 0 1 0

AutoHotkey

<lang AHK>gray_encode(n){ return n ^ (n >> 1) }

gray_decode(n){ p := n while (n >>= 1) p ^= n return p }

BinString(n){ Loop 5 If ( n & ( 1 << (A_Index-1) ) ) o := "1" . o else o := "0" . o return o }

Loop 32 n:=A_Index-1, out .= n " : " BinString(n) " => " BinString(e:=gray_encode(n)) . " => " BinString(gray_decode(e)) " => " BinString(n) "`n" MsgBox % clipboard := out</lang>

Output:
0 : 00000 => 00000 => 00000 => 00000
1 : 00001 => 00001 => 00001 => 00001
2 : 00010 => 00011 => 00010 => 00010
3 : 00011 => 00010 => 00011 => 00011
4 : 00100 => 00110 => 00100 => 00100
5 : 00101 => 00111 => 00101 => 00101
6 : 00110 => 00101 => 00110 => 00110
7 : 00111 => 00100 => 00111 => 00111
8 : 01000 => 01100 => 01000 => 01000
9 : 01001 => 01101 => 01001 => 01001
10 : 01010 => 01111 => 01010 => 01010
11 : 01011 => 01110 => 01011 => 01011
12 : 01100 => 01010 => 01100 => 01100
13 : 01101 => 01011 => 01101 => 01101
14 : 01110 => 01001 => 01110 => 01110
15 : 01111 => 01000 => 01111 => 01111
16 : 10000 => 11000 => 10000 => 10000
17 : 10001 => 11001 => 10001 => 10001
18 : 10010 => 11011 => 10010 => 10010
19 : 10011 => 11010 => 10011 => 10011
20 : 10100 => 11110 => 10100 => 10100
21 : 10101 => 11111 => 10101 => 10101
22 : 10110 => 11101 => 10110 => 10110
23 : 10111 => 11100 => 10111 => 10111
24 : 11000 => 10100 => 11000 => 11000
25 : 11001 => 10101 => 11001 => 11001
26 : 11010 => 10111 => 11010 => 11010
27 : 11011 => 10110 => 11011 => 11011
28 : 11100 => 10010 => 11100 => 11100
29 : 11101 => 10011 => 11101 => 11101
30 : 11110 => 10001 => 11110 => 11110
31 : 11111 => 10000 => 11111 => 11111

BBC BASIC

<lang bbcbasic> INSTALL @lib$+"STRINGLIB"

     PRINT "   Decimal    Binary      Gray   Decoded"
     FOR number% = 0 TO 31
       gray% = FNgrayencode(number%)
       PRINT number% "     " FN_tobase(number%, 2, 5) ;
       PRINT "     " FN_tobase(gray%, 2, 5) FNgraydecode(gray%)
     NEXT
     END
     
     DEF FNgrayencode(B%) = B% EOR (B% >>> 1)
     
     DEF FNgraydecode(G%) : LOCAL B%
     REPEAT B% EOR= G% : G% = G% >>> 1 : UNTIL G% = 0
     = B%</lang>

bc

This language has no bitwise logic. We must repeat, with each bit, the exclusive-or calculation. This solution uses h % 2 and i % 2 to grab the low bits, and repeats if (h % 2 != i % 2) to check if the exclusive-or is one. Our encoding and decoding functions are identical except that h always comes from the decoded integer.

<lang bc>scale = 0 /* to use integer division */

/* encode Gray code */ define e(i) { auto h, r

if (i <= 0) return 0 h = i / 2 r = e(h) * 2 /* recurse */ if (h % 2 != i % 2) r += 1 /* xor low bits of h, i */ return r }

/* decode Gray code */ define d(i) { auto h, r

if (i <= 0) return 0 h = d(i / 2) /* recurse */ r = h * 2 if (h % 2 != i % 2) r += 1 /* xor low bits of h, i */ return r }


/* print i as 5 binary digits */ define p(i) { auto d, d[]

for (d = 0; d <= 4; d++) { d[d] = i % 2 i /= 2 } for (d = 4; d >= 0; d--) { if(d[d] == 0) "0" if(d[d] == 1) "1" } }

for (i = 0; i < 32; i++) { /* original */ t = p(i); " => " /* encoded */ e = e(i); t = p(e); " => " /* decoded */ d = d(e); t = p(d); " " } quit</lang>

Output:
00000 => 00000 => 00000
00001 => 00001 => 00001
00010 => 00011 => 00010
00011 => 00010 => 00011
00100 => 00110 => 00100
00101 => 00111 => 00101
00110 => 00101 => 00110
00111 => 00100 => 00111
01000 => 01100 => 01000
01001 => 01101 => 01001
01010 => 01111 => 01010
01011 => 01110 => 01011
01100 => 01010 => 01100
01101 => 01011 => 01101
01110 => 01001 => 01110
01111 => 01000 => 01111
10000 => 11000 => 10000
10001 => 11001 => 10001
10010 => 11011 => 10010
10011 => 11010 => 10011
10100 => 11110 => 10100
10101 => 11111 => 10101
10110 => 11101 => 10110
10111 => 11100 => 10111
11000 => 10100 => 11000
11001 => 10101 => 11001
11010 => 10111 => 11010
11011 => 10110 => 11011
11100 => 10010 => 11100
11101 => 10011 => 11101
11110 => 10001 => 11110
11111 => 10000 => 11111

C

Translation of: Tcl

<lang c>int gray_encode(int n) {

   return n ^ (n >> 1);

}

int gray_decode(int n) {

   int p = n;
   while (n >>= 1) p ^= n;
   return p;

}</lang> Demonstration code: <lang c>#include <stdio.h>

/* Simple bool formatter, only good on range 0..31 */ void fmtbool(int n, char *buf) {

   char *b = buf + 5;
   *b=0;
   do {

*--b = '0' + (n & 1); n >>= 1;

   } while (b != buf);

}

int main(int argc, char **argv) {

   int i,g,b;
   char bi[6],bg[6],bb[6];
   for (i=0 ; i<32 ; i++) {

g = gray_encode(i); b = gray_decode(g); fmtbool(i,bi); fmtbool(g,bg); fmtbool(b,bb); printf("%2d : %5s => %5s => %5s : %2d\n", i, bi, bg, bb, b);

   }
   return 0;

}</lang>

Output:
 0 : 00000 => 00000 => 00000 :  0
 1 : 00001 => 00001 => 00001 :  1
 2 : 00010 => 00011 => 00010 :  2
 3 : 00011 => 00010 => 00011 :  3
 4 : 00100 => 00110 => 00100 :  4
 5 : 00101 => 00111 => 00101 :  5
 6 : 00110 => 00101 => 00110 :  6
 7 : 00111 => 00100 => 00111 :  7
 8 : 01000 => 01100 => 01000 :  8
 9 : 01001 => 01101 => 01001 :  9
10 : 01010 => 01111 => 01010 : 10
11 : 01011 => 01110 => 01011 : 11
12 : 01100 => 01010 => 01100 : 12
13 : 01101 => 01011 => 01101 : 13
14 : 01110 => 01001 => 01110 : 14
15 : 01111 => 01000 => 01111 : 15
16 : 10000 => 11000 => 10000 : 16
17 : 10001 => 11001 => 10001 : 17
18 : 10010 => 11011 => 10010 : 18
19 : 10011 => 11010 => 10011 : 19
20 : 10100 => 11110 => 10100 : 20
21 : 10101 => 11111 => 10101 : 21
22 : 10110 => 11101 => 10110 : 22
23 : 10111 => 11100 => 10111 : 23
24 : 11000 => 10100 => 11000 : 24
25 : 11001 => 10101 => 11001 : 25
26 : 11010 => 10111 => 11010 : 26
27 : 11011 => 10110 => 11011 : 27
28 : 11100 => 10010 => 11100 : 28
29 : 11101 => 10011 => 11101 : 29
30 : 11110 => 10001 => 11110 : 30
31 : 11111 => 10000 => 11111 : 31

C++

<lang cpp>

  1. include <bitset>
  2. include <iostream>
  3. include <string>
  4. include <assert.h>

uint32_t gray_encode(uint32_t b) {

   return b ^ (b >> 1);

}

uint32_t gray_decode(uint32_t g) {

   for (uint32_t bit = 1U << 31; bit > 1; bit >>= 1)
   {
       if (g & bit) g ^= bit >> 1;
   }
   return g;

}

std::string to_binary(int value) // utility function {

   const std::bitset<32> bs(value);
   const std::string str(bs.to_string());
   const size_t pos(str.find('1'));
   return pos == std::string::npos ? "0" : str.substr(pos);

}

int main() {

   std::cout << "Number\tBinary\tGray\tDecoded\n";
   for (uint32_t n = 0; n < 32; ++n)
   {
       uint32_t g = gray_encode(n);
       assert(gray_decode(g) == n);
       std::cout << n << "\t" << to_binary(n) << "\t" << to_binary(g) << "\t" << g << "\n";
   }

}</lang>

Output:
Number	Binary	Gray	Decoded
0	0	0	0
1	1	1	1
2	10	11	3
3	11	10	2
4	100	110	6
5	101	111	7
6	110	101	5
7	111	100	4
8	1000	1100	12
9	1001	1101	13
10	1010	1111	15
11	1011	1110	14
12	1100	1010	10
13	1101	1011	11
14	1110	1001	9
15	1111	1000	8
16	10000	11000	24
17	10001	11001	25
18	10010	11011	27
19	10011	11010	26
20	10100	11110	30
21	10101	11111	31
22	10110	11101	29
23	10111	11100	28
24	11000	10100	20
25	11001	10101	21
26	11010	10111	23
27	11011	10110	22
28	11100	10010	18
29	11101	10011	19
30	11110	10001	17
31	11111	10000	16

C#

<lang c sharp>using System;

public class Gray {

   public static ulong grayEncode(ulong n) {
       return n^(n>>1);
   }
   public static ulong grayDecode(ulong n) {
       ulong i=1<<8*64-2; //long is 64-bit
       ulong p, b=p=n&i;
       while((i>>=1)>0)
           b|=p=n&i^p>>1;
       return b;
   }
   public static void Main(string[] args) {
       Console.WriteLine("Number\tBinary\tGray\tDecoded");
       for(ulong i=0;i<32;i++) {
           Console.WriteLine(string.Format("{0}\t{1}\t{2}\t{3}", i, Convert.ToString((long)i, 2), Convert.ToString((long)grayEncode(i), 2), grayDecode(grayEncode(i))));
       }
   }

}</lang>

Output:
Number	Binary	Gray	Decoded
0	0	0	0
1	1	1	1
2	10	11	2
3	11	10	3
4	100	110	4
5	101	111	5
6	110	101	6
7	111	100	7
8	1000	1100	8
9	1001	1101	9
10	1010	1111	10
11	1011	1110	11
12	1100	1010	12
13	1101	1011	13
14	1110	1001	14
15	1111	1000	15
16	10000	11000	16
17	10001	11001	17
18	10010	11011	18
19	10011	11010	19
20	10100	11110	20
21	10101	11111	21
22	10110	11101	22
23	10111	11100	23
24	11000	10100	24
25	11001	10101	25
26	11010	10111	26
27	11011	10110	27
28	11100	10010	28
29	11101	10011	29
30	11110	10001	30
31	11111	10000	31

CoffeeScript

<lang coffeescript> gray_encode = (n) ->

 n ^ (n >> 1)
 

gray_decode = (g) ->

 n = g
 n ^= g while g >>= 1
 n
 

for i in [0..32]

 console.log gray_decode gray_encode(i)

</lang>

Common Lisp

<lang lisp>(defun gray-encode (n)

 (logxor n (ash n -1)))

(defun gray-decode (n)

 (do ((p n (logxor p n)))
   ((zerop n) p)
   (setf n (ash n -1))))

(loop for i to 31 do

     (let* ((g (gray-encode i)) (b (gray-decode g)))

(format t "~2d:~6b =>~6b =>~6b :~2d~%" i i g b b)))</lang>

Component Pascal

BlackBox Component Builder <lang oberon2> MODULE GrayCodes; IMPORT StdLog,SYSTEM;

PROCEDURE Encode*(i: INTEGER; OUT x: INTEGER); VAR j: INTEGER; s,r: SET; BEGIN s := BITS(i);j := MAX(SET); WHILE (j >= 0) & ~(j IN s) DO DEC(j) END; r := {};IF j >= 0 THEN INCL(r,j) END; WHILE j > 0 DO IF ((j IN s) & ~(j - 1 IN s)) OR (~(j IN s) & (j - 1 IN s)) THEN INCL(r,j-1) END; DEC(j) END; x := SYSTEM.VAL(INTEGER,r) END Encode;

PROCEDURE Decode*(x: INTEGER; OUT i: INTEGER); VAR j: INTEGER; s,r: SET; BEGIN s := BITS(x);r:={};j := MAX(SET); WHILE (j >= 0) & ~(j IN s) DO DEC(j) END; IF j >= 0 THEN INCL(r,j) END; WHILE j > 0 DO IF ((j IN r) & ~(j - 1 IN s)) OR (~(j IN r) & (j - 1 IN s)) THEN INCL(r,j-1) END; DEC(j) END; i := SYSTEM.VAL(INTEGER,r); END Decode;


PROCEDURE Do*; VAR grayCode,binCode: INTEGER; i: INTEGER; BEGIN StdLog.String(" i ");StdLog.String(" bin code ");StdLog.String(" gray code ");StdLog.Ln; StdLog.String("---");StdLog.String(" ----------------");StdLog.String(" ---------------");StdLog.Ln; FOR i := 0 TO 32 DO; Encode(i,grayCode);Decode(grayCode,binCode); StdLog.IntForm(i,10,3,' ',FALSE); StdLog.IntForm(binCode,2,16,' ',TRUE); StdLog.IntForm(grayCode,2,16,' ',TRUE); StdLog.Ln; END END Do;

END GrayCodes. </lang> Execute: ^QGrayCodes.Do

Output:
 i      bin code       gray code    
--- ---------------- ---------------
  0             0%2             0%2
  1             1%2             1%2
  2            10%2            11%2
  3            11%2            10%2
  4           100%2           110%2
  5           101%2           111%2
  6           110%2           101%2
  7           111%2           100%2
  8          1000%2          1100%2
  9          1001%2          1101%2
 10          1010%2          1111%2
 11          1011%2          1110%2
 12          1100%2          1010%2
 13          1101%2          1011%2
 14          1110%2          1001%2
 15          1111%2          1000%2
 16         10000%2         11000%2
 17         10001%2         11001%2
 18         10010%2         11011%2
 19         10011%2         11010%2
 20         10100%2         11110%2
 21         10101%2         11111%2
 22         10110%2         11101%2
 23         10111%2         11100%2
 24         11000%2         10100%2
 25         11001%2         10101%2
 26         11010%2         10111%2
 27         11011%2         10110%2
 28         11100%2         10010%2
 29         11101%2         10011%2
 30         11110%2         10001%2
 31         11111%2         10000%2
 32        100000%2        110000%2

D

<lang d>uint grayEncode(in uint n) pure nothrow @nogc {

   return n ^ (n >> 1);

}

uint grayDecode(uint n) pure nothrow @nogc {

   auto p = n;
   while (n >>= 1)
       p ^= n;
   return p;

}

void main() {

   import std.stdio;
   " N     N2      enc     dec2 dec".writeln;
   foreach (immutable n; 0 .. 32) {
       immutable g = n.grayEncode;
       immutable d = g.grayDecode;
       writefln("%2d: %5b => %5b => %5b: %2d", n, n, g, d, d);
       assert(d == n);
   }

}</lang>

Output:
 N     N2      enc     dec2 dec
 0:     0 =>     0 =>     0:  0
 1:     1 =>     1 =>     1:  1
 2:    10 =>    11 =>    10:  2
 3:    11 =>    10 =>    11:  3
 4:   100 =>   110 =>   100:  4
 5:   101 =>   111 =>   101:  5
 6:   110 =>   101 =>   110:  6
 7:   111 =>   100 =>   111:  7
 8:  1000 =>  1100 =>  1000:  8
 9:  1001 =>  1101 =>  1001:  9
10:  1010 =>  1111 =>  1010: 10
11:  1011 =>  1110 =>  1011: 11
12:  1100 =>  1010 =>  1100: 12
13:  1101 =>  1011 =>  1101: 13
14:  1110 =>  1001 =>  1110: 14
15:  1111 =>  1000 =>  1111: 15
16: 10000 => 11000 => 10000: 16
17: 10001 => 11001 => 10001: 17
18: 10010 => 11011 => 10010: 18
19: 10011 => 11010 => 10011: 19
20: 10100 => 11110 => 10100: 20
21: 10101 => 11111 => 10101: 21
22: 10110 => 11101 => 10110: 22
23: 10111 => 11100 => 10111: 23
24: 11000 => 10100 => 11000: 24
25: 11001 => 10101 => 11001: 25
26: 11010 => 10111 => 11010: 26
27: 11011 => 10110 => 11011: 27
28: 11100 => 10010 => 11100: 28
29: 11101 => 10011 => 11101: 29
30: 11110 => 10001 => 11110: 30
31: 11111 => 10000 => 11111: 31

Compile-Time version

This version uses a compile time generated translation table, if maximum bit width of the numbers is a constant. The encoding table is generated recursively, then the decode table is calculated and appended. Same output. <lang d>import std.stdio, std.algorithm;

T[] gray(int N : 1, T)() pure nothrow {

   return [T(0), 1];

}

/// Recursively generate gray encoding mapping table. T[] gray(int N, T)() pure nothrow if (N <= T.sizeof * 8) {

   enum T M = T(2) ^^ (N - 1);
   T[] g = gray!(N - 1, T)();
   foreach (immutable i; 0 .. M)
       g ~= M + g[M - i - 1];
   return g;

}

T[][] grayDict(int N, T)() pure nothrow {

   T[][] dict = [gray!(N, T)(), [0]];
   // Append inversed gray encoding mapping.
   foreach (immutable i; 1 .. dict[0].length)
       dict[1] ~= countUntil(dict[0], i);
   return dict;

}

enum M { Encode = 0, Decode = 1 }

T gray(int N, T)(in T n, in int mode=M.Encode) pure nothrow {

   // Generated at compile time.
   enum dict = grayDict!(N, T)();
   return dict[mode][n];

}

void main() {

   foreach (immutable i; 0 .. 32) {
       immutable encoded = gray!(5)(i, M.Encode);
       immutable decoded = gray!(5)(encoded, M.Decode);
       writefln("%2d: %5b => %5b : %2d", i, i, encoded, decoded);
   }

}</lang>

Short Functional-Style Generator

<lang d>import std.stdio, std.algorithm, std.range;

string[] g(in uint n) pure nothrow {

   return n ? g(n - 1).map!q{'0' ~ a}.array ~
              g(n - 1).retro.map!q{'1' ~ a}.array
            : [""];

}

void main() {

   4.g.writeln;

}</lang>

Output:
["0000", "0001", "0011", "0010", "0110", "0111", "0101", "0100", "1100", "1101", "1111", "1110", "1010", "1011", "1001", "1000"]

Delphi

Translation of: DWScript

<lang delphi>program GrayCode;

{$APPTYPE CONSOLE}

uses SysUtils;

function Encode(v: Integer): Integer; begin

 Result := v xor (v shr 1);

end;

function Decode(v: Integer): Integer; begin

 Result := 0;
 while v > 0 do
 begin
   Result := Result xor v;
   v := v shr 1;
 end;

end;

function IntToBin(aValue: LongInt; aDigits: Integer): string; begin

 Result := StringOfChar('0', aDigits);
 while aValue > 0 do
 begin
   if (aValue and 1) = 1 then
     Result[aDigits] := '1';
   Dec(aDigits);
   aValue := aValue shr 1;
 end;

end;

var

 i, g, d: Integer;

begin

 Writeln('decimal  binary   gray    decoded');
 for i := 0 to 31 do
 begin
   g := Encode(i);
   d := Decode(g);
   Writeln(Format('  %2d     %s   %s   %s  %2d', [i, IntToBin(i, 5), IntToBin(g, 5), IntToBin(d, 5), d]));
 end;

end.</lang>

DWScript

<lang delphi>function Encode(v : Integer) : Integer; begin

  Result := v xor (v shr 1);

end;

function Decode(v : Integer) : Integer; begin

  Result := 0;
  while v>0 do begin
     Result := Result xor v;

v := v shr 1;

  end;

end;

PrintLn('decimal binary gray decoded');

var i : Integer; for i:=0 to 31 do begin

  var g := Encode(i);
  var d := Decode(g);
  PrintLn(Format('  %2d     %s   %s   %s  %2d',
                 [i, IntToBin(i, 5), IntToBin(g, 5), IntToBin(d, 5), d]));

end;</lang>

Elixir

Translation of: Erlang

<lang elixir>defmodule Gray_code do

 use Bitwise
 def encode(n), do: bxor(n, bsr(n,1))
 
 def decode(g), do: decode(g,0)
 
 def decode(0,n), do: n
 def decode(g,n), do: decode(bsr(g,1), bxor(g,n))

end

Enum.each(0..31, fn(n) ->

 g = Gray_code.encode(n)
 d = Gray_code.decode(g)
 :io.fwrite("~2B : ~5.2.0B : ~5.2.0B : ~5.2.0B : ~2B~n", [n, n, g, d, d])

end)</lang> output is the same as "Erlang".

Erlang

Translation of: Euphoria

<lang erlang>-module(gray). -export([encode/1, decode/1]).

encode(N) -> N bxor (N bsr 1).

decode(G) -> decode(G,0).

decode(0,N) -> N; decode(G,N) -> decode(G bsr 1, G bxor N). </lang>

Demonstration code: <lang erlang>-module(testgray).

test_encode(N) ->

 G = gray:encode(N),
 D = gray:decode(G),
 io:fwrite("~2B : ~5.2.0B : ~5.2.0B : ~5.2.0B : ~2B~n", [N, N, G, D, D]).

test_encode(N, N) -> []; test_encode(I, N) when I < N -> test_encode(I), test_encode(I+1, N).

main(_) -> test_encode(0,32).</lang>

Output:
 0 : 00000 : 00000 : 00000 :  0
 1 : 00001 : 00001 : 00001 :  1
 2 : 00010 : 00011 : 00010 :  2
 3 : 00011 : 00010 : 00011 :  3
 4 : 00100 : 00110 : 00100 :  4
 5 : 00101 : 00111 : 00101 :  5
 6 : 00110 : 00101 : 00110 :  6
 7 : 00111 : 00100 : 00111 :  7
 8 : 01000 : 01100 : 01000 :  8
 9 : 01001 : 01101 : 01001 :  9
10 : 01010 : 01111 : 01010 : 10
11 : 01011 : 01110 : 01011 : 11
12 : 01100 : 01010 : 01100 : 12
13 : 01101 : 01011 : 01101 : 13
14 : 01110 : 01001 : 01110 : 14
15 : 01111 : 01000 : 01111 : 15
16 : 10000 : 11000 : 10000 : 16
17 : 10001 : 11001 : 10001 : 17
18 : 10010 : 11011 : 10010 : 18
19 : 10011 : 11010 : 10011 : 19
20 : 10100 : 11110 : 10100 : 20
21 : 10101 : 11111 : 10101 : 21
22 : 10110 : 11101 : 10110 : 22
23 : 10111 : 11100 : 10111 : 23
24 : 11000 : 10100 : 11000 : 24
25 : 11001 : 10101 : 11001 : 25
26 : 11010 : 10111 : 11010 : 26
27 : 11011 : 10110 : 11011 : 27
28 : 11100 : 10010 : 11100 : 28
29 : 11101 : 10011 : 11101 : 29
30 : 11110 : 10001 : 11110 : 30
31 : 11111 : 10000 : 11111 : 31

Euphoria

<lang euphoria>function gray_encode(integer n)

   return xor_bits(n,floor(n/2))

end function

function gray_decode(integer n)

   integer g
   g = 0
   while n > 0 do
       g = xor_bits(g,n)
       n = floor(n/2)
   end while
   return g

end function

function dcb(integer n)

   atom d,m
   d = 0
   m = 1
   while n do
       d += remainder(n,2)*m
       n = floor(n/2)
       m *= 10
   end while
   return d

end function

integer j for i = #0 to #1F do

   printf(1,"%05d => ",dcb(i))
   j = gray_encode(i)
   printf(1,"%05d => ",dcb(j))
   j = gray_decode(j)
   printf(1,"%05d\n",dcb(j))

end for</lang>

Output:
00000 => 00000 => 00000
00001 => 00001 => 00001
00010 => 00011 => 00010
00011 => 00010 => 00011
00100 => 00110 => 00100
00101 => 00111 => 00101
00110 => 00101 => 00110
00111 => 00100 => 00111
01000 => 01100 => 01000
01001 => 01101 => 01001
01010 => 01111 => 01010
01011 => 01110 => 01011
01100 => 01010 => 01100
01101 => 01011 => 01101
01110 => 01001 => 01110
01111 => 01000 => 01111
10000 => 11000 => 10000
10001 => 11001 => 10001
10010 => 11011 => 10010
10011 => 11010 => 10011
10100 => 11110 => 10100
10101 => 11111 => 10101
10110 => 11101 => 10110
10111 => 11100 => 10111
11000 => 10100 => 11000
11001 => 10101 => 11001
11010 => 10111 => 11010
11011 => 10110 => 11011
11100 => 10010 => 11100
11101 => 10011 => 11101
11110 => 10001 => 11110
11111 => 10000 => 11111

Factor

Translation of C. <lang factor>USING: math.ranges locals ; IN: rosetta-gray

gray-encode ( n -- n' ) dup -1 shift bitxor ;
gray-decode ( n! -- n' )
  n :> p!
  [ n -1 shift dup n! 0 = not ] [ 
    p n bitxor p! 
  ] while
  p ;
main ( -- )
 -1 32 [a,b] [ dup [ >bin ] [ gray-encode ] bi [ >bin ] [ gray-decode ] bi 4array . ] each ;

MAIN: main </lang> Running above code prints: <lang factor>{ -1 "-1" "0" 0 } { 0 "0" "0" 0 } { 1 "1" "1" 1 } { 2 "10" "11" 2 } { 3 "11" "10" 3 } { 4 "100" "110" 4 } { 5 "101" "111" 5 } { 6 "110" "101" 6 } { 7 "111" "100" 7 } { 8 "1000" "1100" 8 } { 9 "1001" "1101" 9 } { 10 "1010" "1111" 10 } { 11 "1011" "1110" 11 } { 12 "1100" "1010" 12 } { 13 "1101" "1011" 13 } { 14 "1110" "1001" 14 } { 15 "1111" "1000" 15 } { 16 "10000" "11000" 16 } { 17 "10001" "11001" 17 } { 18 "10010" "11011" 18 } { 19 "10011" "11010" 19 } { 20 "10100" "11110" 20 } { 21 "10101" "11111" 21 } { 22 "10110" "11101" 22 } { 23 "10111" "11100" 23 } { 24 "11000" "10100" 24 } { 25 "11001" "10101" 25 } { 26 "11010" "10111" 26 } { 27 "11011" "10110" 27 } { 28 "11100" "10010" 28 } { 29 "11101" "10011" 29 } { 30 "11110" "10001" 30 } { 31 "11111" "10000" 31 } { 32 "100000" "110000" 32 }</lang>

Forth

<lang forth>: >gray ( n -- n ) dup 2/ xor ;

gray> ( n -- n )
 0  1 31 lshift  ( g b mask )
 begin
   >r
    2dup 2/ xor
    r@ and or
   r> 1 rshift
   dup 0=
 until
 drop nip ;
 
test
 2 base !
 32 0 do
   cr i  dup 5 .r ."  ==> "
   >gray dup 5 .r ."  ==> "
   gray>     5 .r
 loop
 decimal ;</lang>

Fortran

Using MIL-STD-1753 extensions in Fortran 77, and formulas found at OEIS for direct and inverse Gray code : <lang fortran> PROGRAM GRAY

     IMPLICIT NONE
     INTEGER IGRAY,I,J,K
     CHARACTER*5 A,B,C
     DO 10 I=0,31
     J=IGRAY(I,1)
     K=IGRAY(J,-1)
     CALL BINARY(A,I,5)
     CALL BINARY(B,J,5)
     CALL BINARY(C,K,5)
     PRINT 99,I,A,B,C,K
  10 CONTINUE
  99 FORMAT(I2,3H : ,A5,4H => ,A5,4H => ,A5,3H : ,I2)
     END
     FUNCTION IGRAY(N,D)
     IMPLICIT NONE
     INTEGER D,K,N,IGRAY
     IF(D.LT.0) GO TO 10
     IGRAY=IEOR(N,ISHFT(N,-1))
     RETURN
  10 K=N
     IGRAY=0
  20 IGRAY=IEOR(IGRAY,K)
     K=K/2
     IF(K.NE.0) GO TO 20
     END
     SUBROUTINE BINARY(S,N,K)
     IMPLICIT NONE
     INTEGER I,K,L,N
     CHARACTER*(*) S
     L=LEN(S)
     DO 10 I=0,K-1

C The following line may replace the next block-if, C on machines using ASCII code : C S(L-I:L-I)=CHAR(48+IAND(1,ISHFT(N,-I))) C On EBCDIC machines, use 240 instead of 48.

     IF(BTEST(N,I)) THEN
     S(L-I:L-I)='1'
     ELSE
     S(L-I:L-I)='0'
     END IF
  10 CONTINUE
     S(1:L-K)=
     END</lang>
 0 : 00000 => 00000 => 00000 :  0
 1 : 00001 => 00001 => 00001 :  1
 2 : 00010 => 00011 => 00010 :  2
 3 : 00011 => 00010 => 00011 :  3
 4 : 00100 => 00110 => 00100 :  4
 5 : 00101 => 00111 => 00101 :  5
 6 : 00110 => 00101 => 00110 :  6
 7 : 00111 => 00100 => 00111 :  7
 8 : 01000 => 01100 => 01000 :  8
 9 : 01001 => 01101 => 01001 :  9
10 : 01010 => 01111 => 01010 : 10
11 : 01011 => 01110 => 01011 : 11
12 : 01100 => 01010 => 01100 : 12
13 : 01101 => 01011 => 01101 : 13
14 : 01110 => 01001 => 01110 : 14
15 : 01111 => 01000 => 01111 : 15
16 : 10000 => 11000 => 10000 : 16
17 : 10001 => 11001 => 10001 : 17
18 : 10010 => 11011 => 10010 : 18
19 : 10011 => 11010 => 10011 : 19
20 : 10100 => 11110 => 10100 : 20
21 : 10101 => 11111 => 10101 : 21
22 : 10110 => 11101 => 10110 : 22
23 : 10111 => 11100 => 10111 : 23
24 : 11000 => 10100 => 11000 : 24
25 : 11001 => 10101 => 11001 : 25
26 : 11010 => 10111 => 11010 : 26
27 : 11011 => 10110 => 11011 : 27
28 : 11100 => 10010 => 11100 : 28
29 : 11101 => 10011 => 11101 : 29
30 : 11110 => 10001 => 11110 : 30
31 : 11111 => 10000 => 11111 : 31

Frink

Frink has built-in functions to convert to and from binary reflected Gray code. <lang frink> for i=0 to 31 {

  gray = binaryToGray[i]
  back = grayToBinary[gray]
  println[(i->binary) + "\t" + (gray->binary) + "\t" + (back->binary)]

} </lang>

Go

Translation of: Euphoria

Binary reflected, as described in the task. Reading down through the solutions, the Euphoria decode algorithm caught my eye as being concise and easy to read. <lang go>package main

import "fmt"

func enc(b int) int {

   return b ^ b>>1

}

func dec(g int) (b int) {

   for ; g != 0; g >>= 1 {
       b ^= g
   }
   return

}

func main() {

   fmt.Println("decimal  binary   gray    decoded")
   for b := 0; b < 32; b++ {
       g := enc(b)
       d := dec(g)
       fmt.Printf("  %2d     %05b   %05b   %05b  %2d\n", b, b, g, d, d)
   }

}</lang>

Output:
decimal  binary   gray    decoded
   0     00000   00000   00000   0
   1     00001   00001   00001   1
   2     00010   00011   00010   2
   3     00011   00010   00011   3
   4     00100   00110   00100   4
   5     00101   00111   00101   5
   6     00110   00101   00110   6
   7     00111   00100   00111   7
   8     01000   01100   01000   8
   9     01001   01101   01001   9
  10     01010   01111   01010  10
  11     01011   01110   01011  11
  12     01100   01010   01100  12
  13     01101   01011   01101  13
  14     01110   01001   01110  14
  15     01111   01000   01111  15
  16     10000   11000   10000  16
  17     10001   11001   10001  17
  18     10010   11011   10010  18
  19     10011   11010   10011  19
  20     10100   11110   10100  20
  21     10101   11111   10101  21
  22     10110   11101   10110  22
  23     10111   11100   10111  23
  24     11000   10100   11000  24
  25     11001   10101   11001  25
  26     11010   10111   11010  26
  27     11011   10110   11011  27
  28     11100   10010   11100  28
  29     11101   10011   11101  29
  30     11110   10001   11110  30
  31     11111   10000   11111  31

Groovy

Solution: <lang groovy>def grayEncode = { i ->

   i ^ (i >>> 1)

}

def grayDecode; grayDecode = { int code ->

   if(code <= 0) return 0
   def h = grayDecode(code >>> 1)
   return (h << 1) + ((code ^ h) & 1)

}</lang>

Test: <lang groovy>def binary = { i, minBits = 1 ->

   def remainder = i
   def bin = []
   while (remainder > 0 || bin.size() <= minBits) {
       bin << (remainder & 1)
       remainder >>>= 1
   }
   bin

}

println "number binary gray code decode" println "====== ====== ========= ======" (0..31).each {

   def code = grayEncode(it)
   def decode = grayDecode(code)
   def iB = binary(it, 5)
   def cB = binary(code, 5)
   printf("    %2d    %1d%1d%1d%1d%1d       %1d%1d%1d%1d%1d       %2d",
       it, iB[4],iB[3],iB[2],iB[1],iB[0], cB[4],cB[3],cB[2],cB[1],cB[0], decode)
   println()

}</lang>

Results:

number   binary   gray code   decode
======   ======   =========   ======
     0    00000       00000        0
     1    00001       00001        1
     2    00010       00011        2
     3    00011       00010        3
     4    00100       00110        4
     5    00101       00111        5
     6    00110       00101        6
     7    00111       00100        7
     8    01000       01100        8
     9    01001       01101        9
    10    01010       01111       10
    11    01011       01110       11
    12    01100       01010       12
    13    01101       01011       13
    14    01110       01001       14
    15    01111       01000       15
    16    10000       11000       16
    17    10001       11001       17
    18    10010       11011       18
    19    10011       11010       19
    20    10100       11110       20
    21    10101       11111       21
    22    10110       11101       22
    23    10111       11100       23
    24    11000       10100       24
    25    11001       10101       25
    26    11010       10111       26
    27    11011       10110       27
    28    11100       10010       28
    29    11101       10011       29
    30    11110       10001       30
    31    11111       10000       31

Haskell

For zero padding, replace the %5s specifiers in the format string with %05s.

<lang Haskell>import Data.Bits import Data.Char import Numeric import Control.Monad import Text.Printf

grayToBin :: (Integral t, Bits t) => t -> t grayToBin 0 = 0 grayToBin g = g `xor` (grayToBin $ g `shiftR` 1)

binToGray :: (Integral t, Bits t) => t -> t binToGray b = b `xor` (b `shiftR` 1)

showBinary :: (Integral t, Show t) => t -> String showBinary n = showIntAtBase 2 intToDigit n ""

showGrayCode :: (Integral t, Bits t, PrintfArg t, Show t) => t -> IO () showGrayCode num = do

   let bin  = showBinary num
   let gray = showBinary (binToGray num)
   printf "int: %2d -> bin: %5s -> gray: %5s\n" num bin gray

main = forM_ [0..31::Int] showGrayCode</lang>

Icon and Unicon

The following works in both languages: <lang unicon>link bitint

procedure main()

   every write(right(i := 0 to 10,4),":",right(int2bit(i),10)," -> ",
                                         right(g := gEncode(i),10)," -> ",
                                         right(b := gDecode(g),10)," -> ",
                                         right(bit2int(b),10))

end

procedure gEncode(b)

   return int2bit(ixor(b, ishift(b,-1)))

end

procedure gDecode(g)

   b := g[1]
   every i := 2 to *g do b ||:= if g[i] == b[i-1] then "0" else "1"
   return b

end</lang>

Sample run:

->gc
   0:         0 ->          0 ->          0 ->          0
   1:         1 ->          1 ->          1 ->          1
   2:        10 ->         11 ->         10 ->          2
   3:        11 ->         10 ->         11 ->          3
   4:       100 ->        110 ->        100 ->          4
   5:       101 ->        111 ->        101 ->          5
   6:       110 ->        101 ->        110 ->          6
   7:       111 ->        100 ->        111 ->          7
   8:      1000 ->       1100 ->       1000 ->          8
   9:      1001 ->       1101 ->       1001 ->          9
  10:      1010 ->       1111 ->       1010 ->         10
->

J

G2B is an invertible function which will translate Gray code to Binary:

<lang j>G2B=: ~:/\&.|:</lang>

Thus G2B inv will translate binary to Gray code.

Required example:

<lang j> n=:i.32

  G2B=: ~:/\&.|:
  (,: ,.@".&.>) 'n';'#:n';'G2B inv#:n';'#.G2B G2B inv#:n'

+--+---------+----------+----------------+ |n |#:n |G2B inv#:n|#.G2B G2B inv#:n| +--+---------+----------+----------------+ | 0|0 0 0 0 0|0 0 0 0 0 | 0 | | 1|0 0 0 0 1|0 0 0 0 1 | 1 | | 2|0 0 0 1 0|0 0 0 1 1 | 2 | | 3|0 0 0 1 1|0 0 0 1 0 | 3 | | 4|0 0 1 0 0|0 0 1 1 0 | 4 | | 5|0 0 1 0 1|0 0 1 1 1 | 5 | | 6|0 0 1 1 0|0 0 1 0 1 | 6 | | 7|0 0 1 1 1|0 0 1 0 0 | 7 | | 8|0 1 0 0 0|0 1 1 0 0 | 8 | | 9|0 1 0 0 1|0 1 1 0 1 | 9 | |10|0 1 0 1 0|0 1 1 1 1 |10 | |11|0 1 0 1 1|0 1 1 1 0 |11 | |12|0 1 1 0 0|0 1 0 1 0 |12 | |13|0 1 1 0 1|0 1 0 1 1 |13 | |14|0 1 1 1 0|0 1 0 0 1 |14 | |15|0 1 1 1 1|0 1 0 0 0 |15 | |16|1 0 0 0 0|1 1 0 0 0 |16 | |17|1 0 0 0 1|1 1 0 0 1 |17 | |18|1 0 0 1 0|1 1 0 1 1 |18 | |19|1 0 0 1 1|1 1 0 1 0 |19 | |20|1 0 1 0 0|1 1 1 1 0 |20 | |21|1 0 1 0 1|1 1 1 1 1 |21 | |22|1 0 1 1 0|1 1 1 0 1 |22 | |23|1 0 1 1 1|1 1 1 0 0 |23 | |24|1 1 0 0 0|1 0 1 0 0 |24 | |25|1 1 0 0 1|1 0 1 0 1 |25 | |26|1 1 0 1 0|1 0 1 1 1 |26 | |27|1 1 0 1 1|1 0 1 1 0 |27 | |28|1 1 1 0 0|1 0 0 1 0 |28 | |29|1 1 1 0 1|1 0 0 1 1 |29 | |30|1 1 1 1 0|1 0 0 0 1 |30 | |31|1 1 1 1 1|1 0 0 0 0 |31 | +--+---------+----------+----------------+</lang>

Java

Translation of: C

<lang java> public class Gray { public static long grayEncode(long n){ return n ^ (n >>> 1); }

public static long grayDecode(long n) { long p = n; while ((n >>>= 1) != 0) p ^= n; return p; } public static void main(String[] args){ System.out.println("i\tBinary\tGray\tDecoded"); for(int i = -1; i < 32;i++){ System.out.print(i +"\t"); System.out.print(Integer.toBinaryString(i) + "\t"); System.out.print(Long.toBinaryString(grayEncode(i))+ "\t"); System.out.println(grayDecode(grayEncode(i))); } } } </lang>

Output:
i	Binary	Gray	Decoded
-1	11111111111111111111111111111111	1000000000000000000000000000000000000000000000000000000000000000	-1
0	0	0	0
1	1	1	1
2	10	11	2
3	11	10	3
4	100	110	4
5	101	111	5
6	110	101	6
7	111	100	7
8	1000	1100	8
9	1001	1101	9
10	1010	1111	10
11	1011	1110	11
12	1100	1010	12
13	1101	1011	13
14	1110	1001	14
15	1111	1000	15
16	10000	11000	16
17	10001	11001	17
18	10010	11011	18
19	10011	11010	19
20	10100	11110	20
21	10101	11111	21
22	10110	11101	22
23	10111	11100	23
24	11000	10100	24
25	11001	10101	25
26	11010	10111	26
27	11011	10110	27
28	11100	10010	28
29	11101	10011	29
30	11110	10001	30
31	11111	10000	31

Here is an example encoding function that does it in a bit-by-bit, more human way: <lang java>public static long grayEncode(long n){ long result = 0; for(int exp = 0; n > 0; n /= 2, exp++){ long nextHighestBit = (n >> 1) & 1; if(nextHighestBit == 1){ result += ((n & 1) == 0) ? (1 << exp) : 0; //flip the bit }else{ result += (n & 1) * (1 << exp); //"n & 1" is "this bit", don't flip it } } return result; }</lang> This decoding function should work for gray codes of any size:

This example is untested. Please check that it's correct, debug it as necessary, and remove this message.


<lang java>public static BigInteger grayDecode(BigInteger n){ String nBits = n.toString(2); String result = nBits.substring(0, 1); for(int i = 1; i < nBits.length(); i++){ //bin[i] = gray[i] ^ bin[i-1]

//XOR with characters result += nBits.charAt(i) != result.charAt(i - 1) ? "1" : "0"; } return new BigInteger(result, 2); }</lang>

Julia

Translation of: C

<lang julia>gray_encode(n) = n $ (n >> 1)

function gray_decode(n)

   p = n
   while (n >>= 1) != 0
       p $= n
   end
   return p

end</lang> Note that these functions work for any integer type, including arbitrary-precision integers (the built-in BigInt type).

K

Binary to Gray code

<lang K> xor: {~x=y}

  gray:{x[0],xor':x}
  / variant: using shift
  gray1:{(x[0],xor[1_ x;-1_ x])}
 
  / variant: iterative
  gray2:{x[0],{:[x[y-1]=1;~x[y];x[y]]}[x]'1+!(#x)-1}</lang>


Gray code to binary

"Accumulated xor" <lang K> g2b:xor\</lang>

An alternative is to find the inverse of the gray code by tracing until fixpoint. Here we find that 1 1 1 1 1 is the inverse of 1 0 0 0 0 <lang K> gray\1 0 0 0 0 (1 0 0 0 0

1 1 0 0 0
1 0 1 0 0
1 1 1 1 0
1 0 0 0 1
1 1 0 0 1
1 0 1 0 1
1 1 1 1 1)

</lang>

As a function (*| takes the last result) <lang K> g2b1:*|{gray x}\</lang>

Iterative version with "do" <lang K> g2b2:{c:#x;b:c#0;b[0]:x[0];i:1;do[#x;b[i]:xor[x[i];b[i-1]];i+:1];b}</lang>


Presentation

<lang K> gray:{x[0],xor':x}

  g2b:xor\
  / using allcomb instead of 2_vs'!32 for nicer presentation
  allcomb:{+(x#y)_vs!_ y^x}
  a:(+allcomb . 5 2)
  `0:,/{n:2_sv x;gg:gray x;gb:g2b gg;n2:2_sv gb;
       ,/$((2$n)," : ",$x," -> ",$gg," -> ",$gb," : ",(2$n2),"\n") }'a</lang>
Output:

<lang K> 0 : 00000 -> 00000 -> 00000 : 0

1 : 00001 -> 00001 -> 00001 :  1 
2 : 00010 -> 00011 -> 00010 :  2 
3 : 00011 -> 00010 -> 00011 :  3 
4 : 00100 -> 00110 -> 00100 :  4 
5 : 00101 -> 00111 -> 00101 :  5 
6 : 00110 -> 00101 -> 00110 :  6 
7 : 00111 -> 00100 -> 00111 :  7 
8 : 01000 -> 01100 -> 01000 :  8 
9 : 01001 -> 01101 -> 01001 :  9 

10 : 01010 -> 01111 -> 01010 : 10 11 : 01011 -> 01110 -> 01011 : 11 12 : 01100 -> 01010 -> 01100 : 12 13 : 01101 -> 01011 -> 01101 : 13 14 : 01110 -> 01001 -> 01110 : 14 15 : 01111 -> 01000 -> 01111 : 15 16 : 10000 -> 11000 -> 10000 : 16 17 : 10001 -> 11001 -> 10001 : 17 18 : 10010 -> 11011 -> 10010 : 18 19 : 10011 -> 11010 -> 10011 : 19 20 : 10100 -> 11110 -> 10100 : 20 21 : 10101 -> 11111 -> 10101 : 21 22 : 10110 -> 11101 -> 10110 : 22 23 : 10111 -> 11100 -> 10111 : 23 24 : 11000 -> 10100 -> 11000 : 24 25 : 11001 -> 10101 -> 11001 : 25 26 : 11010 -> 10111 -> 11010 : 26 27 : 11011 -> 10110 -> 11011 : 27 28 : 11100 -> 10010 -> 11100 : 28 29 : 11101 -> 10011 -> 11101 : 29 30 : 11110 -> 10001 -> 11110 : 30 31 : 11111 -> 10000 -> 11111 : 31</lang>

Liberty BASIC

<lang lb>

   for r =0 to 31
       print " Decimal "; using( "###", r); " is ";
       B$ =dec2Bin$( r)
       print " binary "; B$; ". Binary "; B$;
       G$ =Bin2Gray$( dec2Bin$( r))
       print " is "; G$; " in Gray code, or ";
       B$ =Gray2Bin$( G$)
       print B$; " in pure binary."
   next r
   end
   function Bin2Gray$( bin$)   '   Given a binary number as a string, returns Gray code as a string.
       g$ =left$( bin$, 1)
       for i =2 to len( bin$)
           bitA    =val( mid$( bin$, i -1, 1))
           bitB    =val( mid$( bin$, i,    1))
           AXorB   =bitA xor bitB
           g$      =g$ +str$( AXorB)
       next i
       Bin2Gray$ =g$
   end function
   function Gray2Bin$( g$)     '   Given a Gray code as a string, returns equivalent binary num. 
                               '      as a string
       gl =len(   g$)
       b$ =left$( g$, 1)
       for i =2 to len( g$)
           bitA    =val( mid$( b$, i -1, 1))
           bitB    =val( mid$( g$, i,    1))
           AXorB   =bitA xor bitB
           b$      =b$ +str$( AXorB)
       next i
       Gray2Bin$ =right$( b$, gl)
   end function
   function dec2Bin$( num) '   Given an integer decimal, returns binary equivalent as a string
       n =num
       dec2Bin$ =""
       while ( num >0)
           dec2Bin$    =str$( num mod 2) +dec2Bin$
           num         =int( num /2)
       wend
       if ( n >255) then nBits =16 else nBits =8
       dec2Bin$ =right$( "0000000000000000" +dec2Bin$, nBits)  '   Pad to 8 bit or 16 bit
   end function
   function bin2Dec( b$)   '   Given a binary number as a string, returns decimal equivalent num.
       t =0
       d =len( b$)
       for k =d to 1 step -1
           t   =t +val( mid$( b$, k, 1)) *2^( d -k)
       next k
       bin2Dec =t
   end function

</lang>

Translation of: Euphoria

<lang logo>to gray_encode :number

 output bitxor :number lshift :number -1

end

to gray_decode :code

 local "value
 make "value 0
 while [:code > 0] [
   make "value bitxor :code :value
   make "code lshift :code -1
 ]
 output :value

end</lang>

Demonstration code, including formatters: <lang logo>to format :str :width [pad (char 32)]

 while [(count :str) < :width] [
   make "str word :pad  :str
 ]
 output :str

end

Output binary representation of a number

to binary :number [:width 1]

 local "bits
 ifelse [:number = 0] [
   make "bits 0
 ] [ 
   make "bits "
   while [:number > 0] [
     make "bits word (bitand :number 1) :bits
     make "number lshift :number -1
   ]
 ]
 output (format :bits :width 0)

end

repeat 32 [

 make "num repcount - 1
 make "gray gray_encode :num
 make "decoded gray_decode :gray
 print (sentence (format :num 2) ": (binary :num 5) ": (binary :gray 5) ": 
                 (binary :decoded 5) ": (format :decoded 2)) ]

bye</lang>

Output:
 0 : 00000 : 00000 : 00000 :  0
 1 : 00001 : 00001 : 00001 :  1
 2 : 00010 : 00011 : 00010 :  2
 3 : 00011 : 00010 : 00011 :  3
 4 : 00100 : 00110 : 00100 :  4
 5 : 00101 : 00111 : 00101 :  5
 6 : 00110 : 00101 : 00110 :  6
 7 : 00111 : 00100 : 00111 :  7
 8 : 01000 : 01100 : 01000 :  8
 9 : 01001 : 01101 : 01001 :  9
10 : 01010 : 01111 : 01010 : 10
11 : 01011 : 01110 : 01011 : 11
12 : 01100 : 01010 : 01100 : 12
13 : 01101 : 01011 : 01101 : 13
14 : 01110 : 01001 : 01110 : 14
15 : 01111 : 01000 : 01111 : 15
16 : 10000 : 11000 : 10000 : 16
17 : 10001 : 11001 : 10001 : 17
18 : 10010 : 11011 : 10010 : 18
19 : 10011 : 11010 : 10011 : 19
20 : 10100 : 11110 : 10100 : 20
21 : 10101 : 11111 : 10101 : 21
22 : 10110 : 11101 : 10110 : 22
23 : 10111 : 11100 : 10111 : 23
24 : 11000 : 10100 : 11000 : 24
25 : 11001 : 10101 : 11001 : 25
26 : 11010 : 10111 : 11010 : 26
27 : 11011 : 10110 : 11011 : 27
28 : 11100 : 10010 : 11100 : 28
29 : 11101 : 10011 : 11101 : 29
30 : 11110 : 10001 : 11110 : 30
31 : 11111 : 10000 : 11111 : 31

Lua

Translation of: Euphoria

This code uses the Lua BitOp module. Designed to be a module named gray.lua. <lang lua>local _M = {}

local bit = require('bit') local math = require('math')

_M.encode = function(number)

 return bit.bxor(number, bit.rshift(number, 1));

end

_M.decode = function(gray_code)

 local value = 0
 while gray_code > 0 do
   gray_code, value = bit.rshift(gray_code, 1), bit.bxor(gray_code, value)
 end
 return value

end

return _M</lang>

Demonstration code: <lang lua>local bit = require 'bit' local gray = require 'gray'

-- simple binary string formatter local function to_bit_string(n, width)

 width = width or 1
 local output = ""
 while n > 0 do
   output = bit.band(n,1) .. output
   n = bit.rshift(n,1)
 end
 while #output < width do
   output = '0' .. output
 end
 return output

end

for i = 0,31 do

 g = gray.encode(i);
 gd = gray.decode(g);
 print(string.format("%2d : %s => %s => %s : %2d", i,
   to_bit_string(i,5), to_bit_string(g, 5), 
   to_bit_string(gd,5), gd))

end</lang>

Output:

 0 : 00000 => 00000 => 00000 :  0
 1 : 00001 => 00001 => 00001 :  1
 2 : 00010 => 00011 => 00010 :  2
 3 : 00011 => 00010 => 00011 :  3
 4 : 00100 => 00110 => 00100 :  4
 5 : 00101 => 00111 => 00101 :  5
 6 : 00110 => 00101 => 00110 :  6
 7 : 00111 => 00100 => 00111 :  7
 8 : 01000 => 01100 => 01000 :  8
 9 : 01001 => 01101 => 01001 :  9
10 : 01010 => 01111 => 01010 : 10
11 : 01011 => 01110 => 01011 : 11
12 : 01100 => 01010 => 01100 : 12
13 : 01101 => 01011 => 01101 : 13
14 : 01110 => 01001 => 01110 : 14
15 : 01111 => 01000 => 01111 : 15
16 : 10000 => 11000 => 10000 : 16
17 : 10001 => 11001 => 10001 : 17
18 : 10010 => 11011 => 10010 : 18
19 : 10011 => 11010 => 10011 : 19
20 : 10100 => 11110 => 10100 : 20
21 : 10101 => 11111 => 10101 : 21
22 : 10110 => 11101 => 10110 : 22
23 : 10111 => 11100 => 10111 : 23
24 : 11000 => 10100 => 11000 : 24
25 : 11001 => 10101 => 11001 : 25
26 : 11010 => 10111 => 11010 : 26
27 : 11011 => 10110 => 11011 : 27
28 : 11100 => 10010 => 11100 : 28
29 : 11101 => 10011 => 11101 : 29
30 : 11110 => 10001 => 11110 : 30
31 : 11111 => 10000 => 11111 : 31

Mathematica

<lang Mathematica>graycode[n_]:=BitXor[n,BitShiftRight[n]] graydecode[n_]:=Fold[BitXor,0,FixedPointList[BitShiftRight,n]]</lang>

Output:
Required example:
Grid[{# ,IntegerDigits[#,2],IntegerDigits[graycode@#,2], IntegerDigits[graydecode@graycode@#,2]}&/@Range[32]]
1	{1}	{1}	{1}
2	{1,0}	{1,1}	{1,0}
3	{1,1}	{1,0}	{1,1}
...
15	{1,1,1,1}	{1,0,0,0}	{1,1,1,1}
...
30	{1,1,1,1,0}	{1,0,0,0,1}	{1,1,1,1,0}
31	{1,1,1,1,1}	{1,0,0,0,0}	{1,1,1,1,1}
32	{1,0,0,0,0,0}	{1,1,0,0,0,0}	{1,0,0,0,0,0}


MATLAB

<lang MATLAB> %% Gray Code Generator % this script generates gray codes of n bits % total 2^n -1 continuous gray codes will be generated. % this code follows a recursive approach. therefore, % it can be slow for large n


clear all; clc;

bits = input('Enter the number of bits: '); if (bits<1)

   disp('Sorry, number of bits should be positive');

elseif (mod(bits,1)~=0)

   disp('Sorry, number of bits can only be positive integers');

else

   initial_container = [0;1];
   if bits == 1
       result = initial_container;
   else
       previous_container = initial_container;
       for i=2:bits
           new_gray_container = zeros(2^i,i);
           new_gray_container(1:(2^i)/2,1) = 0;
           new_gray_container(((2^i)/2)+1:end,1) = 1;
           
           for j = 1:(2^i)/2
               new_gray_container(j,2:end) = previous_container(j,:);
           end
           
           for j = ((2^i)/2)+1:2^i
               new_gray_container(j,2:end) = previous_container((2^i)+1-j,:);
           end
           
           previous_container = new_gray_container;
       end
       result = previous_container;
   end
   fprintf('Gray code of %d bits',bits);
   disp(' ');
   disp(result);

end </lang>

Output:
Enter the number of bits: 5
Gray code of 5 bits 
     0     0     0     0     0
     0     0     0     0     1
     0     0     0     1     1
     0     0     0     1     0
     0     0     1     1     0
     0     0     1     1     1
     0     0     1     0     1
     0     0     1     0     0
     0     1     1     0     0
     0     1     1     0     1
     0     1     1     1     1
     0     1     1     1     0
     0     1     0     1     0
     0     1     0     1     1
     0     1     0     0     1
     0     1     0     0     0
     1     1     0     0     0
     1     1     0     0     1
     1     1     0     1     1
     1     1     0     1     0
     1     1     1     1     0
     1     1     1     1     1
     1     1     1     0     1
     1     1     1     0     0
     1     0     1     0     0
     1     0     1     0     1
     1     0     1     1     1
     1     0     1     1     0
     1     0     0     1     0
     1     0     0     1     1
     1     0     0     0     1
     1     0     0     0     0


Mercury

The following is a full implementation of Gray encoding and decoding. It publicly exposes the gray type along with the following value conversion functions:

  • gray.from_int/1
  • gray.to_int/1

The from_int/1 and to_int/1 functions are value conversion functions. from_int/1 converts an int value into the enclosing gray type. to_int/1 converts a gray value back into a regular int type.

The additional gray.coerce/2 predicate converts the representation underlying a gray value into an int value or vice versa (it is moded in both directions). For type safety reasons we do not wish to generally expose the underlying representation, but for some purposes, most notably I/O or storage or their ilk we have to break the type safety. The coerce/2 predicate is used for this purpose.

<lang mercury>:- module gray.

- interface.
- import_module int.
- type gray.

% VALUE conversion functions

- func gray.from_int(int) = gray.
- func gray.to_int(gray) = int.

% REPRESENTATION conversion predicate

- pred gray.coerce(gray, int).
- mode gray.coerce(in, out) is det.
- mode gray.coerce(out, in) is det.
- implementation.
- import_module list.
- type gray
 ---> gray(int).

gray.from_int(X) = gray(X `xor` (X >> 1)).

gray.to_int(gray(G)) = (G > 0 -> G `xor` gray.to_int(gray(G >> 1))

                       ;        G).

gray.coerce(gray(I), I).

- end_module gray.</lang>

The following program tests the above code:

<lang mercury>:- module gray_test.

- interface.
- import_module io.
- pred main(io::di, io::uo) is det.
- implementation.
- import_module gray.
- import_module int, list, string.
- pred check_conversion(list(int)::in, list(gray)::out) is semidet.
- pred display_lists(list(int)::in, list(gray)::in, io::di, io::uo) is det.
- pred display_record(int::in, gray::in, io::di, io::uo) is det.

main(!IO) :-

 Numbers = 0..31,
 ( check_conversion(Numbers, Grays) ->
     io.format("%8s %8s %8s\n", [s("Number"), s("Binary"), s("Gray")], !IO),
     io.format("%8s %8s %8s\n", [s("------"), s("------"), s("----")], !IO),
     display_lists(Numbers, Grays, !IO)
 ;   io.write("Either conversion or back-conversion failed.\n", !IO)).

check_conversion(Numbers, Grays) :-

 Grays = list.map(gray.from_int, Numbers),
 Numbers = list.map(gray.to_int, Grays).

display_lists(Numbers, Grays, !IO) :-

 list.foldl_corresponding(display_record, Numbers, Grays, !IO).

display_record(Number, Gray, !IO) :-

 gray.coerce(Gray, GrayRep),
 NumBin = string.int_to_base_string(Number, 2),
 GrayBin = string.int_to_base_string(GrayRep, 2),
 io.format("%8d %8s %8s\n", [i(Number), s(NumBin), s(GrayBin)], !IO).
- end_module gray_test.</lang>

The main/2 predicate generates a list of numbers from 0 to 31 inclusive and then checks that conversion is working properly. It does so by calling the check_conversion/2 predicate with the list of numbers as an input and the list of Gray-encoded numbers as an output. Note the absence of the usual kinds of testing you'd see in most programming languages. gray.from_int/1 is mapped over the Numbers (input) list and placed into the Grays (output) list. Then gray.to_int is mapped over the Grays list and placed into the Numbers (input) list. Or so it would seem to those used to imperative or functional languages.

In reality what's happening is unification. Since the Grays list is not yet populated, unification is very similar notionally to assignment in other languages. Numbers, however, is instantiated and thus unification is more like testing for equality.

If the conversions check out, main/2 prints off some headers and then displays the lists. Here we're cluttering up the namespace of the gray_test module a little by providing a one-line predicate. While it is true that we could just take the contents of that predicate and place it inline, we've chosen not to do that because the name display_lists communicates more effectively what we intend. The compiler is smart enough to automatically inline that predicate call so there's no efficiency reason not to do it.

However we choose to do that, the result is the same: repeated calls to display_record/4. In that predicate the aforementioned coerce/2 predicate extracts, in this case, the Gray value's representation. This value and the corresponding int value are then converted into a string showing the base-2 representation of their values. io.format/4 then prints them off in a nice format.

The output of the program looks like this:

 Number   Binary     Gray
 ------   ------     ----
      0        0        0
      1        1        1
      2       10       11
      3       11       10
      4      100      110
      5      101      111
      6      110      101
      7      111      100
      8     1000     1100
      9     1001     1101
     10     1010     1111
     11     1011     1110
     12     1100     1010
     13     1101     1011
     14     1110     1001
     15     1111     1000
     16    10000    11000
     17    10001    11001
     18    10010    11011
     19    10011    11010
     20    10100    11110
     21    10101    11111
     22    10110    11101
     23    10111    11100
     24    11000    10100
     25    11001    10101
     26    11010    10111
     27    11011    10110
     28    11100    10010
     29    11101    10011
     30    11110    10001
     31    11111    10000

Nim

Translation of: C

<lang nim>proc grayEncode(n): auto =

 n xor (n shr 1)

proc grayDecode(n): auto =

 result = n
 var t = n
 while t > 0:
   t = t shr 1
   result = result xor t</lang>

Demonstration code: <lang nim>import strutils

for i in 0 .. 32:

 echo i, " => ", toBin(grayEncode(i), 6), " => ", grayDecode(grayEncode(i))</lang>
Output:
0 => 000000 => 0
1 => 000001 => 1
2 => 000011 => 2
3 => 000010 => 3
4 => 000110 => 4
5 => 000111 => 5
6 => 000101 => 6
7 => 000100 => 7
8 => 001100 => 8
9 => 001101 => 9
10 => 001111 => 10
11 => 001110 => 11
12 => 001010 => 12
13 => 001011 => 13
14 => 001001 => 14
15 => 001000 => 15
16 => 011000 => 16
17 => 011001 => 17
18 => 011011 => 18
19 => 011010 => 19
20 => 011110 => 20
21 => 011111 => 21
22 => 011101 => 22
23 => 011100 => 23
24 => 010100 => 24
25 => 010101 => 25
26 => 010111 => 26
27 => 010110 => 27
28 => 010010 => 28
29 => 010011 => 29
30 => 010001 => 30
31 => 010000 => 31
32 => 110000 => 32

OCaml

<lang ocaml>let gray_encode b =

 b lxor (b lsr 1)

let gray_decode n =

 let rec aux p n =
   if n = 0 then p
   else aux (p lxor n) (n lsr 1)
 in
 aux n (n lsr 1)

let bool_string len n =

 let s = String.make len '0' in
 let rec aux i n =
   if n land 1 = 1 then s.[i] <- '1';
   if i <= 0 then s
   else aux (pred i) (n lsr 1)
 in
 aux (pred len) n

let () =

 let s = bool_string 5 in
 for i = 0 to pred 32 do
   let g = gray_encode i in
   let b = gray_decode g in
   Printf.printf "%2d : %s => %s => %s : %2d\n" i (s i) (s g) (s b) b
 done</lang>

PARI/GP

This code may have exposed a bug in PARI 2.4.4: apply(Str, 1) fails. As a workaround I used a closure: apply(k->Str(k), 1). <lang parigp>toGray(n)=bitxor(n,n>>1); fromGray(n)=my(k=1,m=n);while(m>>k,n=bitxor(n,n>>k);k+=k);n; bin(n)=concat(apply(k->Str(k),binary(n)))

for(n=0,31,print(n"\t"bin(n)"\t"bin(g=toGray(n))"\t"fromGray(g)))</lang>

Output:
0	0	0	0
1	1	1	1
2	10	11	2
3	11	10	3
4	100	110	4
5	101	111	5
6	110	101	6
7	111	100	7
8	1000	1100	8
9	1001	1101	9
10	1010	1111	10
11	1011	1110	11
12	1100	1010	12
13	1101	1011	13
14	1110	1001	14
15	1111	1000	15
16	10000	11000	16
17	10001	11001	17
18	10010	11011	18
19	10011	11010	19
20	10100	11110	20
21	10101	11111	21
22	10110	11101	22
23	10111	11100	23
24	11000	10100	24
25	11001	10101	25
26	11010	10111	26
27	11011	10110	27
28	11100	10010	28
29	11101	10011	29
30	11110	10001	30
31	11111	10000	31

Pascal

See Delphi

PicoLisp

<lang PicoLisp>(de grayEncode (N)

  (bin (x| N (>> 1 N))) )

(de grayDecode (G)

  (bin
     (pack
        (let X 0
           (mapcar
              '((C) (setq X (x| X (format C))))
              (chop G) ) ) ) ) )</lang>

Test: <lang PicoLisp>(prinl " Binary Gray Decoded") (for I (range 0 31)

  (let G (grayEncode I)
     (tab (4 9 9 9) I (bin I) G (grayDecode G)) ) )</lang>
Output:
       Binary     Gray  Decoded
   0        0        0        0
   1        1        1        1
   2       10       11        2
   3       11       10        3
   4      100      110        4
   5      101      111        5
   6      110      101        6
   7      111      100        7
   8     1000     1100        8
   9     1001     1101        9
  10     1010     1111       10
  11     1011     1110       11
  12     1100     1010       12
  13     1101     1011       13
  14     1110     1001       14
  15     1111     1000       15
  16    10000    11000       16
  17    10001    11001       17
  18    10010    11011       18
  19    10011    11010       19
  20    10100    11110       20
  21    10101    11111       21
  22    10110    11101       22
  23    10111    11100       23
  24    11000    10100       24
  25    11001    10101       25
  26    11010    10111       26
  27    11011    10110       27
  28    11100    10010       28
  29    11101    10011       29
  30    11110    10001       30
  31    11111    10000       31

Perl

<lang perl>sub bin2gray {

   return $_[0] ^ ($_[0] >> 1);

}

sub gray2bin {

   my ($num)= @_;
   my $bin= $num;
   while( $num >>= 1 ) {
       # a bit ends up flipped iff an odd number of bits to its left is set.
       $bin ^= $num;   # different from the suggested algorithm;
   }                   # avoids using bit mask and explicit bittery
   return $bin;

}

for (0..31) {

   my $gr= bin2gray($_);
   printf "%d\t%b\t%b\t%b\n", $_, $_, $gr, gray2bin($gr);

}</lang>


Perl 6

<lang perl6>sub gray_encode ( Int $n --> Int ) {

   return $n +^ ( $n +> 1 );

}

sub gray_decode ( Int $n is copy --> Int ) {

   my $mask = 1 +< (32-2);
   $n +^= $mask +> 1 if $n +& $mask while $mask +>= 1;
   return $n;

}

for ^32 -> $n {

   my $g = gray_encode($n);
   my $d = gray_decode($g);
   printf "%2d: %5b => %5b => %5b: %2d\n", $n, $n, $g, $d, $d;
   die if $d != $n;

}</lang>

This version is a translation of the Haskell solution, and produces the same output as the first Perl 6 solution.

Translation of: Haskell

<lang perl6>multi bin_to_gray ( [] ) { [] } multi bin_to_gray ( [$head, *@tail] ) {

   return [ $head, ( @tail Z+^ ($head, @tail) ) ];

}

multi gray_to_bin ( [] ) { [] } multi gray_to_bin ( [$head, *@tail] ) {

   my @bin := $head, (@tail Z+^ @bin);
   return @bin.flat;

}

for ^32 -> $n {

   my @b = $n.fmt('%b').comb;
   my $g = bin_to_gray(@b);
   my $d = gray_to_bin($g);
   printf "%2d: %5s => %5s => %5s: %2d\n",
           $n, @b.join, $g.join, $d.join, :2($d.join);
   die if :2($d.join) != $n;

}</lang>

Output:
 0:     0 =>     0 =>     0:  0
 1:     1 =>     1 =>     1:  1
 2:    10 =>    11 =>    10:  2
 3:    11 =>    10 =>    11:  3
 4:   100 =>   110 =>   100:  4
 5:   101 =>   111 =>   101:  5
 6:   110 =>   101 =>   110:  6
 7:   111 =>   100 =>   111:  7
 8:  1000 =>  1100 =>  1000:  8
 9:  1001 =>  1101 =>  1001:  9
10:  1010 =>  1111 =>  1010: 10
11:  1011 =>  1110 =>  1011: 11
12:  1100 =>  1010 =>  1100: 12
13:  1101 =>  1011 =>  1101: 13
14:  1110 =>  1001 =>  1110: 14
15:  1111 =>  1000 =>  1111: 15
16: 10000 => 11000 => 10000: 16
17: 10001 => 11001 => 10001: 17
18: 10010 => 11011 => 10010: 18
19: 10011 => 11010 => 10011: 19
20: 10100 => 11110 => 10100: 20
21: 10101 => 11111 => 10101: 21
22: 10110 => 11101 => 10110: 22
23: 10111 => 11100 => 10111: 23
24: 11000 => 10100 => 11000: 24
25: 11001 => 10101 => 11001: 25
26: 11010 => 10111 => 11010: 26
27: 11011 => 10110 => 11011: 27
28: 11100 => 10010 => 11100: 28
29: 11101 => 10011 => 11101: 29
30: 11110 => 10001 => 11110: 30
31: 11111 => 10000 => 11111: 31

Perl 6 distinguishes numeric bitwise operators with a leading + sign, so +< and +> are left and right shift, while +& is a bitwise AND, while +^ is bitwise XOR (here used as part of an assignment metaoperator).

PHP

<lang php> <?php

/**

* @author Elad Yosifon
*/

/**

* @param int $binary
* @return int
*/

function gray_encode($binary){ return $binary ^ ($binary >> 1); }

/**

* @param int $gray
* @return int
*/

function gray_decode($gray){ $binary = $gray; while($gray >>= 1) $binary ^= $gray; return $binary; }

for($i=0;$i<32;$i++){ $gray_encoded = gray_encode($i); printf("%2d : %05b => %05b => %05b : %2d \n",$i, $i, $gray_encoded, $gray_encoded, gray_decode($gray_encoded)); } </lang>

Output:
 0 : 00000 => 00000 => 00000 :  0 
 1 : 00001 => 00001 => 00001 :  1 
 2 : 00010 => 00011 => 00011 :  2 
 3 : 00011 => 00010 => 00010 :  3 
 4 : 00100 => 00110 => 00110 :  4 
 5 : 00101 => 00111 => 00111 :  5 
 6 : 00110 => 00101 => 00101 :  6 
 7 : 00111 => 00100 => 00100 :  7 
 8 : 01000 => 01100 => 01100 :  8 
 9 : 01001 => 01101 => 01101 :  9 
10 : 01010 => 01111 => 01111 : 10 
11 : 01011 => 01110 => 01110 : 11 
12 : 01100 => 01010 => 01010 : 12 
13 : 01101 => 01011 => 01011 : 13 
14 : 01110 => 01001 => 01001 : 14 
15 : 01111 => 01000 => 01000 : 15 
16 : 10000 => 11000 => 11000 : 16 
17 : 10001 => 11001 => 11001 : 17 
18 : 10010 => 11011 => 11011 : 18 
19 : 10011 => 11010 => 11010 : 19 
20 : 10100 => 11110 => 11110 : 20 
21 : 10101 => 11111 => 11111 : 21 
22 : 10110 => 11101 => 11101 : 22 
23 : 10111 => 11100 => 11100 : 23 
24 : 11000 => 10100 => 10100 : 24 
25 : 11001 => 10101 => 10101 : 25 
26 : 11010 => 10111 => 10111 : 26 
27 : 11011 => 10110 => 10110 : 27 
28 : 11100 => 10010 => 10010 : 28 
29 : 11101 => 10011 => 10011 : 29 
30 : 11110 => 10001 => 10001 : 30 
31 : 11111 => 10000 => 10000 : 31 

PL/I

<lang PL/I>(stringrange, stringsize): Gray_code: procedure options (main); /* 15 November 2013 */

  declare (bin(0:31), g(0:31), b2(0:31)) bit (5);
  declare (c, carry) bit (1);
  declare (i, j) fixed binary (7);
  bin(0) = '00000'b;
  do i = 0 to 31;
     if i > 0 then
        do;
           carry = '1'b;
           bin(i) = bin(i-1);
           do j = 5 to 1 by -1;
              c = substr(bin(i), j, 1) & carry;
              substr(bin(i), j, 1) = substr(bin(i), j, 1) ^ carry;
              carry = c;              
           end;
        end;
     g(i) = bin(i) ^ '0'b || substr(bin(i), 1, 4);
  end;
  do i = 0 to 31;
     substr(b2(i), 1, 1) = substr(g(i), 1, 1);
     do j = 2 to 5;
        substr(b2(i), j, 1) = substr(g(i), j, 1) ^ substr(bin(i), j-1, 1);
     end;
  end;
  do i = 0 to 31;
     put skip edit (i, bin(i), g(i), b2(i)) (f(2), 3(x(1), b));
  end;

end Gray_code;</lang>

 0 00000 00000 00000
 1 00001 00001 00001
 2 00010 00011 00010
 3 00011 00010 00011
 4 00100 00110 00100
 5 00101 00111 00101
 6 00110 00101 00110
 7 00111 00100 00111
 8 01000 01100 01000
 9 01001 01101 01001
10 01010 01111 01010
11 01011 01110 01011
12 01100 01010 01100
13 01101 01011 01101
14 01110 01001 01110
15 01111 01000 01111
16 10000 11000 10000
17 10001 11001 10001
18 10010 11011 10010
19 10011 11010 10011
20 10100 11110 10100
21 10101 11111 10101
22 10110 11101 10110
23 10111 11100 10111
24 11000 10100 11000
25 11001 10101 11001
26 11010 10111 11010
27 11011 10110 11011
28 11100 10010 11100
29 11101 10011 11101
30 11110 10001 11110
31 11111 10000 11111

PowerBASIC

<lang powerbasic>function gray%(byval n%)

 gray%=n% xor (n%\2)

end function

function igray%(byval n%)

 r%=0
 while n%>0
   r%=r% xor n%
   shift right n%,1
 wend
 igray%=r%

end function

print " N GRAY INV" for n%=0 to 31

 g%=gray%(n%)
 print bin$(n%);" ";bin$(g%);" ";bin$(igray%(g%))

next</lang>

Prolog

Codecs

The encoding and decoding predicates are simple and will work with any Prolog that supports bitwise integer operations.

Works with: SWI Prolog
Works with: YAP

<lang Prolog>to_gray(N, G) :-

 N0 is N >> 1,
 G is N xor N0.

from_gray(G, N) :-

 ( G > 0
 ->  S is G >> 1,
     from_gray(S, N0),
     N is G xor N0
 ;   N is G ).</lang>

Test Code

A quick driver around this to test it will prove the point. (This test script uses features not available in every Prolog implementation.)

Works with: SWI Prolog
Works with: YAP

<lang Prolog>:- use_module(library(apply)).

to_gray(N, G) :-

 N0 is N >> 1,
 G is N xor N0.

from_gray(G, N) :-

 ( G > 0
 ->  S is G >> 1,
     from_gray(S, N0),
     N is G xor N0
 ;   N is G ).

make_num(In, Out) :-

 atom_to_term(In, Out, _),
 integer(Out).

write_record(Number, Gray, Decoded) :-

 format('~w~10|~2r~10+~2r~10+~2r~10+~w~n',
        [Number, Number, Gray, Decoded, Decoded]).

go :-

 setof(N, between(0, 31, N), Numbers),
 maplist(to_gray, Numbers, Grays),
 maplist(from_gray, Grays, Decodeds),
 format('~w~10|~w~10+~w~10+~w~10+~w~n',
        ['Number', 'Binary', 'Gray', 'Decoded', 'Number']),
 format('~w~10|~w~10+~w~10+~w~10+~w~n',
        ['------', '------', '----', '-------', '------']),
 maplist(write_record, Numbers, Grays, Decodeds).

go :- halt(1). </lang>

Output:

Putting all of this in a file, we execute it, getting the following results:

% swipl -q -t go -f gray.pl                    # OR: yap -q -z go,halt -f gray.pl
Number    Binary    Gray      Decoded   Number
------    ------    ----      -------   ------
0         0         0         0         0
1         1         1         1         1
2         10        11        10        2
3         11        10        11        3
4         100       110       100       4
5         101       111       101       5
6         110       101       110       6
7         111       100       111       7
8         1000      1100      1000      8
9         1001      1101      1001      9
10        1010      1111      1010      10
11        1011      1110      1011      11
12        1100      1010      1100      12
13        1101      1011      1101      13
14        1110      1001      1110      14
15        1111      1000      1111      15
16        10000     11000     10000     16
17        10001     11001     10001     17
18        10010     11011     10010     18
19        10011     11010     10011     19
20        10100     11110     10100     20
21        10101     11111     10101     21
22        10110     11101     10110     22
23        10111     11100     10111     23
24        11000     10100     11000     24
25        11001     10101     11001     25
26        11010     10111     11010     26
27        11011     10110     11011     27
28        11100     10010     11100     28
29        11101     10011     11101     29
30        11110     10001     11110     30
31        11111     10000     11111     31

PureBasic

<lang PureBasic>Procedure.i gray_encode(n)

 ProcedureReturn n ! (n >> 1)

EndProcedure

Procedure.i gray_decode(g)

 Protected bit = 1 << (8 * SizeOf(Integer) - 2)
 Protected b = g & bit, p = b >> 1
  
 While bit > 1
   bit >> 1
   b | (p ! (g & bit))
   p = (b & bit) >> 1
 Wend 
 ProcedureReturn b

EndProcedure

If OpenConsole()

 PrintN("Number Binary Gray    Decoded")
 Define i, n
 For i = 0 To 31
   g = gray_encode(i)
   Print(RSet(Str(i), 2, "0") + Space(5))
   Print(RSet(Bin(g, #PB_Byte), 5, "0") + Space(2))
   n = gray_decode(g)
   Print(RSet(Bin(n, #PB_Byte), 5, "0") + Space(3))
   PrintN(RSet(Str(n), 2, "0"))
 Next
  
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
 CloseConsole()

EndIf</lang>

Output:
Number Binary Gray    Decoded
00     00000  00000   00
01     00001  00001   01
02     00011  00010   02
03     00010  00011   03
04     00110  00100   04
05     00111  00101   05
06     00101  00110   06
07     00100  00111   07
08     01100  01000   08
09     01101  01001   09
10     01111  01010   10
11     01110  01011   11
12     01010  01100   12
13     01011  01101   13
14     01001  01110   14
15     01000  01111   15
16     11000  10000   16
17     11001  10001   17
18     11011  10010   18
19     11010  10011   19
20     11110  10100   20
21     11111  10101   21
22     11101  10110   22
23     11100  10111   23
24     10100  11000   24
25     10101  11001   25
26     10111  11010   26
27     10110  11011   27
28     10010  11100   28
29     10011  11101   29
30     10001  11110   30
31     10000  11111   31

Python

This example works with lists of discrete binary digits.

First some int<>bin conversion routines

<lang python>>>> def int2bin(n): 'From positive integer to list of binary bits, msb at index 0' if n: bits = [] while n: n,remainder = divmod(n, 2) bits.insert(0, remainder) return bits else: return [0]


>>> def bin2int(bits): 'From binary bits, msb at index 0 to integer' i = 0 for bit in bits: i = i * 2 + bit return i</lang>

Now the bin<>gray converters.

These follow closely the methods in the animation seen here: Converting Between Gray and Binary Codes. <lang python>>>> def bin2gray(bits): return bits[:1] + [i ^ ishift for i, ishift in zip(bits[:-1], bits[1:])]

>>> def gray2bin(bits): b = [bits[0]] for nextb in bits[1:]: b.append(b[-1] ^ nextb) return b</lang>

Sample output

<lang python>>>> for i in range(16): print('int:%2i -> bin:%12r -> gray:%12r -> bin:%12r -> int:%2i' % ( i, int2bin(i), bin2gray(int2bin(i)), gray2bin(bin2gray(int2bin(i))), bin2int(gray2bin(bin2gray(int2bin(i)))) ))


int: 0 -> bin: [0] -> gray: [0] -> bin: [0] -> int: 0 int: 1 -> bin: [1] -> gray: [1] -> bin: [1] -> int: 1 int: 2 -> bin: [1, 0] -> gray: [1, 1] -> bin: [1, 0] -> int: 2 int: 3 -> bin: [1, 1] -> gray: [1, 0] -> bin: [1, 1] -> int: 3 int: 4 -> bin: [1, 0, 0] -> gray: [1, 1, 0] -> bin: [1, 0, 0] -> int: 4 int: 5 -> bin: [1, 0, 1] -> gray: [1, 1, 1] -> bin: [1, 0, 1] -> int: 5 int: 6 -> bin: [1, 1, 0] -> gray: [1, 0, 1] -> bin: [1, 1, 0] -> int: 6 int: 7 -> bin: [1, 1, 1] -> gray: [1, 0, 0] -> bin: [1, 1, 1] -> int: 7 int: 8 -> bin:[1, 0, 0, 0] -> gray:[1, 1, 0, 0] -> bin:[1, 0, 0, 0] -> int: 8 int: 9 -> bin:[1, 0, 0, 1] -> gray:[1, 1, 0, 1] -> bin:[1, 0, 0, 1] -> int: 9 int:10 -> bin:[1, 0, 1, 0] -> gray:[1, 1, 1, 1] -> bin:[1, 0, 1, 0] -> int:10 int:11 -> bin:[1, 0, 1, 1] -> gray:[1, 1, 1, 0] -> bin:[1, 0, 1, 1] -> int:11 int:12 -> bin:[1, 1, 0, 0] -> gray:[1, 0, 1, 0] -> bin:[1, 1, 0, 0] -> int:12 int:13 -> bin:[1, 1, 0, 1] -> gray:[1, 0, 1, 1] -> bin:[1, 1, 0, 1] -> int:13 int:14 -> bin:[1, 1, 1, 0] -> gray:[1, 0, 0, 1] -> bin:[1, 1, 1, 0] -> int:14 int:15 -> bin:[1, 1, 1, 1] -> gray:[1, 0, 0, 0] -> bin:[1, 1, 1, 1] -> int:15 >>> </lang>

R

<lang r> GrayEncode <- function(binary) { gray <- substr(binary,1,1) repeat { if (substr(binary,1,1) != substr(binary,2,2)) gray <- paste(gray,"1",sep="") else gray <- paste(gray,"0",sep="") binary <- substr(binary,2,nchar(binary)) if (nchar(binary) <=1) { break } } return (gray) } GrayDecode <- function(gray) { binary <- substr(gray,1,1) repeat { if (substr(binary,nchar(binary),nchar(binary)) != substr(gray,2,2)) binary <- paste(binary ,"1",sep="") else binary <- paste(binary ,"0",sep="") gray <- substr(gray,2,nchar(gray))

if (nchar(gray) <=1) { break } } return (binary) } </lang>

Racket

<lang racket>

  1. lang racket

(define (gray-encode n) (bitwise-xor n (arithmetic-shift n -1)))

(define (gray-decode n)

 (letrec ([loop (lambda(g bits)
                  (if (> bits 0)
                      (loop (bitwise-xor g bits) (arithmetic-shift bits -1))
                      g))])

(loop 0 n)))

(define (to-bin n) (format "~b" n)) (define (show-table)

 (for ([i (in-range 1 32)]) 
   (printf "~a | ~a | ~a ~n"
           (~r i #:min-width 2 #:pad-string "0")
           (~a (to-bin(gray-encode i)) #:width 5 #:align 'right #:pad-string "0")
           (~a (to-bin (gray-decode(gray-encode i))) #:width 5 #:align 'right #:pad-string "0"))))

</lang>

Output:
> (show-table)
01 | 00001 | 00001
02 | 00011 | 00010
03 | 00010 | 00011
04 | 00110 | 00100
05 | 00111 | 00101
06 | 00101 | 00110
07 | 00100 | 00111
08 | 01100 | 01000
09 | 01101 | 01001
10 | 01111 | 01010
11 | 01110 | 01011
12 | 01010 | 01100
13 | 01011 | 01101
14 | 01001 | 01110
15 | 01000 | 01111
16 | 11000 | 10000
17 | 11001 | 10001
18 | 11011 | 10010
19 | 11010 | 10011
20 | 11110 | 10100
21 | 11111 | 10101
22 | 11101 | 10110
23 | 11100 | 10111
24 | 10100 | 11000
25 | 10101 | 11001
26 | 10111 | 11010
27 | 10110 | 11011
28 | 10010 | 11100
29 | 10011 | 11101
30 | 10001 | 11110
31 | 10000 | 11111

REXX

The leading zeroes for the binary numbers and the gray code could've easily been elided. <lang rexx>/*REXX program to convert decimal───> binary ───> gray code ───> binary.*/ parse arg N .; if N== then N=31 /*Not specified? Then use default*/ L=max(1,length(strip(x2b(d2x(N)),'L',0))) /*for cell width formatting.*/ w=14 /*used for cell width formatting.*/ _=center('binary',w,'─') /*2nd and 4th part of the header.*/ say center('decimal',w,'─')">" _">" center('gray code',w,'─')">" _ /*hdr*/

    do j=0  to N;     b=right(x2b(d2x(j)),L,0)      /*handle 0  ──►  N.*/
    g=b2gray(b)                       /*convert binary to gray code.   */
    a=gray2b(g)                       /*convert gray code to binary.   */
    say center(j,w+1) center(b,w+1) center(g,w+1) center(a,w+1)  /*tell*/
    end   /*j*/

exit /*stick a fork in it, we're done.*/ /*───────────────────────────────────B2GRAY subroutine──────────────────*/ b2gray: procedure; parse arg x $=left(x,1); do b=2 to length(x)

                               $=$||(substr(x,b-1,1) && substr(x,b,1))
                               end   /*b*/        /* && is eXclusive OR*/

return $ /*───────────────────────────────────GRAY2B subroutine──────────────────*/ gray2b: procedure; parse arg x $=left(x,1); do g=2 to length(x)

                               $=$ || (right($,1)    && substr(x,g,1))
                               end   /*g*/        /* && is eXclusive OR*/

return $</lang>

Output:

when using the default input

───decimal────> ────binary────> ──gray code───> ────binary────
       0             00000           00000           00000
       1             00001           00001           00001
       2             00010           00011           00010
       3             00011           00010           00011
       4             00100           00110           00100
       5             00101           00111           00101
       6             00110           00101           00110
       7             00111           00100           00111
       8             01000           01100           01000
       9             01001           01101           01001
      10             01010           01111           01010
      11             01011           01110           01011
      12             01100           01010           01100
      13             01101           01011           01101
      14             01110           01001           01110
      15             01111           01000           01111
      16             10000           11000           10000
      17             10001           11001           10001
      18             10010           11011           10010
      19             10011           11010           10011
      20             10100           11110           10100
      21             10101           11111           10101
      22             10110           11101           10110
      23             10111           11100           10111
      24             11000           10100           11000
      25             11001           10101           11001
      26             11010           10111           11010
      27             11011           10110           11011
      28             11100           10010           11100
      29             11101           10011           11101
      30             11110           10001           11110
      31             11111           10000           11111 

Ruby

Integer#from_gray has recursion so it can use each bit of the answer to compute the next bit.

<lang ruby>class Integer

 # Converts a normal integer to a Gray code.
 def to_gray
   raise Math::DomainError, "integer is negative" if self < 0
   self ^ (self >> 1)
 end
 
 # Converts a Gray code to a normal integer.
 def from_gray
   raise Math::DomainError, "integer is negative" if self < 0
   recurse = proc do |i|
     next 0 if i == 0
     o = recurse[i >> 1] << 1
     o | (i[0] ^ o[1])
   end
   recurse[self]
 end

end

(0..31).each do |number|

 encoded = number.to_gray
 decoded = encoded.from_gray
 printf "%2d : %5b => %5b => %5b : %2d\n",
        number, number, encoded, decoded, decoded

end</lang>

Output:
 0 :     0 =>     0 =>     0 :  0
 1 :     1 =>     1 =>     1 :  1
 2 :    10 =>    11 =>    10 :  2
 3 :    11 =>    10 =>    11 :  3
 4 :   100 =>   110 =>   100 :  4
 5 :   101 =>   111 =>   101 :  5
 6 :   110 =>   101 =>   110 :  6
 7 :   111 =>   100 =>   111 :  7
 8 :  1000 =>  1100 =>  1000 :  8
 9 :  1001 =>  1101 =>  1001 :  9
10 :  1010 =>  1111 =>  1010 : 10
11 :  1011 =>  1110 =>  1011 : 11
12 :  1100 =>  1010 =>  1100 : 12
13 :  1101 =>  1011 =>  1101 : 13
14 :  1110 =>  1001 =>  1110 : 14
15 :  1111 =>  1000 =>  1111 : 15
16 : 10000 => 11000 => 10000 : 16
17 : 10001 => 11001 => 10001 : 17
18 : 10010 => 11011 => 10010 : 18
19 : 10011 => 11010 => 10011 : 19
20 : 10100 => 11110 => 10100 : 20
21 : 10101 => 11111 => 10101 : 21
22 : 10110 => 11101 => 10110 : 22
23 : 10111 => 11100 => 10111 : 23
24 : 11000 => 10100 => 11000 : 24
25 : 11001 => 10101 => 11001 : 25
26 : 11010 => 10111 => 11010 : 26
27 : 11011 => 10110 => 11011 : 27
28 : 11100 => 10010 => 11100 : 28
29 : 11101 => 10011 => 11101 : 29
30 : 11110 => 10001 => 11110 : 30
31 : 11111 => 10000 => 11111 : 31

Rust

<lang rust>fn gray_encode(integer: uint) -> uint { (integer >> 1) ^ integer }

fn gray_decode(integer: uint) -> uint { match integer { 0 => 0, _ => integer ^ gray_decode(integer >> 1) } }


fn main() { for i in range(0u,32u) { println!("{:2} {:0>5t} {:0>5t} {:2}", i, i, gray_encode(i), gray_decode(i)); }

}</lang>

Scala

Functional style: the Gray code is encoded to, and decoded from a String. The scanLeft function takes a sequence (here, of characters) and produces a collection containing cumulative results of applying an operator going left to right. Here the operator is exclusive-or, "^", and we can use "_" placeholders to represent the arguments to the left and right. tail removes the "0" we added as the initial accumulator value, and mkString turns the collection back into a String, that we can parse into an integer (Integer.parseInt is directly from the java.lang package). <lang scala>def encode(n: Int) = (n ^ (n >>> 1)).toBinaryString def decode(s: String) = Integer.parseInt( s.scanLeft(0)(_ ^ _.asDigit).tail.mkString , 2)

println("decimal binary gray decoded") for (i <- 0 to 31; g = encode(i))

 println("%7d  %6s  %5s  %7s".format(i, i.toBinaryString, g, decode(g)))

</lang>

Output:
decimal  binary   gray  decoded
      0       0      0        0
      1       1      1        1
      2      10     11        2
      3      11     10        3
      4     100    110        4
      5     101    111        5
      6     110    101        6
      7     111    100        7
      8    1000   1100        8
      9    1001   1101        9
     10    1010   1111       10
     11    1011   1110       11
     12    1100   1010       12
     13    1101   1011       13
     14    1110   1001       14
     15    1111   1000       15
     16   10000  11000       16
     17   10001  11001       17
     18   10010  11011       18
     19   10011  11010       19
     20   10100  11110       20
     21   10101  11111       21
     22   10110  11101       22
     23   10111  11100       23
     24   11000  10100       24
     25   11001  10101       25
     26   11010  10111       26
     27   11011  10110       27
     28   11100  10010       28
     29   11101  10011       29
     30   11110  10001       30
     31   11111  10000       31

Alternatively, more imperative style: <lang scala>def encode(n: Long) = n ^ (n >>> 1)

def decode(n: Long) = {

 var g = 0L
 var bits = n
 while (bits > 0) {
   g ^= bits
   bits >>= 1
 }
 g

}

def toBin(n: Long) = ("0000" + n.toBinaryString) takeRight 5

println("decimal binary gray decoded") for (i <- 0 until 32) {

 val g = encode(i)
 println("%7d  %6s  %5s  %7s".format(i, toBin(i), toBin(g), decode(g)))

}</lang> Improved version of decode using functional style (recursion+local method). No vars and mutations. <lang scala>def decode(n:Long)={

 def calc(g:Long,bits:Long):Long=if (bits>0) calc(g^bits, bits>>1) else g
 calc(0, n)

}</lang>

Output:
decimal  binary   gray  decoded
      0   00000  00000        0
      1   00001  00001        1
      2   00010  00011        2
      3   00011  00010        3
      4   00100  00110        4
      5   00101  00111        5
      6   00110  00101        6
      7   00111  00100        7
      8   01000  01100        8
      9   01001  01101        9
     10   01010  01111       10
     11   01011  01110       11
     12   01100  01010       12
     13   01101  01011       13
     14   01110  01001       14
     15   01111  01000       15
     16   10000  11000       16
     17   10001  11001       17
     18   10010  11011       18
     19   10011  11010       19
     20   10100  11110       20
     21   10101  11111       21
     22   10110  11101       22
     23   10111  11100       23
     24   11000  10100       24
     25   11001  10101       25
     26   11010  10111       26
     27   11011  10110       27
     28   11100  10010       28
     29   11101  10011       29
     30   11110  10001       30
     31   11111  10000       31

Scratch

[1]

Seed7

The type bin32 is intended for bit operations that are not defined for integer values. Bin32 is used for the exclusive or (><) operation. <lang seed7>$ include "seed7_05.s7i";

 include "bin32.s7i";

const func integer: grayEncode (in integer: n) is

 return ord(bin32(n) >< bin32(n >> 1));

const func integer: grayDecode (in var integer: n) is func

 result
   var integer: decoded is 0;
 begin
   decoded := n;
   while n > 1 do
     n >>:= 1;
     decoded := ord(bin32(decoded) >< bin32(n));
   end while;
 end func;

const proc: main is func

 local
   var integer: i is 0;
 begin
   for i range 0 to 32 do
     writeln(i <& " => " <& grayEncode(i) radix 2 lpad0 6 <& " => " <& grayDecode(grayEncode(i)));
   end for;
 end func;</lang>
Output:
0 => 000000 => 0
1 => 000001 => 1
2 => 000011 => 2
3 => 000010 => 3
4 => 000110 => 4
5 => 000111 => 5
6 => 000101 => 6
7 => 000100 => 7
8 => 001100 => 8
9 => 001101 => 9
10 => 001111 => 10
11 => 001110 => 11
12 => 001010 => 12
13 => 001011 => 13
14 => 001001 => 14
15 => 001000 => 15
16 => 011000 => 16
17 => 011001 => 17
18 => 011011 => 18
19 => 011010 => 19
20 => 011110 => 20
21 => 011111 => 21
22 => 011101 => 22
23 => 011100 => 23
24 => 010100 => 24
25 => 010101 => 25
26 => 010111 => 26
27 => 010110 => 27
28 => 010010 => 28
29 => 010011 => 29
30 => 010001 => 30
31 => 010000 => 31
32 => 110000 => 32

Sidef

Translation of: Perl

<lang ruby>__USE_INTNUM__

func bin2gray(n) {

   n ^ (n >> 1);

}

func gray2bin(num) {

   var bin = num;
   while (num >>= 1) { bin ^= num };
   return bin;

}

0..31 -> each { |i|

   var gr = bin2gray(i);
   printf("%d\t%b\t%b\t%b\n", i, i, gr, gray2bin(gr));

}</lang>

Standard ML

<lang sml>fun gray_encode b =

 Word.xorb (b, Word.>> (b, 0w1))

fun gray_decode n =

 let
   fun aux (p, n) =
     if n = 0w0 then p
     else aux (Word.xorb (p, n), Word.>> (n, 0w1))
 in
   aux (n, Word.>> (n, 0w1))
 end;

val s = Word.fmt StringCvt.BIN; fun aux i =

 if i = 0w32 then
   ()
 else
   let
     val g = gray_encode i
     val b = gray_decode g
   in
     print (Word.toString i ^ " :\t" ^ s i ^ " => " ^ s g ^ " => " ^ s b ^ "\t: " ^ Word.toString b ^ "\n");
     aux (i + 0w1)
   end;

aux 0w0</lang>

SQL

<lang sql> DECLARE @binary AS NVARCHAR(MAX) = '001010111' DECLARE @gray AS NVARCHAR(MAX) =

--Encoder SET @gray = LEFT(@binary, 1)

WHILE LEN(@binary) > 1

 BEGIN 
     IF LEFT(@binary, 1) != SUBSTRING(@binary, 2, 1) 
       SET @gray = @gray + '1' 
     ELSE 
       SET @gray = @gray + '0' 
     SET @binary = RIGHT(@binary, LEN(@binary) - 1) 
 END 

SELECT @gray

--Decoder SET @binary = LEFT(@gray, 1)

WHILE LEN(@gray) > 1

 BEGIN 
     IF RIGHT(@binary, 1) != SUBSTRING(@gray, 2, 1) 
       SET @binary = @binary + '1' 
     ELSE 
       SET @binary = @binary + '0' 
     SET @gray = RIGHT(@gray, LEN(@gray) - 1) 
 END 

SELECT @binary </lang>

Tcl

<lang tcl>namespace eval gray {

   proc encode n {

expr {$n ^ $n >> 1}

   }
   proc decode n {

# Compute some bit at least as large as MSB set i [expr {2**int(ceil(log($n+1)/log(2)))}] set b [set bprev [expr {$n & $i}]] while {[set i [expr {$i >> 1}]]} { set b [expr {$b | [set bprev [expr {$n & $i ^ $bprev >> 1}]]}] } return $b

   }

}</lang> Demonstrating: <lang tcl>package require Tcl 8.6; # Just for %b format specifier for {set i 0} {$i < 32} {incr i} {

   set g [gray::encode $i]
   set b [gray::decode $g]
   puts [format "%2d: %05b => %05b => %05b : %2d" $i $i $g $b $b]

}</lang>

Output:
 0: 00000 => 00000 => 00000 :  0
 1: 00001 => 00001 => 00001 :  1
 2: 00010 => 00011 => 00010 :  2
 3: 00011 => 00010 => 00011 :  3
 4: 00100 => 00110 => 00100 :  4
 5: 00101 => 00111 => 00101 :  5
 6: 00110 => 00101 => 00110 :  6
 7: 00111 => 00100 => 00111 :  7
 8: 01000 => 01100 => 01000 :  8
 9: 01001 => 01101 => 01001 :  9
10: 01010 => 01111 => 01010 : 10
11: 01011 => 01110 => 01011 : 11
12: 01100 => 01010 => 01100 : 12
13: 01101 => 01011 => 01101 : 13
14: 01110 => 01001 => 01110 : 14
15: 01111 => 01000 => 01111 : 15
16: 10000 => 11000 => 10000 : 16
17: 10001 => 11001 => 10001 : 17
18: 10010 => 11011 => 10010 : 18
19: 10011 => 11010 => 10011 : 19
20: 10100 => 11110 => 10100 : 20
21: 10101 => 11111 => 10101 : 21
22: 10110 => 11101 => 10110 : 22
23: 10111 => 11100 => 10111 : 23
24: 11000 => 10100 => 11000 : 24
25: 11001 => 10101 => 11001 : 25
26: 11010 => 10111 => 11010 : 26
27: 11011 => 10110 => 11011 : 27
28: 11100 => 10010 => 11100 : 28
29: 11101 => 10011 => 11101 : 29
30: 11110 => 10001 => 11110 : 30
31: 11111 => 10000 => 11111 : 31

Ursala

<lang Ursala>#import std

  1. import nat

xor = ~&Y&& not ~&B # either and not both

btog = xor*+ zipp0@iitBX # map xor over the argument zipped with its shift

gtob = ~&y+ =><0> ^C/xor@lrhPX ~&r # fold xor over the next input with previous output

  1. show+

test = mat` * 2-$'01'***K7xSS pad0*K7 <.~&,btog,gtob+ btog>* iota32</lang>

Output:
00000 00000 00000
00001 00001 00001
00010 00011 00010
00011 00010 00011
00100 00110 00100
00101 00111 00101
00110 00101 00110
00111 00100 00111
01000 01100 01000
01001 01101 01001
01010 01111 01010
01011 01110 01011
01100 01010 01100
01101 01011 01101
01110 01001 01110
01111 01000 01111
10000 11000 10000
10001 11001 10001
10010 11011 10010
10011 11010 10011
10100 11110 10100
10101 11111 10101
10110 11101 10110
10111 11100 10111
11000 10100 11000
11001 10101 11001
11010 10111 11010
11011 10110 11011
11100 10010 11100
11101 10011 11101
11110 10001 11110
11111 10000 11111

VHDL

Combinatorial encoder: <lang VHDL>LIBRARY ieee; USE ieee.std_logic_1164.all;

entity b2g is

  port(  bin  : in  std_logic_vector (4 downto 0);
         gray : out std_logic_vector (4 downto 0)
       );

end b2g ;

architecture rtl of b2g is

 constant N : integer := bin'high;

begin

 gray <= bin(n) & ( bin(N-1 downto 0) xor bin(N downto 1));

end architecture rtl;</lang>

Combinatorial decoder: <lang VHDL>LIBRARY ieee; USE ieee.std_logic_1164.all;

entity g2b is

  port(  gray : in     std_logic_vector (4 downto 0);
         bin  : buffer std_logic_vector (4 downto 0)
       );

end g2b ;

architecture rtl of g2b is

 constant N : integer := bin'high;

begin

 bin(N) <= gray(N);
 gen_xor: for i in N-1 downto 0 generate
   bin(i) <= gray(i) xor bin(i+1);
 end generate;  

end architecture rtl;</lang>

XPL0

<lang XPL0>include c:\cxpl\codes; \intrinsic 'code' declarations

func Gray2Bin(N); \Convert N from Gray code to binary int N; int S; [S:= 1; repeat N:= N>>S | N;

       S:= S<<1;

until S=32; return N; ]; \Gray2Bin


func Bin2Gray(N); \Convert N from binary to Gray code int N; return N>>1 | N;


proc BinOut(N); \Output N in binary int N; int R; [R:= N&1; N:= N>>1; if N then BinOut(N); ChOut(0, R+^0); ]; \BinOut


int N, G; [for N:= 0 to 31 do

       [BinOut(N); ChOut(0, 9\tab\);
       G:= Bin2Gray(N);
       BinOut(G);  ChOut(0, 9\tab\);
       BinOut(Gray2Bin(G));  CrLf(0);
       ];

]</lang>

Output:
0       0       0
1       1       1
10      11      10
11      10      11
100     110     100
101     111     101
110     101     110
111     100     111
1000    1100    1000
1001    1101    1001
1010    1111    1010
1011    1110    1011
1100    1010    1100
1101    1011    1101
1110    1001    1110
1111    1000    1111
10000   11000   10000
10001   11001   10001
10010   11011   10010
10011   11010   10011
10100   11110   10100
10101   11111   10101
10110   11101   10110
10111   11100   10111
11000   10100   11000
11001   10101   11001
11010   10111   11010
11011   10110   11011
11100   10010   11100
11101   10011   11101
11110   10001   11110
11111   10000   11111

zkl

<lang zkl>fcn grayEncode(n){ n.bitXor(n.shiftRight(1)) } fcn grayDecode(g){ b:=g; while(g/=2){ b=b.bitXor(g) } b }</lang> <lang zkl>foreach n in ([0..31]){

  g:=grayEncode(n); b:=grayDecode(g);
  println("%2d(%05.2B) --> %2d(%05.2B) --> %2d(%05.2B)".fmt(n,n,g,g,b,b));

}</lang>

Output:
 0(00000) -->  0(00000) -->  0(00000)
 1(00001) -->  1(00001) -->  1(00001)
 2(00010) -->  3(00011) -->  2(00010)
 3(00011) -->  2(00010) -->  3(00011)
 4(00100) -->  6(00110) -->  4(00100)
 5(00101) -->  7(00111) -->  5(00101)
 6(00110) -->  5(00101) -->  6(00110)
 7(00111) -->  4(00100) -->  7(00111)
 8(01000) --> 12(01100) -->  8(01000)
 9(01001) --> 13(01101) -->  9(01001)
10(01010) --> 15(01111) --> 10(01010)
11(01011) --> 14(01110) --> 11(01011)
12(01100) --> 10(01010) --> 12(01100)
13(01101) --> 11(01011) --> 13(01101)
14(01110) -->  9(01001) --> 14(01110)
15(01111) -->  8(01000) --> 15(01111)
16(10000) --> 24(11000) --> 16(10000)
17(10001) --> 25(11001) --> 17(10001)
18(10010) --> 27(11011) --> 18(10010)
19(10011) --> 26(11010) --> 19(10011)
20(10100) --> 30(11110) --> 20(10100)
21(10101) --> 31(11111) --> 21(10101)
22(10110) --> 29(11101) --> 22(10110)
23(10111) --> 28(11100) --> 23(10111)
24(11000) --> 20(10100) --> 24(11000)
25(11001) --> 21(10101) --> 25(11001)
26(11010) --> 23(10111) --> 26(11010)
27(11011) --> 22(10110) --> 27(11011)
28(11100) --> 18(10010) --> 28(11100)
29(11101) --> 19(10011) --> 29(11101)
30(11110) --> 17(10001) --> 30(11110)
31(11111) --> 16(10000) --> 31(11111)