Gray code: Difference between revisions

{{trans|Python: on integers}}

R n (+) n >> 1

V gray = gray_encode(i)

V dec = gray_decode(gray)

{{out}}

xra a ; set A=0

loop: push psw ; print number as decimal

jmp 5

arrow: db ' ==> $'

{{out}}

=={{header|Action!}}==

BYTE i

PrintB2(b) PutE()

OD

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Gray_code.png Screenshot from Atari 8-bit computer]

Values are implemented with 8 bits according to representation clause

of Unsigned_8 (check package Interfaces).

use Ada.Text_IO, Interfaces;

New_Line;

end loop;

Check compactness of assembly code generated by GNAT :http://pastebin.com/qtNjeQk9<br>

{{out}}

=={{header|Aime}}==

{{trans|C}}

gray_encode(integer n)

{

p;

Demonstration code:

main(void)

{

return 0;

{{out}}

<pre> 0: 00000 => 00000 => 00000: 0

=={{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

printf (($zd, ": ", 2(2r5d, " >= "), 2r5dl$, i, BIN i, GRAY BIN i, YARG GRAY BIN i))

OD

{{out}}

<pre> 0: 00000 >= 00000 >= 00000

{{trans|C}}

Version: Hopper-BASIC.

#proto GrayEncode(_X_)

#synon _GrayEncode *getGrayEncode

Wend

Return (p)

{{out}}

<pre>

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

{{out}}

<pre style="overflow: auto; height: 20em;">0 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}

{{out}}

<pre>1 1 0 1 0</pre>

=={{header|Arturo}}==

fromGray: function [n][

p: n

pad to :string decoded 2

]

{{out}}

=={{header|AutoHotkey}}==

return n ^ (n >> 1)

}

n:=A_Index-1, out .= n " : " BinString(n) " => " BinString(e:=gray_encode(n))

. " => " BinString(gray_decode(e)) " => " BinString(n) "`n"

{{out}}

<pre style="overflow: auto; height: 20em;">0 : 00000 => 00000 => 00000 => 00000

=={{header|AWK}}==

function bits2str(bits, data, mask)

for (i=0; i < 32; i++)

printf "%-3s => %05d => %05d => %05d\n",i, bits2str(i),bits2str(gray_encode(i)), bits2str(gray_decode(gray_encode(i)))

{{out}}

<pre>0 => 00000 => 00000 => 00000

=={{header|Batch File}}==

:: Batch File Implementation

echo(%%n -^> !bin! -^> !gray! -^> !rebin!

)

{{Out}}

<pre style="overflow: auto; height: 20em;"># -> bin -> enc -> dec

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

PRINT " Decimal Binary Gray Decoded"

DEF FNgraydecode(G%) : LOCAL B%

REPEAT B% EOR= G% : G% = G% >>> 1 : UNTIL G% = 0

=={{header|bc}}==

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

/* encode Gray code */

"

}

{{out}}

=={{header|C}}==

{{trans|Tcl}}

return n ^ (n >> 1);

}

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

return p;

Demonstration code:

/* Simple bool formatter, only good on range 0..31 */

}

return 0;

{{out}}

<pre>

=={{header|C sharp}}==

public class Gray {

}

}

{{out}}

<pre>

=={{header|C++}}==

#include <bitset>

#include <iostream>

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

}

{{out}}

<pre>

=={{header|CoffeeScript}}==

gray_encode = (n) ->

n ^ (n >> 1)

for i in [0..32]

console.log gray_decode gray_encode(i)

=={{header|Common Lisp}}==

(logxor n (ash n -1)))

(loop for i to 31 do

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

{{out}}

=={{header|Component Pascal}}==

BlackBox Component Builder

MODULE GrayCodes;

IMPORT StdLog,SYSTEM;

END GrayCodes.

Execute: ^QGrayCodes.Do<br/>

{{out}}

=={{header|Crystal}}==

{{trans|C}}

def gray_encode(bin)

bin ^ (bin >> 1)

bin

end

Demonstration code:

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

gr = gray_encode n

printf "%2d : %05b => %05b => %05b : %2d\n", n, n, gr, bin, bin

end

{{out}}

<pre>

=={{header|D}}==

return n ^ (n >> 1);

}

