Gray code

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).

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]

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 i = 1 << 8 * sizeof(int) - 2;
   int p, b = p = n & i;

   while (i >>= 1)

b |= p = n & i ^ p >> 1;

   return b;

}</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>#include <bitset>

1. include <iostream>
2. include <string>

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);
       uint32_t b = gray_decode(g);

       std::cout << n << "\t" << to_binary(n) << "\t" << to_binary(g) << "\t" << b << "\n";
   }

}</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

D

<lang d>import std.stdio;

nothrow pure T enGray(T)(const T n) {

   return n ^ (n >>> 1);

}

nothrow pure T deGray(T)(const T n) {

   if (n == 0)
       return 0;

   enum T MSB = (cast(T)1) << (T.sizeof * 8 - 1);

   static nothrow pure bool bitSet(T m, uint pos) {
       return (m & (MSB >>> pos)) != 0;
   }
   // bit pos count from MSB/left

   T posFromMSB;
   while (!bitSet(n, posFromMSB))
       posFromMSB++;

   auto res = MSB >>> posFromMSB;
   foreach (bitPos; posFromMSB + 1 .. T.sizeof * 8)
       if (bitSet(n, bitPos) != bitSet(res, bitPos - 1))
           res += MSB >>> bitPos;
   return res;

}

void main() {

   writeln("num  bits    encoded  decoded");
   foreach (i; 0 .. 32) {
       auto encoded = enGray(i);
       writefln("%2d: %5b ==> %5b : %2d",
                i, i, encoded, deGray(encoded));
   }

}</lang> Output:

num  bits    encoded  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

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. <lang d>import std.stdio, std.conv, std.algorithm ;

T[] Gray(int N : 1, T)() { return [to!T(0), 1] ; }

T[] Gray(int N, T)() { // recursively generate gray encoding mapping table

   assert(N <= T.sizeof*8, "N exceed number of bit of T") ;
   enum T M = to!T(2)^^(N-1) ;
   T[] g = Gray!(N - 1, T);
   foreach(i;0..M)
       g ~= M + g[M - i - 1] ;
   return g ;

}

T[][] GrayDict(int N, T)() {

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

}

enum { Encode = 0 , Decode = 1 } ;

T gray(int N, T)(T n, int Mode = Encode) {

   enum Dict = GrayDict!(N, T) ;  // generated at compile time
   return Dict[Mode][n] ;

}

void main() {

   foreach(i; 0..32) {
       auto encoded = gray!(5)(i, Encode) ;
       auto decoded = gray!(5)(encoded, Decode) ;
       writefln("%2d: %5b => %5b : %2d", i, i, encoded, decoded) ;
   } // checked correct ouput

}</lang>

J

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

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

Thus:

<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

This example encodes using bitwise operations and decodes using Strings. <lang java>public class Gray { public static long grayEncode(long n){ return n ^ (n >>> 1); }

public static long grayDecode(long n){ String nBits = Long.toBinaryString(n); 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 Long.valueOf(result, 2); }

public static void main(String[] args){ System.out.println("i\tBinary\tGray\tDecoded"); for(int i = 0; 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
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>

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

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: <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>

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>

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