Gray code
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
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.
[edit] 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).
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;
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
[edit] AutoHotkey
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
- 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
[edit] BBC BASIC
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%
[edit] 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.
scale = 0 /* to use integer division */Output:
/* 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
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
[edit] 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;
}
Demonstration code:
#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;
}
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
[edit] C++
#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";
}
}
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
[edit] C#
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))));
}
}
}
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
[edit] 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)
[edit] Common 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)))
[edit] D
import std.stdio;
T enGray(T)(in T n) pure nothrow {
return n ^ (n >>> 1);
}
T deGray(T)(in T n) pure nothrow {
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) {
immutable encoded = enGray(i);
writefln("%2d: %5b ==> %5b : %2d",
i, i, encoded, deGray(encoded));
}
}
- 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
[edit] 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.
import std.stdio, std.conv, std.algorithm;
T[] gray(int N : 1, T)() { return [to!T(0), 1]; }
/// recursively generate gray encoding mapping table
T[] gray(int N, T)() pure nothrow {
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]];
// append inversed gray encoding mapping
foreach (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) {
// generated at compile time
enum dict = grayDict!(N, T)();
return dict[mode][n];
}
void main() {
foreach (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);
}
}
[edit] Short Functional-Style Generator
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() {
writeln(g(4));
}
- Output:
["0000", "0001", "0011", "0010", "0110", "0111", "0101", "0100", "1100", "1101", "1111", "1110", "1010", "1011", "1001", "1000"]
[edit] 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.
[edit] DWScript
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;
[edit] 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).
Demonstration code:
-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).
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
[edit] 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
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
[edit] Factor
Translation of C.
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
Running above code prints:
{ -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 }
[edit] 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 ;
[edit] Fortran
Using MIL-STD-1753 extensions in Fortran 77, and formulas found at OEIS for direct and inverse Gray code :
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
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
[edit] Go
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.
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)
}
}
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
[edit] Groovy
Solution:
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)
}
Test:
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()
}
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
[edit] Haskell
This being Haskell, the conversion to binary and the printout take more effort than the conversion to and from gray code. The binary conversion function num2bin has an additional width argument to force zero padding, which looks nicer.
module Main where
main = mapM_ (putStrLn . flip grayconvstr 5) [0..31]
-- Convert number to bit list, MSB first. Second argument is minimum width.
num2bin :: (Integral t) => t -> t -> [t]
num2bin n w = num2bin' n w [] where
num2bin' n w acc | n <= 0 && w <= 0 = acc
| otherwise = num2bin' m (w-1) (b:acc)
where (m, b) = divMod n 2
xor2 :: (Integral t) => t -> t -> t
xor2 x y = (x + y) `mod` 2
bin2gray :: (Integral t) => [t] -> [t]
bin2gray [] = []
bin2gray (x:xs) = x : zipWith xor2 xs (x:xs)
gray2bin :: (Integral t) => [t] -> [t]
gray2bin [] = []
gray2bin (x:xs) = bin
where bin = x : zipWith xor2 xs bin -- note the recursive definition
-- Prettyprinting, since it is in the task description...
grayconvstr :: (Integral t, Show t) => t -> t -> String
grayconvstr n w = (show n) ++ ": " ++ (show b) ++ " => " ++ (show g) ++ " => " ++ (show u)
where
b = num2bin n w
g = bin2gray b
u = gray2bin g
[edit] J
G2B is an invertible function which will translate Gray code to Binary:
G2B=: ~:/\&.|:
Thus G2B inv will translate binary to Gray code.
Required example:
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 |
+--+---------+----------+----------------+
[edit] 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)));
}
}
}
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:
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;
}
This decoding function should work for gray codes of any size:
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);
}
[edit] K
Binary to Gray code
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}
Gray code to binary
"Accumulated xor"
g2b:xor\
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
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)
As a function (*| takes the last result)
g2b1:*|{gray x}\
Iterative version with "do"
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}
Presentation
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
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
[edit] Liberty BASIC
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
[edit] 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
Demonstration code, including formatters:
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
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
[edit] Lua
This code uses the Lua BitOp module. Designed to be a module named gray.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
Demonstration code:
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
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
[edit] Mathematica
graycode[n_]:=BitXor[n,BitShiftRight[n]]
graydecode[n_]:=Fold[BitXor,0,FixedPointList[BitShiftRight,n]]
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}
[edit] 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
[edit] 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).
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)))
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
[edit] Pascal
See Delphi
[edit] 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) ) ) ) ) )
Test:
(prinl " Binary Gray Decoded")
(for I (range 0 31)
(let G (grayEncode I)
(tab (4 9 9 9) I (bin I) G (grayDecode G)) ) )
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
[edit] 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);
}
[edit] Perl 6
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;
}
This version is a translation of the Haskell solution, and produces the same output as the first Perl 6 solution.
multi bin_to_gray ( [] ) { [] }Output:
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;
}
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).
[edit] 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
[edit] 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
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
[edit] Python
This example works with lists of discrete binary digits.
- First some int<>bin conversion routines
>>> 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
- Now the bin<>gray converters.
These follow closely the methods in the animation seen here: Converting Between Gray and Binary Codes.
>>> 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
- Sample output
>>> 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
>>>
[edit] Ruby
Integer#from_gray has recursion so it can use each bit of the answer to compute the next bit.
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
[edit] 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).
def encode(n: Int) = (n ^ (n >>> 1)).toBinaryStringOutput:
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)))
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:
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)))
}
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
[edit] 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
}
}
Demonstrating:
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]
}
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
[edit] Ursala
#import std
#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
#show+
test = mat` * 2-$'01'***K7xSS pad0*K7 <.~&,btog,gtob+ btog>* iota32
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
[edit] 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);
];
]
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
Categories:
- Programming Tasks
- Solutions by Programming Task
- Ada
- AutoHotkey
- BBC BASIC
- Bc
- C
- C++
- C sharp
- CoffeeScript
- Common Lisp
- D
- Delphi
- DWScript
- Erlang
- Euphoria
- Factor
- Forth
- Fortran
- Go
- Groovy
- Haskell
- J
- Java
- Examples needing attention
- K
- Liberty BASIC
- Logo
- Lua
- Mathematica
- OCaml
- PARI/GP
- Pascal
- PicoLisp
- Perl
- Perl 6
- PowerBASIC
- PureBasic
- Python
- Ruby
- Scala
- Tcl
- Ursala
- XPL0