assert(d == n);

}

{{out}}

<pre> N N2 enc dec2 dec

then the decode table is calculated and appended.

Same output.

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

writefln("%2d: %5b => %5b : %2d", i, i, encoded, decoded);

}

===Short Functional-Style Generator===

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

void main() {

4.g.writeln;

{{out}}

<pre>["0000", "0001", "0011", "0010", "0110", "0111", "0101", "0100", "1100", "1101", "1111", "1110", "1010", "1011", "1001", "1000"]</pre>

=={{header|Delphi}}==

{{trans|DWScript}}

{$APPTYPE CONSOLE}

Writeln(Format(' %2d %s %s %s %2d', [i, IntToBin(i, 5), IntToBin(g, 5), IntToBin(d, 5), d]));

end;

{{out}}

<pre>

=={{header|DWScript}}==

begin

Result := v xor (v shr 1);

PrintLn(Format(' %2d %s %s %s %2d',

[i, IntToBin(i, 5), IntToBin(g, 5), IntToBin(d, 5), d]));

=={{header|Elixir}}==

{{trans|Erlang}}

use Bitwise

def encode(n), do: bxor(n, bsr(n,1))

d = Gray_code.decode(g)

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

output is the same as "Erlang".

=={{header|Erlang}}==

{{trans|Euphoria}}

-export([encode/1, decode/1]).

decode(0,N) -> N;

decode(G,N) -> decode(G bsr 1, G bxor N).

Demonstration code:

test_encode(N) ->

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

{{out}}

=={{header|Euphoria}}==

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

end function

j = gray_decode(j)

printf(1,"%05d\n",dcb(j))

{{out}}

=={{header|F_Sharp|F#}}==

===The Function===

// Functıons to translate bınary to grey code and vv. Nigel Galloway: December 7th., 2018

let grayCode,invGrayCode=let fN g (n:uint8)=n^^^(n>>>g) in ((fN 1),(fN 1>>fN 2>>fN 4))

===The Task===

{{out}}

<pre>

=={{header|Factor}}==

Translation of C.

IN: rosetta-gray

MAIN: main

Running above code prints:

{ 0 "0" "0" 0 }

{ 1 "1" "1" 1 }

{ 30 "11110" "10001" 30 }

{ 31 "11111" "10000" 31 }

=={{header|Forth}}==

These functions take input parameters from the stack and return the result on the stack.

\ 2/ is Forth divide by 2, ie: shift right 1

: gray> ( n -- n )

loop

decimal ; \ revert to BASE 10

{{out}}

<pre>

=={{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 [[oeis:A003188|direct]] and [[oeis:A006068|inverse]] Gray code :

IMPLICIT NONE

INTEGER IGRAY,I,J,K

10 CONTINUE

S(1:L-K)=''

<pre> 0 : 00000 => 00000 => 00000 : 0

=={{header|FreeBASIC}}==

' compile with: fbc -s console

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> i binary gray gra2bin

=={{header|Frink}}==

Frink has built-in functions to convert to and from binary reflected Gray code.

for i=0 to 31

{

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"

fmt.Printf(" %2d %05b %05b %05b %2d\n", b, b, g, d, d)

}

{{out}}

<pre>

=={{header|Groovy}}==

Solution:

i ^ (i >>> 1)

}

def h = grayDecode(code >>> 1)

return (h << 1) + ((code ^ h) & 1)

Test:

def remainder = i

def bin = []

it, iB[4],iB[3],iB[2],iB[1],iB[0], cB[4],cB[3],cB[2],cB[1],cB[0], decode)

println()

Results:

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

import Data.Char

import Numeric

printf "int: %2d -> bin: %5s -> gray: %5s\n" num bin gray

=={{header|Icon}} and {{header|Unicon}}==

The following works in both languages:

procedure main()

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

return b

Sample run:

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

Thus <code>G2B inv</code> will translate binary to Gray code.

Required example:

G2B=: ~:/\&.|:

(,: ,.@".&.>) 'n';'#:n';'G2B inv#:n';'#.G2B G2B inv#:n'

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

}

}

{{out}}

<pre>

</pre>

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++){

}

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

}

return new BigInteger(result, 2);

