Gray code
Pete: Add Limbo
{{task}}[[wp:Gray code|Gray code]] is a form of binary encoding where transitions between consecutive numbers differ by only one bit. This is a useful encoding for reducing hardware data hazards with values that change rapidly and/or connect to slower hardware as inputs. It is also useful for generating inputs for [[wp:Karnaugh map|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):
Or:
Decoding (MSB is bit 0, b is binary, g is Gray code):
;Reference
* [http://www.wisc-online.com/Objects/ViewObject.aspx?ID=IAU8307 Converting Between Gray and Binary Codes]. It includes step-by-step animations.
=={{header|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
{{out}}
=={{header|Aime}}==
{{trans|C}}
integer
gray_encode(integer n)
{
return n ^ (n >> 1);
}
integer
gray_decode(integer n)
{
integer p;
p = n;
while (n >>= 1) {
p ^= n;
}
return p;
}
Demonstration code:
integer
main(void)
{
integer i, g, b;
i = 0;
while (i < 32) {
g = gray_encode(i);
b = gray_decode(g);
o_winteger(2, i);
o_text(": ");
o_fxinteger(5, 2, i);
o_text(" => ");
o_fxinteger(5, 2, g);
o_text(" => ");
o_fxinteger(5, 2, b);
o_text(": ");
o_winteger(2, b);
o_byte('\n');
i += 1;
}
return 0;
}
{{out}}
=={{header|ALGOL 68}}==
In Algol 68 the BITS mode is specifically designed for manipulating machine words as a row of bits so it is natural to treat Gray encoded integers as values of MODE BITS. The standard operator BIN (INT) : BITS converts an INT value to a BITS value. The ABS (BITS) : INT operator performs the reverse conversion, though it has not been needed for this task. It is also natural in the language for simple operations on values to be implemented as operators, rather than as functions, as in the program below.
BEGIN
OP GRAY = (BITS b) BITS : b XOR (b SHR 1); CO Convert to Gray code CO
OP YARG = (BITS g) BITS : CO Convert from Gray code CO
BEGIN
BITS b := g, mask := g SHR 1;
WHILE mask /= 2r0 DO b := b XOR mask; mask := mask SHR 1 OD;
b
END;
FOR i FROM 0 TO 31 DO
printf (($zd, ": ", 2(2r5d, " >= "), 2r5dl$, i, BIN i, GRAY BIN i, YARG GRAY BIN i))
OD
END
{{out}}
=={{header|APL}}==
Generate the complete N-bit Gray sequence as a matrix:[http://ngn.github.io/apl/web/index.html#code=N%u21905%0A%28%7B%280%2C%u2375%29%u236A1%2C%u2296%u2375%7D%u2363N%29%281%200%u2374%u236C%29,run=1 run]
N←5
({(0,⍵)⍪1,⊖⍵}⍣N)(1 0⍴⍬)
{{out}}
Encode and decode an individual integer:[http://ngn.github.io/apl/web/index.html#code=N%u21905%0AgrayEncode%u2190%7Ba%u2260N%u2191%280%2Ca%u2190%28N%u23742%29%u22A4%u2375%29%7D%0AgrayDecode%u2190%7B2%u22A5%u2260%u233FN%20N%u2191N%282%D7N%29%u2374%u2375%2C0%2CN%u23740%7D%0A%0AgrayEncode%2019,run=1 run]
N←5
grayEncode←{a≠N↑(0,a←(N⍴2)⊤⍵)}
grayDecode←{2⊥≠⌿N N↑N(2×N)⍴⍵,0,N⍴0}
grayEncode 19
{{out}}
=={{header|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
{{out}}
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
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%
=={{header|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 */
/* 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
{{out}}
=={{header|C}}==
{{trans|Tcl}}
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
/* 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;
}
{{out}}
=={{header|C++}}==
#include
#include
#include
#include
uint32_t gray_encode(uint32_t b)
{
return b ^ (b >> 1);
}
uint32_t gray_decode(uint32_t g)
{
for (uint32_t bit = 1U << 31; bit > 1; bit >>= 1)
{
if (g & bit) g ^= bit >> 1;
}
return g;
}
std::string to_binary(int value) // utility function
{
const std::bitset<32> bs(value);
const std::string str(bs.to_string());
const size_t pos(str.find('1'));
return pos == std::string::npos ? "0" : str.substr(pos);
}
int main()
{
std::cout << "Number\tBinary\tGray\tDecoded\n";
for (uint32_t n = 0; n < 32; ++n)
{
uint32_t g = gray_encode(n);
assert(gray_decode(g) == n);
std::cout << n << "\t" << to_binary(n) << "\t" << to_binary(g) << "\t" << g << "\n";
}
}
{{out}}
=={{header|C sharp}}==
using System;
public class Gray {
public static ulong grayEncode(ulong n) {
return n^(n>>1);
}
public static ulong grayDecode(ulong n) {
ulong i=1<<8*64-2; //long is 64-bit
ulong p, b=p=n&i;
while((i>>=1)>0)
b|=p=n&i^p>>1;
return b;
}
public static void Main(string[] args) {
Console.WriteLine("Number\tBinary\tGray\tDecoded");
for(ulong i=0;i<32;i++) {
Console.WriteLine(string.Format("{0}\t{1}\t{2}\t{3}", i, Convert.ToString((long)i, 2), Convert.ToString((long)grayEncode(i), 2), grayDecode(grayEncode(i))));
}
}
}
{{out}}
=={{header|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)
=={{header|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)))
{{out}}
=={{header|Component Pascal}}==
BlackBox Component Builder
MODULE GrayCodes;
IMPORT StdLog,SYSTEM;
PROCEDURE Encode*(i: INTEGER; OUT x: INTEGER);
VAR
j: INTEGER;
s,r: SET;
BEGIN
s := BITS(i);j := MAX(SET);
WHILE (j >= 0) & ~(j IN s) DO DEC(j) END;
r := {};IF j >= 0 THEN INCL(r,j) END;
WHILE j > 0 DO
IF ((j IN s) & ~(j - 1 IN s)) OR (~(j IN s) & (j - 1 IN s)) THEN INCL(r,j-1) END;
DEC(j)
END;
x := SYSTEM.VAL(INTEGER,r)
END Encode;
PROCEDURE Decode*(x: INTEGER; OUT i: INTEGER);
VAR
j: INTEGER;
s,r: SET;
BEGIN
s := BITS(x);r:={};j := MAX(SET);
WHILE (j >= 0) & ~(j IN s) DO DEC(j) END;
IF j >= 0 THEN INCL(r,j) END;
WHILE j > 0 DO
IF ((j IN r) & ~(j - 1 IN s)) OR (~(j IN r) & (j - 1 IN s)) THEN INCL(r,j-1) END;
DEC(j)
END;
i := SYSTEM.VAL(INTEGER,r);
END Decode;
PROCEDURE Do*;
VAR
grayCode,binCode: INTEGER;
i: INTEGER;
BEGIN
StdLog.String(" i ");StdLog.String(" bin code ");StdLog.String(" gray code ");StdLog.Ln;
StdLog.String("---");StdLog.String(" ----------------");StdLog.String(" ---------------");StdLog.Ln;
FOR i := 0 TO 32 DO;
Encode(i,grayCode);Decode(grayCode,binCode);
StdLog.IntForm(i,10,3,' ',FALSE);
StdLog.IntForm(binCode,2,16,' ',TRUE);
StdLog.IntForm(grayCode,2,16,' ',TRUE);
StdLog.Ln;
END
END Do;
END GrayCodes.
Execute: ^QGrayCodes.Do
{{out}}
=={{header|D}}==
uint grayEncode(in uint n) pure nothrow @nogc {
return n ^ (n >> 1);
}
uint grayDecode(uint n) pure nothrow @nogc {
auto p = n;
while (n >>= 1)
p ^= n;
return p;
}
void main() {
import std.stdio;
" N N2 enc dec2 dec".writeln;
foreach (immutable n; 0 .. 32) {
immutable g = n.grayEncode;
immutable d = g.grayDecode;
writefln("%2d: %5b => %5b => %5b: %2d", n, n, g, d, d);
assert(d == n);
}
}
{{out}}
===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.algorithm;
T[] gray(int N : 1, T)() pure nothrow {
return [T(0), 1];
}
/// Recursively generate gray encoding mapping table.
T[] gray(int N, T)() pure nothrow if (N <= T.sizeof * 8) {
enum T M = T(2) ^^ (N - 1);
T[] g = gray!(N - 1, T)();
foreach (immutable i; 0 .. M)
g ~= M + g[M - i - 1];
return g;
}
T[][] grayDict(int N, T)() pure nothrow {
T[][] dict = [gray!(N, T)(), [0]];
// Append inversed gray encoding mapping.
foreach (immutable i; 1 .. dict[0].length)
dict[1] ~= countUntil(dict[0], i);
return dict;
}
enum M { Encode = 0, Decode = 1 }
T gray(int N, T)(in T n, in int mode=M.Encode) pure nothrow {
// Generated at compile time.
enum dict = grayDict!(N, T)();
return dict[mode][n];
}
void main() {
foreach (immutable i; 0 .. 32) {
immutable encoded = gray!(5)(i, M.Encode);
immutable decoded = gray!(5)(encoded, M.Decode);
writefln("%2d: %5b => %5b : %2d", i, i, encoded, decoded);
}
}
===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() {
4.g.writeln;
}
{{out}}
=={{header|Delphi}}==
{{trans|DWScript}}
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.
=={{header|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;
=={{header|Elixir}}==
{{trans|Erlang}}
defmodule Gray_code do
use Bitwise
def encode(n), do: bxor(n, bsr(n,1))
def decode(g), do: decode(g,0)
def decode(0,n), do: n
def decode(g,n), do: decode(bsr(g,1), bxor(g,n))
end
Enum.each(0..31, fn(n) ->
g = Gray_code.encode(n)
d = Gray_code.decode(g)
:io.fwrite("~2B : ~5.2.0B : ~5.2.0B : ~5.2.0B : ~2B~n", [n, n, g, d, d])
end)
output is the same as "Erlang".
=={{header|Erlang}}==
{{trans|Euphoria}}
-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).
{{out}}
=={{header|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
{{out}}
=={{header|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 }
=={{header|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 ;
=={{header|Fortran}}==
Using [http://www.everyspec.com/MIL-STD/MIL-STD+(1700+-+1799)/download.php?spec=MIL-STD-1753.011044.PDF MIL-STD-1753] extensions in '''Fortran 77''', and formulas found at OEIS for [http://oeis.org/A003188 direct] and [http://oeis.org/A006068 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
=={{header|Frink}}==
Frink has built-in functions to convert to and from binary reflected Gray code.
for i=0 to 31
{
gray = binaryToGray[i]
back = grayToBinary[gray]
println[(i->binary) + "\t" + (gray->binary) + "\t" + (back->binary)]
}
=={{header|Go}}==
{{trans|Euphoria}}
Binary reflected, as described in the task. Reading down through the solutions, the Euphoria decode algorithm caught my eye as being concise and easy to read.
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)
}
}
{{out}}
=={{header|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:
=={{header|Haskell}}==
For zero padding, replace the %5s specifiers in the format string with %05s.
import Data.Bits
import Data.Char
import Numeric
import Control.Monad
import Text.Printf
grayToBin :: (Integral t, Bits t) => t -> t
grayToBin 0 = 0
grayToBin g = g `xor` (grayToBin $ g `shiftR` 1)
binToGray :: (Integral t, Bits t) => t -> t
binToGray b = b `xor` (b `shiftR` 1)
showBinary :: (Integral t, Show t) => t -> String
showBinary n = showIntAtBase 2 intToDigit n ""
showGrayCode :: (Integral t, Bits t, PrintfArg t, Show t) => t -> IO ()
showGrayCode num = do
let bin = showBinary num
let gray = showBinary (binToGray num)
printf "int: %2d -> bin: %5s -> gray: %5s\n" num bin gray
main = forM_ [0..31::Int] showGrayCode
=={{header|Icon}} and {{header|Unicon}}==
The following works in both languages:
link bitint
procedure main()
every write(right(i := 0 to 10,4),":",right(int2bit(i),10)," -> ",
right(g := gEncode(i),10)," -> ",
right(b := gDecode(g),10)," -> ",
right(bit2int(b),10))
end
procedure gEncode(b)
return int2bit(ixor(b, ishift(b,-1)))
end
procedure gDecode(g)
b := g[1]
every i := 2 to *g do b ||:= if g[i] == b[i-1] then "0" else "1"
return b
end
Sample run:
=={{header|J}}==
G2B=: ~:/\&.|:
Thus
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 |
+--+---------+----------+----------------+
=={{header|Java}}==
{{trans|C}}
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)));
}
}
}
{{out}}
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:
{{untested}}
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);
}
=={{header|Julia}}==
{{trans|C}}
gray_encode(n) = n $ (n >> 1)
function gray_decode(n)
p = n
while (n >>= 1) != 0
p $= n
end
return p
end
Note that these functions work for any integer type, including arbitrary-precision integers (the built-in
=={{header|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
{{out}}
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
=={{header|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
=={{header|Limbo}}==
{{trans|Go}}
implement Gray;
include "sys.m"; sys: Sys;
print: import sys;
include "draw.m";
Gray: module {
init: fn(nil: ref Draw->Context, args: list of string);
# Export gray and grayinv so that this module can be used as either a
# standalone program or as a library:
gray: fn(n: int): int;
grayinv: fn(n: int): int;
};
init(nil: ref Draw->Context, args: list of string)
{
sys = load Sys Sys->PATH;
for(i := 0; i < 32; i++) {
g := gray(i);
f := grayinv(g);
print("%2d %5s %2d %5s %5s %2d\n", i, binstr(i), g, binstr(g), binstr(f), f);
}
}
gray(n: int): int
{
return n ^ (n >> 1);
}
grayinv(n: int): int
{
r := 0;
while(n) {
r ^= n;
n >>= 1;
}
return r;
}
binstr(n: int): string
{
if(!n)
return "0";
s := "";
while(n) {
s = (string (n&1)) + s;
n >>= 1;
}
return s;
}
{{out}}
=={{header|Logo}}==
{{trans|Euphoria}}
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
{{out}}
=={{header|Lua}}==
{{trans|Euphoria}}
This code uses the [http://bitop.luajit.org/index.html 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
{{out}}
=={{header|Mathematica}}==
graycode[n_]:=BitXor[n,BitShiftRight[n]]
graydecode[n_]:=Fold[BitXor,0,FixedPointList[BitShiftRight,n]]
{{out}}
=={{header|MATLAB}}==
%% Gray Code Generator
% this script generates gray codes of n bits
% total 2^n -1 continuous gray codes will be generated.
% this code follows a recursive approach. therefore,
% it can be slow for large n
clear all;
clc;
bits = input('Enter the number of bits: ');
if (bits<1)
disp('Sorry, number of bits should be positive');
elseif (mod(bits,1)~=0)
disp('Sorry, number of bits can only be positive integers');
else
initial_container = [0;1];
if bits == 1
result = initial_container;
else
previous_container = initial_container;
for i=2:bits
new_gray_container = zeros(2^i,i);
new_gray_container(1:(2^i)/2,1) = 0;
new_gray_container(((2^i)/2)+1:end,1) = 1;
for j = 1:(2^i)/2
new_gray_container(j,2:end) = previous_container(j,:);
end
for j = ((2^i)/2)+1:2^i
new_gray_container(j,2:end) = previous_container((2^i)+1-j,:);
end
previous_container = new_gray_container;
end
result = previous_container;
end
fprintf('Gray code of %d bits',bits);
disp(' ');
disp(result);
end
{{out}}
=={{header|Mercury}}==
The following is a full implementation of Gray encoding and decoding.
It publicly exposes the gray type along with the following
value conversion functions:
* gray.from_int/1
* gray.to_int/1
The from_int/1 and to_int/1 functions are ''value'' conversion functions. from_int/1 converts an int value into the enclosing gray type. to_int/1 converts a gray value back into a regular int type.
The additional gray.coerce/2 predicate converts the ''representation'' underlying a gray value into an int value or vice versa (it is moded in both directions). For type safety reasons we do not wish to generally expose the underlying representation, but for some purposes, most notably I/O or storage or their ilk we have to break the type safety. The coerce/2 predicate is used for this purpose.
:- module gray.
:- interface.
:- import_module int.
:- type gray.
% VALUE conversion functions
:- func gray.from_int(int) = gray.
:- func gray.to_int(gray) = int.
% REPRESENTATION conversion predicate
:- pred gray.coerce(gray, int).
:- mode gray.coerce(in, out) is det.
:- mode gray.coerce(out, in) is det.
:- implementation.
:- import_module list.
:- type gray
---> gray(int).
gray.from_int(X) = gray(X `xor` (X >> 1)).
gray.to_int(gray(G)) = (G > 0 -> G `xor` gray.to_int(gray(G >> 1))
; G).
gray.coerce(gray(I), I).
:- end_module gray.
The following program tests the above code:
:- module gray_test.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module gray.
:- import_module int, list, string.
:- pred check_conversion(list(int)::in, list(gray)::out) is semidet.
:- pred display_lists(list(int)::in, list(gray)::in, io::di, io::uo) is det.
:- pred display_record(int::in, gray::in, io::di, io::uo) is det.
main(!IO) :-
Numbers = 0..31,
( check_conversion(Numbers, Grays) ->
io.format("%8s %8s %8s\n", [s("Number"), s("Binary"), s("Gray")], !IO),
io.format("%8s %8s %8s\n", [s("------"), s("------"), s("----")], !IO),
display_lists(Numbers, Grays, !IO)
; io.write("Either conversion or back-conversion failed.\n", !IO)).
check_conversion(Numbers, Grays) :-
Grays = list.map(gray.from_int, Numbers),
Numbers = list.map(gray.to_int, Grays).
display_lists(Numbers, Grays, !IO) :-
list.foldl_corresponding(display_record, Numbers, Grays, !IO).
display_record(Number, Gray, !IO) :-
gray.coerce(Gray, GrayRep),
NumBin = string.int_to_base_string(Number, 2),
GrayBin = string.int_to_base_string(GrayRep, 2),
io.format("%8d %8s %8s\n", [i(Number), s(NumBin), s(GrayBin)], !IO).
:- end_module gray_test.
The main/2 predicate generates a list of numbers from 0 to 31 inclusive and then checks that conversion is working properly.
It does so by calling the check_conversion/2 predicate with the
list of numbers as an input and the list of Gray-encoded numbers as an output.
Note the absence of the usual kinds of testing you'd see in most programming languages.
gray.from_int/1 is mapped over the Numbers (input) list and placed into the Grays (output) list.
Then gray.to_int is mapped over the Grays list and placed into the Numbers (input) list.
Or so it would seem to those used to imperative or functional languages.
In reality what's happening is [https://en.wikipedia.org/wiki/Unification_%28computer_science%29 unification].
Since the Grays list is not yet populated, unification is very similar notionally to assignment in other languages.
Numbers, however, '''is''' instantiated and thus unification is more like testing for equality.
If the conversions check out, main/2 prints off some headers and then displays the lists. Here we're cluttering up the namespace of the gray_test module a little by providing a one-line predicate. While it is true that we ''could'' just take the contents of that predicate and place it inline, we've chosen not to do that because the name display_lists communicates more effectively what we intend.
The compiler is smart enough to automatically inline that predicate call so there's no efficiency reason not to do it.
However we choose to do that, the result is the same: repeated calls to display_record/4. In that predicate the aforementioned coerce/2 predicate extracts, in this case, the Gray value's representation.
This value and the corresponding int value are then converted into a string showing the base-2 representation of their values.
io.format/4 then prints them off in a nice format.
The output of the program looks like this:
Number Binary Gray
------ ------ ----
0 0 0
1 1 1
2 10 11
3 11 10
4 100 110
5 101 111
6 110 101
7 111 100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
16 10000 11000
17 10001 11001
18 10010 11011
19 10011 11010
20 10100 11110
21 10101 11111
22 10110 11101
23 10111 11100
24 11000 10100
25 11001 10101
26 11010 10111
27 11011 10110
28 11100 10010
29 11101 10011
30 11110 10001
31 11111 10000
=={{header|Nim}}==
{{trans|C}}
proc grayEncode(n): auto =
n xor (n shr 1)
proc grayDecode(n): auto =
result = n
var t = n
while t > 0:
t = t shr 1
result = result xor t
Demonstration code:
import strutils
for i in 0 .. 32:
echo i, " => ", toBin(grayEncode(i), 6), " => ", grayDecode(grayEncode(i))
{{out}}
=={{header|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
=={{header|PARI/GP}}==
This code may have exposed a bug in PARI 2.4.4:
As a workaround I used a closure:
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)))
{{out}}
=={{header|Pascal}}==
See [[Gray_code#Delphi | Delphi]]
=={{header|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)) ) )
{{out}}
=={{header|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);
}
=={{header|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.
{{trans|Haskell}}
multi bin_to_gray ( [] ) { [] }
multi bin_to_gray ( [$head, *@tail] ) {
return [ $head, ( @tail Z+^ ($head, @tail) ) ];
}
multi gray_to_bin ( [] ) { [] }
multi gray_to_bin ( [$head, *@tail] ) {
my @bin := $head, (@tail Z+^ @bin);
return @bin.flat;
}
for ^32 -> $n {
my @b = $n.fmt('%b').comb;
my $g = bin_to_gray(@b);
my $d = gray_to_bin($g);
printf "%2d: %5s => %5s => %5s: %2d\n",
$n, @b.join, $g.join, $d.join, :2($d.join);
die if :2($d.join) != $n;
}
{{out}}
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).
=={{header|PHP}}==
/**
* @author Elad Yosifon
*/
/**
* @param int $binary
* @return int
*/
function gray_encode($binary){
return $binary ^ ($binary >> 1);
}
/**
* @param int $gray
* @return int
*/
function gray_decode($gray){
$binary = $gray;
while($gray >>= 1) $binary ^= $gray;
return $binary;
}
for($i=0;$i<32;$i++){
$gray_encoded = gray_encode($i);
printf("%2d : %05b => %05b => %05b : %2d \n",$i, $i, $gray_encoded, $gray_encoded, gray_decode($gray_encoded));
}
{{out}}
=={{header|PL/I}}==
(stringrange, stringsize):
Gray_code: procedure options (main); /* 15 November 2013 */
declare (bin(0:31), g(0:31), b2(0:31)) bit (5);
declare (c, carry) bit (1);
declare (i, j) fixed binary (7);
bin(0) = '00000'b;
do i = 0 to 31;
if i > 0 then
do;
carry = '1'b;
bin(i) = bin(i-1);
do j = 5 to 1 by -1;
c = substr(bin(i), j, 1) & carry;
substr(bin(i), j, 1) = substr(bin(i), j, 1) ^ carry;
carry = c;
end;
end;
g(i) = bin(i) ^ '0'b || substr(bin(i), 1, 4);
end;
do i = 0 to 31;
substr(b2(i), 1, 1) = substr(g(i), 1, 1);
do j = 2 to 5;
substr(b2(i), j, 1) = substr(g(i), j, 1) ^ substr(bin(i), j-1, 1);
end;
end;
do i = 0 to 31;
put skip edit (i, bin(i), g(i), b2(i)) (f(2), 3(x(1), b));
end;
end Gray_code;
=={{header|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
=={{header|Prolog}}==
=== Codecs ===
The encoding and decoding predicates are simple and will work
with any Prolog that supports bitwise integer operations.
{{works with|SWI Prolog}}
{{works with|YAP}}
to_gray(N, G) :-
N0 is N >> 1,
G is N xor N0.
from_gray(G, N) :-
( G > 0
-> S is G >> 1,
from_gray(S, N0),
N is G xor N0
; N is G ).
=== Test Code ===
A quick driver around this to test it will prove the point.
(This test script uses features not available in every Prolog implementation.)
{{works with|SWI Prolog}}
{{works with|YAP}}
:- use_module(library(apply)).
to_gray(N, G) :-
N0 is N >> 1,
G is N xor N0.
from_gray(G, N) :-
( G > 0
-> S is G >> 1,
from_gray(S, N0),
N is G xor N0
; N is G ).
make_num(In, Out) :-
atom_to_term(In, Out, _),
integer(Out).
write_record(Number, Gray, Decoded) :-
format('~w~10|~2r~10+~2r~10+~2r~10+~w~n',
[Number, Number, Gray, Decoded, Decoded]).
go :-
setof(N, between(0, 31, N), Numbers),
maplist(to_gray, Numbers, Grays),
maplist(from_gray, Grays, Decodeds),
format('~w~10|~w~10+~w~10+~w~10+~w~n',
['Number', 'Binary', 'Gray', 'Decoded', 'Number']),
format('~w~10|~w~10+~w~10+~w~10+~w~n',
['------', '------', '----', '-------', '------']),
maplist(write_record, Numbers, Grays, Decodeds).
go :- halt(1).
{{out}}
Putting all of this in a file, we execute it, getting the following results:
=={{header|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
{{out}}
=={{header|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: [http://www.wisc-online.com/Objects/ViewObject.aspx?ID=IAU8307 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
>>>
=={{header|R}}==
GrayEncode <- function(binary) {
gray <- substr(binary,1,1)
repeat {
if (substr(binary,1,1) != substr(binary,2,2)) gray <- paste(gray,"1",sep="")
else gray <- paste(gray,"0",sep="")
binary <- substr(binary,2,nchar(binary))
if (nchar(binary) <=1) {
break
}
}
return (gray)
}
GrayDecode <- function(gray) {
binary <- substr(gray,1,1)
repeat {
if (substr(binary,nchar(binary),nchar(binary)) != substr(gray,2,2)) binary <- paste(binary ,"1",sep="")
else binary <- paste(binary ,"0",sep="")
gray <- substr(gray,2,nchar(gray))
if (nchar(gray) <=1) {
break
}
}
return (binary)
}
=={{header|Racket}}==
#lang racket
(define (gray-encode n) (bitwise-xor n (arithmetic-shift n -1)))
(define (gray-decode n)
(letrec ([loop (lambda(g bits)
(if (> bits 0)
(loop (bitwise-xor g bits) (arithmetic-shift bits -1))
g))])
(loop 0 n)))
(define (to-bin n) (format "~b" n))
(define (show-table)
(for ([i (in-range 1 32)])
(printf "~a | ~a | ~a ~n"
(~r i #:min-width 2 #:pad-string "0")
(~a (to-bin(gray-encode i)) #:width 5 #:align 'right #:pad-string "0")
(~a (to-bin (gray-decode(gray-encode i))) #:width 5 #:align 'right #:pad-string "0"))))
{{out}}
=={{header|REXX}}==
The leading zeroes for the binary numbers and the gray code could've easily been elided.
/*REXX program to convert decimal───> binary ───> gray code ───> binary.*/
parse arg N .; if N=='' then N=31 /*Not specified? Then use default*/
L=max(1,length(strip(x2b(d2x(N)),'L',0))) /*for cell width formatting.*/
w=14 /*used for cell width formatting.*/
_=center('binary',w,'─') /*2nd and 4th part of the header.*/
say center('decimal',w,'─')">" _">" center('gray code',w,'─')">" _ /*hdr*/
do j=0 to N; b=right(x2b(d2x(j)),L,0) /*handle 0 ──► N.*/
g=b2gray(b) /*convert binary to gray code. */
a=gray2b(g) /*convert gray code to binary. */
say center(j,w+1) center(b,w+1) center(g,w+1) center(a,w+1) /*tell*/
end /*j*/
exit /*stick a fork in it, we're done.*/
/*───────────────────────────────────B2GRAY subroutine──────────────────*/
b2gray: procedure; parse arg x
$=left(x,1); do b=2 to length(x)
$=$||(substr(x,b-1,1) && substr(x,b,1))
end /*b*/ /* && is eXclusive OR*/
return $
/*───────────────────────────────────GRAY2B subroutine──────────────────*/
gray2b: procedure; parse arg x
$=left(x,1); do g=2 to length(x)
$=$ || (right($,1) && substr(x,g,1))
end /*g*/ /* && is eXclusive OR*/
return $
{{out}} when using the default input
=={{header|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
{{out}}
=={{header|Rust}}==
{{works with|Rust|1.1}}
fn gray_encode(integer: u64) -> u64 {
(integer >> 1) ^ integer
}
fn gray_decode(integer: u64) -> u64 {
match integer {
0 => 0,
_ => integer ^ gray_decode(integer >> 1)
}
}
fn main() {
for i in 0..32 {
println!("{:2} {:0>5b} {:0>5b} {:2}", i, i, gray_encode(i),
gray_decode(i));
}
}
=={{header|Scala}}==
Functional style: the Gray code is encoded to, and decoded from a String.
The
Here the operator is exclusive-or, "^", and we can use "_" placeholders to represent the arguments to the left and right.
def encode(n: Int) = (n ^ (n >>> 1)).toBinaryString
def decode(s: String) = Integer.parseInt( s.scanLeft(0)(_ ^ _.asDigit).tail.mkString , 2)
println("decimal binary gray decoded")
for (i <- 0 to 31; g = encode(i))
println("%7d %6s %5s %7s".format(i, i.toBinaryString, g, decode(g)))
{{out}}
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)))
}
Improved version of decode using functional style (recursion+local method).
No vars and mutations.
def decode(n:Long)={
def calc(g:Long,bits:Long):Long=if (bits>0) calc(g^bits, bits>>1) else g
calc(0, n)
}
{{out}}
=={{header|Scratch}}==
[http://i.imgur.com/0sw5D4T.png]
=={{header|Seed7}}==
The type [http://seed7.sourceforge.net/libraries/bin32.htm bin32] is intended for bit operations that are not defined for [http://seed7.sourceforge.net/libraries/integer.htm integer] values.
Bin32 is used for the [http://seed7.sourceforge.net/libraries/bin32.htm#%28in_bin32%29%3E%3C%28in_bin32%29 exclusive or] ('''><''') operation.
$ include "seed7_05.s7i";
include "bin32.s7i";
const func integer: grayEncode (in integer: n) is
return ord(bin32(n) >< bin32(n >> 1));
const func integer: grayDecode (in var integer: n) is func
result
var integer: decoded is 0;
begin
decoded := n;
while n > 1 do
n >>:= 1;
decoded := ord(bin32(decoded) >< bin32(n));
end while;
end func;
const proc: main is func
local
var integer: i is 0;
begin
for i range 0 to 32 do
writeln(i <& " => " <& grayEncode(i) radix 2 lpad0 6 <& " => " <& grayDecode(grayEncode(i)));
end for;
end func;
{{out}}
=={{header|Sidef}}==
{{trans|Perl}}
__USE_INTNUM__
func bin2gray(n) {
n ^ (n >> 1);
}
func gray2bin(num) {
var bin = num;
while (num >>= 1) { bin ^= num };
return bin;
}
0..31 -> each { |i|
var gr = bin2gray(i);
printf("%d\t%b\t%b\t%b\n", i, i, gr, gray2bin(gr));
}
=={{header|Standard ML}}==
fun gray_encode b =
Word.xorb (b, Word.>> (b, 0w1))
fun gray_decode n =
let
fun aux (p, n) =
if n = 0w0 then p
else aux (Word.xorb (p, n), Word.>> (n, 0w1))
in
aux (n, Word.>> (n, 0w1))
end;
val s = Word.fmt StringCvt.BIN;
fun aux i =
if i = 0w32 then
()
else
let
val g = gray_encode i
val b = gray_decode g
in
print (Word.toString i ^ " :\t" ^ s i ^ " => " ^ s g ^ " => " ^ s b ^ "\t: " ^ Word.toString b ^ "\n");
aux (i + 0w1)
end;
aux 0w0
=={{header|SQL}}==
DECLARE @binary AS NVARCHAR(MAX) = '001010111'
DECLARE @gray AS NVARCHAR(MAX) = ''
--Encoder
SET @gray = LEFT(@binary, 1)
WHILE LEN(@binary) > 1
BEGIN
IF LEFT(@binary, 1) != SUBSTRING(@binary, 2, 1)
SET @gray = @gray + '1'
ELSE
SET @gray = @gray + '0'
SET @binary = RIGHT(@binary, LEN(@binary) - 1)
END
SELECT @gray
--Decoder
SET @binary = LEFT(@gray, 1)
WHILE LEN(@gray) > 1
BEGIN
IF RIGHT(@binary, 1) != SUBSTRING(@gray, 2, 1)
SET @binary = @binary + '1'
ELSE
SET @binary = @binary + '0'
SET @gray = RIGHT(@gray, LEN(@gray) - 1)
END
SELECT @binary
=={{header|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]
}
{{out}}
=={{header|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
{{out}}
=={{header|VHDL}}==
Combinatorial encoder:
LIBRARY ieee;
USE ieee.std_logic_1164.all;
entity b2g is
port( bin : in std_logic_vector (4 downto 0);
gray : out std_logic_vector (4 downto 0)
);
end b2g ;
architecture rtl of b2g is
constant N : integer := bin'high;
begin
gray <= bin(n) & ( bin(N-1 downto 0) xor bin(N downto 1));
end architecture rtl;
Combinatorial decoder:
LIBRARY ieee;
USE ieee.std_logic_1164.all;
entity g2b is
port( gray : in std_logic_vector (4 downto 0);
bin : buffer std_logic_vector (4 downto 0)
);
end g2b ;
architecture rtl of g2b is
constant N : integer := bin'high;
begin
bin(N) <= gray(N);
gen_xor: for i in N-1 downto 0 generate
bin(i) <= gray(i) xor bin(i+1);
end generate;
end architecture rtl;
=={{header|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);
];
]
{{out}}
=={{header|zkl}}==
fcn grayEncode(n){ n.bitXor(n.shiftRight(1)) }
fcn grayDecode(g){ b:=g; while(g/=2){ b=b.bitXor(g) } b }
foreach n in ([0..31]){
g:=grayEncode(n); b:=grayDecode(g);
println("%2d(%05.2B) --> %2d(%05.2B) --> %2d(%05.2B)".fmt(n,n,g,g,b,b));
}
{{out}}
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
* [http://www.wisc-online.com/Objects/ViewObject.aspx?ID=IAU8307 Converting Between Gray and Binary Codes]. It includes step-by-step animations.
=={{header|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).
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
{{out}}
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
=={{header|Aime}}==
{{trans|C}}
gray_encode(integer n)
{
return n ^ (n >> 1);
}
integer
gray_decode(integer n)
{
integer p;
p = n;
while (n >>= 1) {
p ^= n;
}
return p;
}
Demonstration code:
main(void)
{
integer i, g, b;
i = 0;
while (i < 32) {
g = gray_encode(i);
b = gray_decode(g);
o_winteger(2, i);
o_text(": ");
o_fxinteger(5, 2, i);
o_text(" => ");
o_fxinteger(5, 2, g);
o_text(" => ");
o_fxinteger(5, 2, b);
o_text(": ");
o_winteger(2, b);
o_byte('\n');
i += 1;
}
return 0;
}
{{out}}
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
=={{header|ALGOL 68}}==
In Algol 68 the BITS mode is specifically designed for manipulating machine words as a row of bits so it is natural to treat Gray encoded integers as values of MODE BITS. The standard operator BIN (INT) : BITS converts an INT value to a BITS value. The ABS (BITS) : INT operator performs the reverse conversion, though it has not been needed for this task. It is also natural in the language for simple operations on values to be implemented as operators, rather than as functions, as in the program below.
OP GRAY = (BITS b) BITS : b XOR (b SHR 1); CO Convert to Gray code CO
OP YARG = (BITS g) BITS : CO Convert from Gray code CO
BEGIN
BITS b := g, mask := g SHR 1;
WHILE mask /= 2r0 DO b := b XOR mask; mask := mask SHR 1 OD;
b
END;
FOR i FROM 0 TO 31 DO
printf (($zd, ": ", 2(2r5d, " >= "), 2r5dl$, i, BIN i, GRAY BIN i, YARG GRAY BIN i))
OD
END
{{out}}
0: 00000 >= 00000 >= 00000
1: 00001 >= 00001 >= 00001
2: 00010 >= 00011 >= 00010
3: 00011 >= 00010 >= 00011
4: 00100 >= 00110 >= 00100
5: 00101 >= 00111 >= 00101
6: 00110 >= 00101 >= 00110
7: 00111 >= 00100 >= 00111
8: 01000 >= 01100 >= 01000
9: 01001 >= 01101 >= 01001
10: 01010 >= 01111 >= 01010
11: 01011 >= 01110 >= 01011
12: 01100 >= 01010 >= 01100
13: 01101 >= 01011 >= 01101
14: 01110 >= 01001 >= 01110
15: 01111 >= 01000 >= 01111
16: 10000 >= 11000 >= 10000
17: 10001 >= 11001 >= 10001
18: 10010 >= 11011 >= 10010
19: 10011 >= 11010 >= 10011
20: 10100 >= 11110 >= 10100
21: 10101 >= 11111 >= 10101
22: 10110 >= 11101 >= 10110
23: 10111 >= 11100 >= 10111
24: 11000 >= 10100 >= 11000
25: 11001 >= 10101 >= 11001
26: 11010 >= 10111 >= 11010
27: 11011 >= 10110 >= 11011
28: 11100 >= 10010 >= 11100
29: 11101 >= 10011 >= 11101
30: 11110 >= 10001 >= 11110
31: 11111 >= 10000 >= 11111
=={{header|APL}}==
Generate the complete N-bit Gray sequence as a matrix:[http://ngn.github.io/apl/web/index.html#code=N%u21905%0A%28%7B%280%2C%u2375%29%u236A1%2C%u2296%u2375%7D%u2363N%29%281%200%u2374%u236C%29,run=1 run]
({(0,⍵)⍪1,⊖⍵}⍣N)(1 0⍴⍬)
{{out}}
0 0 0 0 0
0 0 0 0 1
0 0 0 1 1
0 0 0 1 0
0 0 1 1 0
0 0 1 1 1
0 0 1 0 1
0 0 1 0 0
0 1 1 0 0
0 1 1 0 1
0 1 1 1 1
0 1 1 1 0
0 1 0 1 0
0 1 0 1 1
0 1 0 0 1
0 1 0 0 0
1 1 0 0 0
1 1 0 0 1
1 1 0 1 1
1 1 0 1 0
1 1 1 1 0
1 1 1 1 1
1 1 1 0 1
1 1 1 0 0
1 0 1 0 0
1 0 1 0 1
1 0 1 1 1
1 0 1 1 0
1 0 0 1 0
1 0 0 1 1
1 0 0 0 1
1 0 0 0 0
Encode and decode an individual integer:[http://ngn.github.io/apl/web/index.html#code=N%u21905%0AgrayEncode%u2190%7Ba%u2260N%u2191%280%2Ca%u2190%28N%u23742%29%u22A4%u2375%29%7D%0AgrayDecode%u2190%7B2%u22A5%u2260%u233FN%20N%u2191N%282%D7N%29%u2374%u2375%2C0%2CN%u23740%7D%0A%0AgrayEncode%2019,run=1 run]
grayEncode←{a≠N↑(0,a←(N⍴2)⊤⍵)}
grayDecode←{2⊥≠⌿N N↑N(2×N)⍴⍵,0,N⍴0}
grayEncode 19
{{out}}
1 1 0 1 0
=={{header|AutoHotkey}}==
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
{{out}}
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
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
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%
=={{header|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.
/* 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
{{out}}
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
=={{header|C}}==
{{trans|Tcl}}
return n ^ (n >> 1);
}
int gray_decode(int n) {
int p = n;
while (n >>= 1) p ^= n;
return p;
}
Demonstration code:
/* 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;
}
{{out}}
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
=={{header|C++}}==
#include
#include
#include
#include
uint32_t gray_encode(uint32_t b)
{
return b ^ (b >> 1);
}
uint32_t gray_decode(uint32_t g)
{
for (uint32_t bit = 1U << 31; bit > 1; bit >>= 1)
{
if (g & bit) g ^= bit >> 1;
}
return g;
}
std::string to_binary(int value) // utility function
{
const std::bitset<32> bs(value);
const std::string str(bs.to_string());
const size_t pos(str.find('1'));
return pos == std::string::npos ? "0" : str.substr(pos);
}
int main()
{
std::cout << "Number\tBinary\tGray\tDecoded\n";
for (uint32_t n = 0; n < 32; ++n)
{
uint32_t g = gray_encode(n);
assert(gray_decode(g) == n);
std::cout << n << "\t" << to_binary(n) << "\t" << to_binary(g) << "\t" << g << "\n";
}
}
{{out}}
Number Binary Gray Decoded
0 0 0 0
1 1 1 1
2 10 11 3
3 11 10 2
4 100 110 6
5 101 111 7
6 110 101 5
7 111 100 4
8 1000 1100 12
9 1001 1101 13
10 1010 1111 15
11 1011 1110 14
12 1100 1010 10
13 1101 1011 11
14 1110 1001 9
15 1111 1000 8
16 10000 11000 24
17 10001 11001 25
18 10010 11011 27
19 10011 11010 26
20 10100 11110 30
21 10101 11111 31
22 10110 11101 29
23 10111 11100 28
24 11000 10100 20
25 11001 10101 21
26 11010 10111 23
27 11011 10110 22
28 11100 10010 18
29 11101 10011 19
30 11110 10001 17
31 11111 10000 16
=={{header|C sharp}}==
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))));
}
}
}
{{out}}
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
=={{header|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)
=={{header|Common Lisp}}==
(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)))
{{out}}
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
=={{header|Component Pascal}}==
BlackBox Component Builder
MODULE GrayCodes;
IMPORT StdLog,SYSTEM;
PROCEDURE Encode*(i: INTEGER; OUT x: INTEGER);
VAR
j: INTEGER;
s,r: SET;
BEGIN
s := BITS(i);j := MAX(SET);
WHILE (j >= 0) & ~(j IN s) DO DEC(j) END;
r := {};IF j >= 0 THEN INCL(r,j) END;
WHILE j > 0 DO
IF ((j IN s) & ~(j - 1 IN s)) OR (~(j IN s) & (j - 1 IN s)) THEN INCL(r,j-1) END;
DEC(j)
END;
x := SYSTEM.VAL(INTEGER,r)
END Encode;
PROCEDURE Decode*(x: INTEGER; OUT i: INTEGER);
VAR
j: INTEGER;
s,r: SET;
BEGIN
s := BITS(x);r:={};j := MAX(SET);
WHILE (j >= 0) & ~(j IN s) DO DEC(j) END;
IF j >= 0 THEN INCL(r,j) END;
WHILE j > 0 DO
IF ((j IN r) & ~(j - 1 IN s)) OR (~(j IN r) & (j - 1 IN s)) THEN INCL(r,j-1) END;
DEC(j)
END;
i := SYSTEM.VAL(INTEGER,r);
END Decode;
PROCEDURE Do*;
VAR
grayCode,binCode: INTEGER;
i: INTEGER;
BEGIN
StdLog.String(" i ");StdLog.String(" bin code ");StdLog.String(" gray code ");StdLog.Ln;
StdLog.String("---");StdLog.String(" ----------------");StdLog.String(" ---------------");StdLog.Ln;
FOR i := 0 TO 32 DO;
Encode(i,grayCode);Decode(grayCode,binCode);
StdLog.IntForm(i,10,3,' ',FALSE);
StdLog.IntForm(binCode,2,16,' ',TRUE);
StdLog.IntForm(grayCode,2,16,' ',TRUE);
StdLog.Ln;
END
END Do;
END GrayCodes.
Execute: ^QGrayCodes.Do
{{out}}
i bin code gray code
--- ---------------- ---------------
0 0%2 0%2
1 1%2 1%2
2 10%2 11%2
3 11%2 10%2
4 100%2 110%2
5 101%2 111%2
6 110%2 101%2
7 111%2 100%2
8 1000%2 1100%2
9 1001%2 1101%2
10 1010%2 1111%2
11 1011%2 1110%2
12 1100%2 1010%2
13 1101%2 1011%2
14 1110%2 1001%2
15 1111%2 1000%2
16 10000%2 11000%2
17 10001%2 11001%2
18 10010%2 11011%2
19 10011%2 11010%2
20 10100%2 11110%2
21 10101%2 11111%2
22 10110%2 11101%2
23 10111%2 11100%2
24 11000%2 10100%2
25 11001%2 10101%2
26 11010%2 10111%2
27 11011%2 10110%2
28 11100%2 10010%2
29 11101%2 10011%2
30 11110%2 10001%2
31 11111%2 10000%2
32 100000%2 110000%2
=={{header|D}}==
return n ^ (n >> 1);
}
uint grayDecode(uint n) pure nothrow @nogc {
auto p = n;
while (n >>= 1)
p ^= n;
return p;
}
void main() {
import std.stdio;
" N N2 enc dec2 dec".writeln;
foreach (immutable n; 0 .. 32) {
immutable g = n.grayEncode;
immutable d = g.grayDecode;
writefln("%2d: %5b => %5b => %5b: %2d", n, n, g, d, d);
assert(d == n);
}
}
{{out}}
N N2 enc dec2 dec
0: 0 => 0 => 0: 0
1: 1 => 1 => 1: 1
2: 10 => 11 => 10: 2
3: 11 => 10 => 11: 3
4: 100 => 110 => 100: 4
5: 101 => 111 => 101: 5
6: 110 => 101 => 110: 6
7: 111 => 100 => 111: 7
8: 1000 => 1100 => 1000: 8
9: 1001 => 1101 => 1001: 9
10: 1010 => 1111 => 1010: 10
11: 1011 => 1110 => 1011: 11
12: 1100 => 1010 => 1100: 12
13: 1101 => 1011 => 1101: 13
14: 1110 => 1001 => 1110: 14
15: 1111 => 1000 => 1111: 15
16: 10000 => 11000 => 10000: 16
17: 10001 => 11001 => 10001: 17
18: 10010 => 11011 => 10010: 18
19: 10011 => 11010 => 10011: 19
20: 10100 => 11110 => 10100: 20
21: 10101 => 11111 => 10101: 21
22: 10110 => 11101 => 10110: 22
23: 10111 => 11100 => 10111: 23
24: 11000 => 10100 => 11000: 24
25: 11001 => 10101 => 11001: 25
26: 11010 => 10111 => 11010: 26
27: 11011 => 10110 => 11011: 27
28: 11100 => 10010 => 11100: 28
29: 11101 => 10011 => 11101: 29
30: 11110 => 10001 => 11110: 30
31: 11111 => 10000 => 11111: 31
===Compile-Time version===
This version uses a compile time generated translation table,
if maximum bit width of the numbers is a constant.
The encoding table is generated recursively,
then the decode table is calculated and appended.
Same output.
T[] gray(int N : 1, T)() pure nothrow {
return [T(0), 1];
}
/// Recursively generate gray encoding mapping table.
T[] gray(int N, T)() pure nothrow if (N <= T.sizeof * 8) {
enum T M = T(2) ^^ (N - 1);
T[] g = gray!(N - 1, T)();
foreach (immutable i; 0 .. M)
g ~= M + g[M - i - 1];
return g;
}
T[][] grayDict(int N, T)() pure nothrow {
T[][] dict = [gray!(N, T)(), [0]];
// Append inversed gray encoding mapping.
foreach (immutable i; 1 .. dict[0].length)
dict[1] ~= countUntil(dict[0], i);
return dict;
}
enum M { Encode = 0, Decode = 1 }
T gray(int N, T)(in T n, in int mode=M.Encode) pure nothrow {
// Generated at compile time.
enum dict = grayDict!(N, T)();
return dict[mode][n];
}
void main() {
foreach (immutable i; 0 .. 32) {
immutable encoded = gray!(5)(i, M.Encode);
immutable decoded = gray!(5)(encoded, M.Decode);
writefln("%2d: %5b => %5b : %2d", i, i, encoded, decoded);
}
}
===Short Functional-Style Generator===
string[] g(in uint n) pure nothrow {
return n ? g(n - 1).map!q{'0' ~ a}.array ~
g(n - 1).retro.map!q{'1' ~ a}.array
: [""];
}
void main() {
4.g.writeln;
}
{{out}}
["0000", "0001", "0011", "0010", "0110", "0111", "0101", "0100", "1100", "1101", "1111", "1110", "1010", "1011", "1001", "1000"]
=={{header|Delphi}}==
{{trans|DWScript}}
{$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.
=={{header|DWScript}}==
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;
=={{header|Elixir}}==
{{trans|Erlang}}
use Bitwise
def encode(n), do: bxor(n, bsr(n,1))
def decode(g), do: decode(g,0)
def decode(0,n), do: n
def decode(g,n), do: decode(bsr(g,1), bxor(g,n))
end
Enum.each(0..31, fn(n) ->
g = Gray_code.encode(n)
d = Gray_code.decode(g)
:io.fwrite("~2B : ~5.2.0B : ~5.2.0B : ~5.2.0B : ~2B~n", [n, n, g, d, d])
end)
output is the same as "Erlang".
=={{header|Erlang}}==
{{trans|Euphoria}}
-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:
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).
{{out}}
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
=={{header|Euphoria}}==
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
{{out}}
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
=={{header|Factor}}==
Translation of C.
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:
{ 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 }
=={{header|Forth}}==
: 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 ;
=={{header|Fortran}}==
Using [http://www.everyspec.com/MIL-STD/MIL-STD+(1700+-+1799)/download.php?spec=MIL-STD-1753.011044.PDF MIL-STD-1753] extensions in '''Fortran 77''', and formulas found at OEIS for [http://oeis.org/A003188 direct] and [http://oeis.org/A006068 inverse] Gray code :
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
=={{header|Frink}}==
Frink has built-in functions to convert to and from binary reflected Gray code.
for i=0 to 31
{
gray = binaryToGray[i]
back = grayToBinary[gray]
println[(i->binary) + "\t" + (gray->binary) + "\t" + (back->binary)]
}
=={{header|Go}}==
{{trans|Euphoria}}
Binary reflected, as described in the task. Reading down through the solutions, the Euphoria decode algorithm caught my eye as being concise and easy to read.
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)
}
}
{{out}}
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
=={{header|Groovy}}==
Solution:
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 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
=={{header|Haskell}}==
For zero padding, replace the %5s specifiers in the format string with %05s.
import Data.Char
import Numeric
import Control.Monad
import Text.Printf
grayToBin :: (Integral t, Bits t) => t -> t
grayToBin 0 = 0
grayToBin g = g `xor` (grayToBin $ g `shiftR` 1)
binToGray :: (Integral t, Bits t) => t -> t
binToGray b = b `xor` (b `shiftR` 1)
showBinary :: (Integral t, Show t) => t -> String
showBinary n = showIntAtBase 2 intToDigit n ""
showGrayCode :: (Integral t, Bits t, PrintfArg t, Show t) => t -> IO ()
showGrayCode num = do
let bin = showBinary num
let gray = showBinary (binToGray num)
printf "int: %2d -> bin: %5s -> gray: %5s\n" num bin gray
main = forM_ [0..31::Int] showGrayCode
=={{header|Icon}} and {{header|Unicon}}==
The following works in both languages:
procedure main()
every write(right(i := 0 to 10,4),":",right(int2bit(i),10)," -> ",
right(g := gEncode(i),10)," -> ",
right(b := gDecode(g),10)," -> ",
right(bit2int(b),10))
end
procedure gEncode(b)
return int2bit(ixor(b, ishift(b,-1)))
end
procedure gDecode(g)
b := g[1]
every i := 2 to *g do b ||:= if g[i] == b[i-1] then "0" else "1"
return b
end
Sample run:
->gc
0: 0 -> 0 -> 0 -> 0
1: 1 -> 1 -> 1 -> 1
2: 10 -> 11 -> 10 -> 2
3: 11 -> 10 -> 11 -> 3
4: 100 -> 110 -> 100 -> 4
5: 101 -> 111 -> 101 -> 5
6: 110 -> 101 -> 110 -> 6
7: 111 -> 100 -> 111 -> 7
8: 1000 -> 1100 -> 1000 -> 8
9: 1001 -> 1101 -> 1001 -> 9
10: 1010 -> 1111 -> 1010 -> 10
->
=={{header|J}}==
G2B is an invertible function which will translate Gray code to Binary:Thus
G2B inv will translate binary to Gray code.Required example:
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 |
+--+---------+----------+----------------+
=={{header|Java}}==
{{trans|C}}
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)));
}
}
}
{{out}}
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:
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:
{{untested}}
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);
}
=={{header|Julia}}==
{{trans|C}}
function gray_decode(n)
p = n
while (n >>= 1) != 0
p $= n
end
return p
end
Note that these functions work for any integer type, including arbitrary-precision integers (the built-in
BigInt type).=={{header|K}}==
Binary to Gray code
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"
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
(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)
Iterative version with "do"
Presentation
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
{{out}}
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
=={{header|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
=={{header|Limbo}}==
{{trans|Go}}
include "sys.m"; sys: Sys;
print: import sys;
include "draw.m";
Gray: module {
init: fn(nil: ref Draw->Context, args: list of string);
# Export gray and grayinv so that this module can be used as either a
# standalone program or as a library:
gray: fn(n: int): int;
grayinv: fn(n: int): int;
};
init(nil: ref Draw->Context, args: list of string)
{
sys = load Sys Sys->PATH;
for(i := 0; i < 32; i++) {
g := gray(i);
f := grayinv(g);
print("%2d %5s %2d %5s %5s %2d\n", i, binstr(i), g, binstr(g), binstr(f), f);
}
}
gray(n: int): int
{
return n ^ (n >> 1);
}
grayinv(n: int): int
{
r := 0;
while(n) {
r ^= n;
n >>= 1;
}
return r;
}
binstr(n: int): string
{
if(!n)
return "0";
s := "";
while(n) {
s = (string (n&1)) + s;
n >>= 1;
}
return s;
}
{{out}}
0 0 0 0 0 0
1 1 1 1 1 1
2 10 3 11 10 2
3 11 2 10 11 3
4 100 6 110 100 4
5 101 7 111 101 5
6 110 5 101 110 6
7 111 4 100 111 7
8 1000 12 1100 1000 8
9 1001 13 1101 1001 9
10 1010 15 1111 1010 10
11 1011 14 1110 1011 11
12 1100 10 1010 1100 12
13 1101 11 1011 1101 13
14 1110 9 1001 1110 14
15 1111 8 1000 1111 15
16 10000 24 11000 10000 16
17 10001 25 11001 10001 17
18 10010 27 11011 10010 18
19 10011 26 11010 10011 19
20 10100 30 11110 10100 20
21 10101 31 11111 10101 21
22 10110 29 11101 10110 22
23 10111 28 11100 10111 23
24 11000 20 10100 11000 24
25 11001 21 10101 11001 25
26 11010 23 10111 11010 26
27 11011 22 10110 11011 27
28 11100 18 10010 11100 28
29 11101 19 10011 11101 29
30 11110 17 10001 11110 30
31 11111 16 10000 11111 31
=={{header|Logo}}==
{{trans|Euphoria}}
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:
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
{{out}}
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
=={{header|Lua}}==
{{trans|Euphoria}}
This code uses the [http://bitop.luajit.org/index.html Lua BitOp] module. Designed to be a module named gray.lua.
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 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
{{out}}
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
=={{header|Mathematica}}==
graydecode[n_]:=Fold[BitXor,0,FixedPointList[BitShiftRight,n]]
{{out}}
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}
=={{header|MATLAB}}==
%% Gray Code Generator
% this script generates gray codes of n bits
% total 2^n -1 continuous gray codes will be generated.
% this code follows a recursive approach. therefore,
% it can be slow for large n
clear all;
clc;
bits = input('Enter the number of bits: ');
if (bits<1)
disp('Sorry, number of bits should be positive');
elseif (mod(bits,1)~=0)
disp('Sorry, number of bits can only be positive integers');
else
initial_container = [0;1];
if bits == 1
result = initial_container;
else
previous_container = initial_container;
for i=2:bits
new_gray_container = zeros(2^i,i);
new_gray_container(1:(2^i)/2,1) = 0;
new_gray_container(((2^i)/2)+1:end,1) = 1;
for j = 1:(2^i)/2
new_gray_container(j,2:end) = previous_container(j,:);
end
for j = ((2^i)/2)+1:2^i
new_gray_container(j,2:end) = previous_container((2^i)+1-j,:);
end
previous_container = new_gray_container;
end
result = previous_container;
end
fprintf('Gray code of %d bits',bits);
disp(' ');
disp(result);
end
{{out}}
Enter the number of bits: 5
Gray code of 5 bits
0 0 0 0 0
0 0 0 0 1
0 0 0 1 1
0 0 0 1 0
0 0 1 1 0
0 0 1 1 1
0 0 1 0 1
0 0 1 0 0
0 1 1 0 0
0 1 1 0 1
0 1 1 1 1
0 1 1 1 0
0 1 0 1 0
0 1 0 1 1
0 1 0 0 1
0 1 0 0 0
1 1 0 0 0
1 1 0 0 1
1 1 0 1 1
1 1 0 1 0
1 1 1 1 0
1 1 1 1 1
1 1 1 0 1
1 1 1 0 0
1 0 1 0 0
1 0 1 0 1
1 0 1 1 1
1 0 1 1 0
1 0 0 1 0
1 0 0 1 1
1 0 0 0 1
1 0 0 0 0
=={{header|Mercury}}==
The following is a full implementation of Gray encoding and decoding.
It publicly exposes the gray type along with the following
value conversion functions:
* gray.from_int/1
* gray.to_int/1
The from_int/1 and to_int/1 functions are ''value'' conversion functions. from_int/1 converts an int value into the enclosing gray type. to_int/1 converts a gray value back into a regular int type.
The additional gray.coerce/2 predicate converts the ''representation'' underlying a gray value into an int value or vice versa (it is moded in both directions). For type safety reasons we do not wish to generally expose the underlying representation, but for some purposes, most notably I/O or storage or their ilk we have to break the type safety. The coerce/2 predicate is used for this purpose.
:- interface.
:- import_module int.
:- type gray.
% VALUE conversion functions
:- func gray.from_int(int) = gray.
:- func gray.to_int(gray) = int.
% REPRESENTATION conversion predicate
:- pred gray.coerce(gray, int).
:- mode gray.coerce(in, out) is det.
:- mode gray.coerce(out, in) is det.
:- implementation.
:- import_module list.
:- type gray
---> gray(int).
gray.from_int(X) = gray(X `xor` (X >> 1)).
gray.to_int(gray(G)) = (G > 0 -> G `xor` gray.to_int(gray(G >> 1))
; G).
gray.coerce(gray(I), I).
:- end_module gray.
The following program tests the above code:
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module gray.
:- import_module int, list, string.
:- pred check_conversion(list(int)::in, list(gray)::out) is semidet.
:- pred display_lists(list(int)::in, list(gray)::in, io::di, io::uo) is det.
:- pred display_record(int::in, gray::in, io::di, io::uo) is det.
main(!IO) :-
Numbers = 0..31,
( check_conversion(Numbers, Grays) ->
io.format("%8s %8s %8s\n", [s("Number"), s("Binary"), s("Gray")], !IO),
io.format("%8s %8s %8s\n", [s("------"), s("------"), s("----")], !IO),
display_lists(Numbers, Grays, !IO)
; io.write("Either conversion or back-conversion failed.\n", !IO)).
check_conversion(Numbers, Grays) :-
Grays = list.map(gray.from_int, Numbers),
Numbers = list.map(gray.to_int, Grays).
display_lists(Numbers, Grays, !IO) :-
list.foldl_corresponding(display_record, Numbers, Grays, !IO).
display_record(Number, Gray, !IO) :-
gray.coerce(Gray, GrayRep),
NumBin = string.int_to_base_string(Number, 2),
GrayBin = string.int_to_base_string(GrayRep, 2),
io.format("%8d %8s %8s\n", [i(Number), s(NumBin), s(GrayBin)], !IO).
:- end_module gray_test.
The main/2 predicate generates a list of numbers from 0 to 31 inclusive and then checks that conversion is working properly.
It does so by calling the check_conversion/2 predicate with the
list of numbers as an input and the list of Gray-encoded numbers as an output.
Note the absence of the usual kinds of testing you'd see in most programming languages.
gray.from_int/1 is mapped over the Numbers (input) list and placed into the Grays (output) list.
Then gray.to_int is mapped over the Grays list and placed into the Numbers (input) list.
Or so it would seem to those used to imperative or functional languages.
In reality what's happening is [https://en.wikipedia.org/wiki/Unification_%28computer_science%29 unification].
Since the Grays list is not yet populated, unification is very similar notionally to assignment in other languages.
Numbers, however, '''is''' instantiated and thus unification is more like testing for equality.
If the conversions check out, main/2 prints off some headers and then displays the lists. Here we're cluttering up the namespace of the gray_test module a little by providing a one-line predicate. While it is true that we ''could'' just take the contents of that predicate and place it inline, we've chosen not to do that because the name display_lists communicates more effectively what we intend.
The compiler is smart enough to automatically inline that predicate call so there's no efficiency reason not to do it.
However we choose to do that, the result is the same: repeated calls to display_record/4. In that predicate the aforementioned coerce/2 predicate extracts, in this case, the Gray value's representation.
This value and the corresponding int value are then converted into a string showing the base-2 representation of their values.
io.format/4 then prints them off in a nice format.
The output of the program looks like this:
Number Binary Gray
------ ------ ----
0 0 0
1 1 1
2 10 11
3 11 10
4 100 110
5 101 111
6 110 101
7 111 100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
16 10000 11000
17 10001 11001
18 10010 11011
19 10011 11010
20 10100 11110
21 10101 11111
22 10110 11101
23 10111 11100
24 11000 10100
25 11001 10101
26 11010 10111
27 11011 10110
28 11100 10010
29 11101 10011
30 11110 10001
31 11111 10000
=={{header|Nim}}==
{{trans|C}}
n xor (n shr 1)
proc grayDecode(n): auto =
result = n
var t = n
while t > 0:
t = t shr 1
result = result xor t
Demonstration code:
for i in 0 .. 32:
echo i, " => ", toBin(grayEncode(i), 6), " => ", grayDecode(grayEncode(i))
{{out}}
0 => 000000 => 0
1 => 000001 => 1
2 => 000011 => 2
3 => 000010 => 3
4 => 000110 => 4
5 => 000111 => 5
6 => 000101 => 6
7 => 000100 => 7
8 => 001100 => 8
9 => 001101 => 9
10 => 001111 => 10
11 => 001110 => 11
12 => 001010 => 12
13 => 001011 => 13
14 => 001001 => 14
15 => 001000 => 15
16 => 011000 => 16
17 => 011001 => 17
18 => 011011 => 18
19 => 011010 => 19
20 => 011110 => 20
21 => 011111 => 21
22 => 011101 => 22
23 => 011100 => 23
24 => 010100 => 24
25 => 010101 => 25
26 => 010111 => 26
27 => 010110 => 27
28 => 010010 => 28
29 => 010011 => 29
30 => 010001 => 30
31 => 010000 => 31
32 => 110000 => 32
=={{header|OCaml}}==
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
=={{header|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).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)))
{{out}}
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
=={{header|Pascal}}==
See [[Gray_code#Delphi | Delphi]]
=={{header|PicoLisp}}==
(bin (x| N (>> 1 N))) )
(de grayDecode (G)
(bin
(pack
(let X 0
(mapcar
'((C) (setq X (x| X (format C))))
(chop G) ) ) ) ) )
Test:
(for I (range 0 31)
(let G (grayEncode I)
(tab (4 9 9 9) I (bin I) G (grayDecode G)) ) )
{{out}}
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
=={{header|Perl}}==
{
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);
}
=={{header|Perl 6}}==
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.
{{trans|Haskell}}
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;
}
{{out}}
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).
=={{header|PHP}}==
/**
* @author Elad Yosifon
*/
/**
* @param int $binary
* @return int
*/
function gray_encode($binary){
return $binary ^ ($binary >> 1);
}
/**
* @param int $gray
* @return int
*/
function gray_decode($gray){
$binary = $gray;
while($gray >>= 1) $binary ^= $gray;
return $binary;
}
for($i=0;$i<32;$i++){
$gray_encoded = gray_encode($i);
printf("%2d : %05b => %05b => %05b : %2d \n",$i, $i, $gray_encoded, $gray_encoded, gray_decode($gray_encoded));
}
{{out}}
0 : 00000 => 00000 => 00000 : 0
1 : 00001 => 00001 => 00001 : 1
2 : 00010 => 00011 => 00011 : 2
3 : 00011 => 00010 => 00010 : 3
4 : 00100 => 00110 => 00110 : 4
5 : 00101 => 00111 => 00111 : 5
6 : 00110 => 00101 => 00101 : 6
7 : 00111 => 00100 => 00100 : 7
8 : 01000 => 01100 => 01100 : 8
9 : 01001 => 01101 => 01101 : 9
10 : 01010 => 01111 => 01111 : 10
11 : 01011 => 01110 => 01110 : 11
12 : 01100 => 01010 => 01010 : 12
13 : 01101 => 01011 => 01011 : 13
14 : 01110 => 01001 => 01001 : 14
15 : 01111 => 01000 => 01000 : 15
16 : 10000 => 11000 => 11000 : 16
17 : 10001 => 11001 => 11001 : 17
18 : 10010 => 11011 => 11011 : 18
19 : 10011 => 11010 => 11010 : 19
20 : 10100 => 11110 => 11110 : 20
21 : 10101 => 11111 => 11111 : 21
22 : 10110 => 11101 => 11101 : 22
23 : 10111 => 11100 => 11100 : 23
24 : 11000 => 10100 => 10100 : 24
25 : 11001 => 10101 => 10101 : 25
26 : 11010 => 10111 => 10111 : 26
27 : 11011 => 10110 => 10110 : 27
28 : 11100 => 10010 => 10010 : 28
29 : 11101 => 10011 => 10011 : 29
30 : 11110 => 10001 => 10001 : 30
31 : 11111 => 10000 => 10000 : 31
=={{header|PL/I}}==
Gray_code: procedure options (main); /* 15 November 2013 */
declare (bin(0:31), g(0:31), b2(0:31)) bit (5);
declare (c, carry) bit (1);
declare (i, j) fixed binary (7);
bin(0) = '00000'b;
do i = 0 to 31;
if i > 0 then
do;
carry = '1'b;
bin(i) = bin(i-1);
do j = 5 to 1 by -1;
c = substr(bin(i), j, 1) & carry;
substr(bin(i), j, 1) = substr(bin(i), j, 1) ^ carry;
carry = c;
end;
end;
g(i) = bin(i) ^ '0'b || substr(bin(i), 1, 4);
end;
do i = 0 to 31;
substr(b2(i), 1, 1) = substr(g(i), 1, 1);
do j = 2 to 5;
substr(b2(i), j, 1) = substr(g(i), j, 1) ^ substr(bin(i), j-1, 1);
end;
end;
do i = 0 to 31;
put skip edit (i, bin(i), g(i), b2(i)) (f(2), 3(x(1), b));
end;
end Gray_code;
0 00000 00000 00000
1 00001 00001 00001
2 00010 00011 00010
3 00011 00010 00011
4 00100 00110 00100
5 00101 00111 00101
6 00110 00101 00110
7 00111 00100 00111
8 01000 01100 01000
9 01001 01101 01001
10 01010 01111 01010
11 01011 01110 01011
12 01100 01010 01100
13 01101 01011 01101
14 01110 01001 01110
15 01111 01000 01111
16 10000 11000 10000
17 10001 11001 10001
18 10010 11011 10010
19 10011 11010 10011
20 10100 11110 10100
21 10101 11111 10101
22 10110 11101 10110
23 10111 11100 10111
24 11000 10100 11000
25 11001 10101 11001
26 11010 10111 11010
27 11011 10110 11011
28 11100 10010 11100
29 11101 10011 11101
30 11110 10001 11110
31 11111 10000 11111
=={{header|PowerBASIC}}==
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
=={{header|Prolog}}==
=== Codecs ===
The encoding and decoding predicates are simple and will work
with any Prolog that supports bitwise integer operations.
{{works with|SWI Prolog}}
{{works with|YAP}}
N0 is N >> 1,
G is N xor N0.
from_gray(G, N) :-
( G > 0
-> S is G >> 1,
from_gray(S, N0),
N is G xor N0
; N is G ).
=== Test Code ===
A quick driver around this to test it will prove the point.
(This test script uses features not available in every Prolog implementation.)
{{works with|SWI Prolog}}
{{works with|YAP}}
to_gray(N, G) :-
N0 is N >> 1,
G is N xor N0.
from_gray(G, N) :-
( G > 0
-> S is G >> 1,
from_gray(S, N0),
N is G xor N0
; N is G ).
make_num(In, Out) :-
atom_to_term(In, Out, _),
integer(Out).
write_record(Number, Gray, Decoded) :-
format('~w~10|~2r~10+~2r~10+~2r~10+~w~n',
[Number, Number, Gray, Decoded, Decoded]).
go :-
setof(N, between(0, 31, N), Numbers),
maplist(to_gray, Numbers, Grays),
maplist(from_gray, Grays, Decodeds),
format('~w~10|~w~10+~w~10+~w~10+~w~n',
['Number', 'Binary', 'Gray', 'Decoded', 'Number']),
format('~w~10|~w~10+~w~10+~w~10+~w~n',
['------', '------', '----', '-------', '------']),
maplist(write_record, Numbers, Grays, Decodeds).
go :- halt(1).
{{out}}
Putting all of this in a file, we execute it, getting the following results:
% swipl -q -t go -f gray.pl # OR: yap -q -z go,halt -f gray.pl
Number Binary Gray Decoded Number
------ ------ ---- ------- ------
0 0 0 0 0
1 1 1 1 1
2 10 11 10 2
3 11 10 11 3
4 100 110 100 4
5 101 111 101 5
6 110 101 110 6
7 111 100 111 7
8 1000 1100 1000 8
9 1001 1101 1001 9
10 1010 1111 1010 10
11 1011 1110 1011 11
12 1100 1010 1100 12
13 1101 1011 1101 13
14 1110 1001 1110 14
15 1111 1000 1111 15
16 10000 11000 10000 16
17 10001 11001 10001 17
18 10010 11011 10010 18
19 10011 11010 10011 19
20 10100 11110 10100 20
21 10101 11111 10101 21
22 10110 11101 10110 22
23 10111 11100 10111 23
24 11000 10100 11000 24
25 11001 10101 11001 25
26 11010 10111 11010 26
27 11011 10110 11011 27
28 11100 10010 11100 28
29 11101 10011 11101 29
30 11110 10001 11110 30
31 11111 10000 11111 31
=={{header|PureBasic}}==
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
{{out}}
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
=={{header|Python}}==
This example works with lists of discrete binary digits.
;First some int<>bin conversion routines:
'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: [http://www.wisc-online.com/Objects/ViewObject.aspx?ID=IAU8307 Converting Between Gray and Binary Codes].
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
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
>>>
=={{header|R}}==
GrayEncode <- function(binary) {
gray <- substr(binary,1,1)
repeat {
if (substr(binary,1,1) != substr(binary,2,2)) gray <- paste(gray,"1",sep="")
else gray <- paste(gray,"0",sep="")
binary <- substr(binary,2,nchar(binary))
if (nchar(binary) <=1) {
break
}
}
return (gray)
}
GrayDecode <- function(gray) {
binary <- substr(gray,1,1)
repeat {
if (substr(binary,nchar(binary),nchar(binary)) != substr(gray,2,2)) binary <- paste(binary ,"1",sep="")
else binary <- paste(binary ,"0",sep="")
gray <- substr(gray,2,nchar(gray))
if (nchar(gray) <=1) {
break
}
}
return (binary)
}
=={{header|Racket}}==
#lang racket
(define (gray-encode n) (bitwise-xor n (arithmetic-shift n -1)))
(define (gray-decode n)
(letrec ([loop (lambda(g bits)
(if (> bits 0)
(loop (bitwise-xor g bits) (arithmetic-shift bits -1))
g))])
(loop 0 n)))
(define (to-bin n) (format "~b" n))
(define (show-table)
(for ([i (in-range 1 32)])
(printf "~a | ~a | ~a ~n"
(~r i #:min-width 2 #:pad-string "0")
(~a (to-bin(gray-encode i)) #:width 5 #:align 'right #:pad-string "0")
(~a (to-bin (gray-decode(gray-encode i))) #:width 5 #:align 'right #:pad-string "0"))))
{{out}}
> (show-table)
01 | 00001 | 00001
02 | 00011 | 00010
03 | 00010 | 00011
04 | 00110 | 00100
05 | 00111 | 00101
06 | 00101 | 00110
07 | 00100 | 00111
08 | 01100 | 01000
09 | 01101 | 01001
10 | 01111 | 01010
11 | 01110 | 01011
12 | 01010 | 01100
13 | 01011 | 01101
14 | 01001 | 01110
15 | 01000 | 01111
16 | 11000 | 10000
17 | 11001 | 10001
18 | 11011 | 10010
19 | 11010 | 10011
20 | 11110 | 10100
21 | 11111 | 10101
22 | 11101 | 10110
23 | 11100 | 10111
24 | 10100 | 11000
25 | 10101 | 11001
26 | 10111 | 11010
27 | 10110 | 11011
28 | 10010 | 11100
29 | 10011 | 11101
30 | 10001 | 11110
31 | 10000 | 11111
=={{header|REXX}}==
The leading zeroes for the binary numbers and the gray code could've easily been elided.
parse arg N .; if N=='' then N=31 /*Not specified? Then use default*/
L=max(1,length(strip(x2b(d2x(N)),'L',0))) /*for cell width formatting.*/
w=14 /*used for cell width formatting.*/
_=center('binary',w,'─') /*2nd and 4th part of the header.*/
say center('decimal',w,'─')">" _">" center('gray code',w,'─')">" _ /*hdr*/
do j=0 to N; b=right(x2b(d2x(j)),L,0) /*handle 0 ──► N.*/
g=b2gray(b) /*convert binary to gray code. */
a=gray2b(g) /*convert gray code to binary. */
say center(j,w+1) center(b,w+1) center(g,w+1) center(a,w+1) /*tell*/
end /*j*/
exit /*stick a fork in it, we're done.*/
/*───────────────────────────────────B2GRAY subroutine──────────────────*/
b2gray: procedure; parse arg x
$=left(x,1); do b=2 to length(x)
$=$||(substr(x,b-1,1) && substr(x,b,1))
end /*b*/ /* && is eXclusive OR*/
return $
/*───────────────────────────────────GRAY2B subroutine──────────────────*/
gray2b: procedure; parse arg x
$=left(x,1); do g=2 to length(x)
$=$ || (right($,1) && substr(x,g,1))
end /*g*/ /* && is eXclusive OR*/
return $
{{out}} when using the default input
───decimal────> ────binary────> ──gray code───> ────binary────
0 00000 00000 00000
1 00001 00001 00001
2 00010 00011 00010
3 00011 00010 00011
4 00100 00110 00100
5 00101 00111 00101
6 00110 00101 00110
7 00111 00100 00111
8 01000 01100 01000
9 01001 01101 01001
10 01010 01111 01010
11 01011 01110 01011
12 01100 01010 01100
13 01101 01011 01101
14 01110 01001 01110
15 01111 01000 01111
16 10000 11000 10000
17 10001 11001 10001
18 10010 11011 10010
19 10011 11010 10011
20 10100 11110 10100
21 10101 11111 10101
22 10110 11101 10110
23 10111 11100 10111
24 11000 10100 11000
25 11001 10101 11001
26 11010 10111 11010
27 11011 10110 11011
28 11100 10010 11100
29 11101 10011 11101
30 11110 10001 11110
31 11111 10000 11111
=={{header|Ruby}}==
Integer#from_gray has recursion so it can use each bit of the answer to compute the next bit.
# 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
{{out}}
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
=={{header|Rust}}==
{{works with|Rust|1.1}}
(integer >> 1) ^ integer
}
fn gray_decode(integer: u64) -> u64 {
match integer {
0 => 0,
_ => integer ^ gray_decode(integer >> 1)
}
}
fn main() {
for i in 0..32 {
println!("{:2} {:0>5b} {:0>5b} {:2}", i, i, gray_encode(i),
gray_decode(i));
}
}
=={{header|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 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)))
{{out}}
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 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)))
}
Improved version of decode using functional style (recursion+local method).
No vars and mutations.
def calc(g:Long,bits:Long):Long=if (bits>0) calc(g^bits, bits>>1) else g
calc(0, n)
}
{{out}}
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
=={{header|Scratch}}==
[http://i.imgur.com/0sw5D4T.png]
=={{header|Seed7}}==
The type [http://seed7.sourceforge.net/libraries/bin32.htm bin32] is intended for bit operations that are not defined for [http://seed7.sourceforge.net/libraries/integer.htm integer] values.
Bin32 is used for the [http://seed7.sourceforge.net/libraries/bin32.htm#%28in_bin32%29%3E%3C%28in_bin32%29 exclusive or] ('''><''') operation.
include "bin32.s7i";
const func integer: grayEncode (in integer: n) is
return ord(bin32(n) >< bin32(n >> 1));
const func integer: grayDecode (in var integer: n) is func
result
var integer: decoded is 0;
begin
decoded := n;
while n > 1 do
n >>:= 1;
decoded := ord(bin32(decoded) >< bin32(n));
end while;
end func;
const proc: main is func
local
var integer: i is 0;
begin
for i range 0 to 32 do
writeln(i <& " => " <& grayEncode(i) radix 2 lpad0 6 <& " => " <& grayDecode(grayEncode(i)));
end for;
end func;
{{out}}
0 => 000000 => 0
1 => 000001 => 1
2 => 000011 => 2
3 => 000010 => 3
4 => 000110 => 4
5 => 000111 => 5
6 => 000101 => 6
7 => 000100 => 7
8 => 001100 => 8
9 => 001101 => 9
10 => 001111 => 10
11 => 001110 => 11
12 => 001010 => 12
13 => 001011 => 13
14 => 001001 => 14
15 => 001000 => 15
16 => 011000 => 16
17 => 011001 => 17
18 => 011011 => 18
19 => 011010 => 19
20 => 011110 => 20
21 => 011111 => 21
22 => 011101 => 22
23 => 011100 => 23
24 => 010100 => 24
25 => 010101 => 25
26 => 010111 => 26
27 => 010110 => 27
28 => 010010 => 28
29 => 010011 => 29
30 => 010001 => 30
31 => 010000 => 31
32 => 110000 => 32
=={{header|Sidef}}==
{{trans|Perl}}
func bin2gray(n) {
n ^ (n >> 1);
}
func gray2bin(num) {
var bin = num;
while (num >>= 1) { bin ^= num };
return bin;
}
0..31 -> each { |i|
var gr = bin2gray(i);
printf("%d\t%b\t%b\t%b\n", i, i, gr, gray2bin(gr));
}
=={{header|Standard ML}}==
Word.xorb (b, Word.>> (b, 0w1))
fun gray_decode n =
let
fun aux (p, n) =
if n = 0w0 then p
else aux (Word.xorb (p, n), Word.>> (n, 0w1))
in
aux (n, Word.>> (n, 0w1))
end;
val s = Word.fmt StringCvt.BIN;
fun aux i =
if i = 0w32 then
()
else
let
val g = gray_encode i
val b = gray_decode g
in
print (Word.toString i ^ " :\t" ^ s i ^ " => " ^ s g ^ " => " ^ s b ^ "\t: " ^ Word.toString b ^ "\n");
aux (i + 0w1)
end;
aux 0w0
=={{header|SQL}}==
DECLARE @binary AS NVARCHAR(MAX) = '001010111'
DECLARE @gray AS NVARCHAR(MAX) = ''
--Encoder
SET @gray = LEFT(@binary, 1)
WHILE LEN(@binary) > 1
BEGIN
IF LEFT(@binary, 1) != SUBSTRING(@binary, 2, 1)
SET @gray = @gray + '1'
ELSE
SET @gray = @gray + '0'
SET @binary = RIGHT(@binary, LEN(@binary) - 1)
END
SELECT @gray
--Decoder
SET @binary = LEFT(@gray, 1)
WHILE LEN(@gray) > 1
BEGIN
IF RIGHT(@binary, 1) != SUBSTRING(@gray, 2, 1)
SET @binary = @binary + '1'
ELSE
SET @binary = @binary + '0'
SET @gray = RIGHT(@gray, LEN(@gray) - 1)
END
SELECT @binary
=={{header|Tcl}}==
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:
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]
}
{{out}}
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
=={{header|Ursala}}==
#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
{{out}}
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
=={{header|VHDL}}==
Combinatorial encoder:
USE ieee.std_logic_1164.all;
entity b2g is
port( bin : in std_logic_vector (4 downto 0);
gray : out std_logic_vector (4 downto 0)
);
end b2g ;
architecture rtl of b2g is
constant N : integer := bin'high;
begin
gray <= bin(n) & ( bin(N-1 downto 0) xor bin(N downto 1));
end architecture rtl;
Combinatorial decoder:
USE ieee.std_logic_1164.all;
entity g2b is
port( gray : in std_logic_vector (4 downto 0);
bin : buffer std_logic_vector (4 downto 0)
);
end g2b ;
architecture rtl of g2b is
constant N : integer := bin'high;
begin
bin(N) <= gray(N);
gen_xor: for i in N-1 downto 0 generate
bin(i) <= gray(i) xor bin(i+1);
end generate;
end architecture rtl;
=={{header|XPL0}}==
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);
];
]
{{out}}
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
=={{header|zkl}}==
fcn grayDecode(g){ b:=g; while(g/=2){ b=b.bitXor(g) } b }
g:=grayEncode(n); b:=grayDecode(g);
println("%2d(%05.2B) --> %2d(%05.2B) --> %2d(%05.2B)".fmt(n,n,g,g,b,b));
}
{{out}}
0(00000) --> 0(00000) --> 0(00000)
1(00001) --> 1(00001) --> 1(00001)
2(00010) --> 3(00011) --> 2(00010)
3(00011) --> 2(00010) --> 3(00011)
4(00100) --> 6(00110) --> 4(00100)
5(00101) --> 7(00111) --> 5(00101)
6(00110) --> 5(00101) --> 6(00110)
7(00111) --> 4(00100) --> 7(00111)
8(01000) --> 12(01100) --> 8(01000)
9(01001) --> 13(01101) --> 9(01001)
10(01010) --> 15(01111) --> 10(01010)
11(01011) --> 14(01110) --> 11(01011)
12(01100) --> 10(01010) --> 12(01100)
13(01101) --> 11(01011) --> 13(01101)
14(01110) --> 9(01001) --> 14(01110)
15(01111) --> 8(01000) --> 15(01111)
16(10000) --> 24(11000) --> 16(10000)
17(10001) --> 25(11001) --> 17(10001)
18(10010) --> 27(11011) --> 18(10010)
19(10011) --> 26(11010) --> 19(10011)
20(10100) --> 30(11110) --> 20(10100)
21(10101) --> 31(11111) --> 21(10101)
22(10110) --> 29(11101) --> 22(10110)
23(10111) --> 28(11100) --> 23(10111)
24(11000) --> 20(10100) --> 24(11000)
25(11001) --> 21(10101) --> 25(11001)
26(11010) --> 23(10111) --> 26(11010)
27(11011) --> 22(10110) --> 27(11011)
28(11100) --> 18(10010) --> 28(11100)
29(11101) --> 19(10011) --> 29(11101)
30(11110) --> 17(10001) --> 30(11110)
31(11111) --> 16(10000) --> 31(11111)