Gray code: Difference between revisions
(adding fortran 77) |
(→{{header|Fortran}}: clear beginning of string in case it's larger than binary representation) |
||
Line 590: | Line 590: | ||
END IF |
END IF |
||
10 CONTINUE |
10 CONTINUE |
||
DO 20 I=1,L-K |
|||
S(I:I)=' ' |
|||
20 CONTINUE |
|||
END</lang> |
END</lang> |
||
Line 624: | Line 627: | ||
30 : 11110 => 10001 => 11110 : 30 |
30 : 11110 => 10001 => 11110 : 30 |
||
31 : 11111 => 10000 => 11111 : 31</pre> |
31 : 11111 => 10000 => 11111 : 31</pre> |
||
=={{header|J}}== |
=={{header|J}}== |
||
Revision as of 11:37, 1 June 2011
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
- Converting Between Gray and Binary Codes. It includes step-by-step animations.
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
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
<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>
- include <iostream>
- 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
C#
<lang csharp>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
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) {
enum T MSB = (cast(T)1) << (T.sizeof * 8 - 1);
auto res = (n & MSB) ; foreach (bit; 1 .. T.sizeof * 8) res += ( n ^ (res >>> 1) ) & (MSB >>> bit) ; 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> A succinct functional-style generator: <lang d>import std.stdio, std.algorithm, std.range;
string[] g(uint n) {
return n ? array(map!q{'0' ~ a}(g(n - 1))) ~ array(map!q{'1' ~ a}(retro(g(n - 1)))) : [""];
}
void main() {
writeln(g(4));
}</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 IF(BTEST(N,I)) THEN S(L-I:L-I)='1' ELSE S(L-I:L-I)='0' END IF 10 CONTINUE DO 20 I=1,L-K S(I:I)=' ' 20 CONTINUE 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
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
<lang java>public class Gray { public static long grayEncode(long n){ return n ^ (n >>> 1); }
public static long grayDecode(long n) { long i = 1 << 8 * 64 - 2; //long is 64-bit long p, b = p = n & i;
while ((i >>= 1) > 0) b |= p = n & i ^ p >> 1; return b; }
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> This decoding function should work for gray codes of any size:
<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>
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
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 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>
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).
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>
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