=={{header|Javascript}}==

'''Module''' <code>gray-code.js</code>

return number ^ (number >> 1)

}

return number

'''Test'''

import * as gray from './gray-code.js'

decodedGrayCode

))

{{out}}

<pre>

{{works with|Julia|0.6}}

{{trans|C}}

function graydecode(n::Integer)

r = n

end

return r

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

Binary to Gray code

gray:{x[0],xor':x}

/ variant: iterative

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

a:(+allcomb . 5 2)

`0:,/{n:2_sv x;gg:gray x;gb:g2b gg;n2:2_sv gb;

{{out}}

=={{header|Kotlin}}==

object Gray {

println("${Integer.toBinaryString(g)}\t${Gray.decode(g)}")

}

{{out}}

=={{header|Liberty BASIC}}==

for r =0 to 31

print " Decimal "; using( "###", r); " is ";

bin2Dec =t

end function

{{out}}

<pre>

{{trans|Go}}

include "sys.m"; sys: Sys;

}

return s;

{{out}}

=={{header|Lobster}}==

{{trans|C}}

return n ^ (n >> 1)

number_to_string(g, 2, 5) + " ⇾ " +

number_to_string(b, 2, 5) + " : " +

{{out}}

<pre>

=={{header|Logo}}==

{{trans|Euphoria}}

output bitxor :number lshift :number -1

end

]

output :value

Demonstration code, including formatters:

while [(count :str) < :width] [

make "str word :pad :str

print (sentence (format :num 2) ": (binary :num 5) ": (binary :gray 5) ":

(binary :decoded 5) ": (format :decoded 2)) ]

{{out}}

{{trans|Euphoria}}

This code uses the [http://bitop.luajit.org/index.html Lua BitOp] module. Designed to be a module named <tt>gray.lua</tt>.

local bit = require('bit')

end

Demonstration code:

local gray = require 'gray'

to_bit_string(i,5), to_bit_string(g, 5),

to_bit_string(gd,5), gd))

{{out}}

Additions to showing the modules/functions replacement mechanism of M2000

Module Code32 (&code(), &decode()){

Const d$="{0::-2} {1:-6} {2:-6} {3:-6} {4::-2}"

// pass Code32 to GrayCode in place of doit

GrayCode ; doit as Code32

{{out}}

<pre style="overflow: auto; height: 20em;">

=={{header|Mathematica}} / {{header|Wolfram Language}}==

{{out}}

<pre>Required example:

=={{header|MATLAB}}==

%% Gray Code Generator

% this script generates gray codes of n bits

disp(result);

end

{{out}}

The additional <tt>gray.coerce/2</tt> predicate converts the ''representation'' underlying a <tt>gray</tt> value into an <tt>int</tt> 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 <tt>coerce/2</tt> predicate is used for this purpose.

:- interface.

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

The following program tests the above code:

:- interface.

io.format("%8d %8s %8s\n", [i(Number), s(NumBin), s(GrayBin)], !IO).

The <tt>main/2</tt> predicate generates a list of numbers from 0 to 31 inclusive and then checks that conversion is working properly.

=={{header|Nim}}==

{{trans|C}}

n xor (n shr 1)

while t > 0:

t = t shr 1

Demonstration code:

for i in 0 .. 32:

{{out}}

<pre> 0 => 000000 => 0

=={{header|NOWUT}}==

adapted from C

sectiondata

endfunc

returnex $0C ; clean off 3 parameters from the stack

{{out}}

<pre style="overflow: auto; height: 20em;">00 : 00000 => 00000 => 00000

=={{header|OCaml}}==

b lxor (b lsr 1)

let b = gray_decode g in

Printf.printf "%2d : %s => %s => %s : %2d\n" i (s i) (s g) (s b) b

=={{header|PARI/GP}}==

This code may have exposed a bug in PARI 2.4.4: <code>apply(Str, 1)</code> fails.

As a workaround I used a closure: <code>apply(k->Str(k), 1)</code>.

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

{{out}}

<pre>0 0 0 0

=={{header|Perl}}==

{

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

my $gr= bin2gray($_);

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

=={{header|Phix}}==

{{Trans|Delphi}} (turned out to be almost the same as Euphoria)

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">gray_encode</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d %05b %05b %2d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

=={{header|PHP}}==

<?php

printf("%2d : %05b => %05b => %05b : %2d \n",$i, $i, $gray_encoded, $gray_encoded, gray_decode($gray_encoded));

}

{{out}}

<pre>

=={{header|Picat}}==

foreach(I in 0..2**5-1)

G = gray_encode1(I),

P := P ^ N,

N := N >> 1

{{out}}

=={{header|PicoLisp}}==

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

(mapcar

'((C) (setq X (x| X (format C))))

Test:

(for I (range 0 31)

(let G (grayEncode I)

{{out}}

<pre> Binary Gray Decoded

=={{header|PL/I}}==

Gray_code: procedure options (main); /* 15 November 2013 */

declare (bin(0:31), g(0:31), b2(0:31)) bit (5);

put skip edit (i, bin(i), g(i), b2(i)) (f(2), 3(x(1), b));

end;

<pre>

0 00000 00000 00000

=={{header|PowerBASIC}}==

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

end function

g%=gray%(n%)

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

=={{header|Prolog}}==

{{works with|SWI Prolog}}

{{works with|YAP}}

N0 is N >> 1,

G is N xor N0.

from_gray(S, N0),

N is G xor N0

=== Test Code ===

{{works with|SWI Prolog}}

{{works with|YAP}}

to_gray(N, G) :-

maplist(write_record, Numbers, Grays, Decodeds).

go :- halt(1).

{{out}}

=={{header|PureBasic}}==

ProcedureReturn n ! (n >> 1)

EndProcedure

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

{{out}}

<pre>Number Gray Binary Decoded

===Python: on integers===

Works with python integers

return n ^ n >> 1

gray = gray_encode(i)

dec = gray_decode(gray)

{{out}}

;First some int<>bin conversion routines:

'From positive integer to list of binary bits, msb at index 0'

if n:

for bit in bits:

i = i * 2 + bit

;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:])]

b = [bits[0]]

for nextb in bits[1:]: b.append(b[-1] ^ nextb)

;Sample output

print('int:%2i -> bin:%12r -> gray:%12r -> bin:%12r -> int:%2i' %

( i,

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|Quackery}}==

[ dup

i^ encodegray dup 5 echobin

say " -> "

{{out}}

=={{header|R}}==

GrayEncode <- function(binary) {

gray <- substr(binary,1,1)

return (binary)

}

=={{header|Racket}}==

#lang racket

(~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}}

<pre style="overflow: auto; height: 20em;">> (show-table)

=={{header|Raku}}==

(formerly Perl 6)

sub gray_encode ( Int $n --> Int ) {

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

die if $d != $n;

}

{{out}}

=={{header|REXX}}==

The leading zeroes for the binary numbers and the gray code could've easily been elided.

parse arg N . /*get the optional argument from the CL*/

if N=='' | N=="," then N=31 /*Not specified? Then use the default.*/

end /*g*/ /* ↑ */

/* │ */

'''output''' &nbsp; when using the default input:

<pre>

=={{header|Ring}}==

# Project : Gray code

result = result + string(binary)

return result

Output:

<pre>

<tt>Integer#from_gray</tt> 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

printf "%2d : %5b => %5b => %5b : %2d\n",

number, number, encoded, decoded, decoded

{{out}}

<pre style="overflow: auto; height: 20em;">

=={{header|Rust}}==

{{works with|Rust|1.1}}

(integer >> 1) ^ integer

}

}

=={{header|Scala}}==

The <code>scanLeft</code> 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. <code>tail</code> removes the "0" we added as the initial accumulator value, and <code>mkString</code> 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)

for (i <- 0 to 31; g = encode(i))

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

{{out}}

<pre style="overflow: auto; height: 20em;">decimal binary gray decoded

</pre>

Alternatively, more imperative style:

def decode(n: Long) = {

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

<pre style="overflow: auto; height: 20em;">decimal binary gray decoded

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";

writeln(i <& " => " <& grayEncode(i) radix 2 lpad0 6 <& " => " <& grayDecode(grayEncode(i)));

end for;

{{out}}

=={{header|SenseTalk}}==

Note: Inputs and outputs as strings

function BinaryToGray param1