Gray code: Difference between revisions
Content added Content deleted
(Updated to compile with Nim 1.4. Changed somewhat the presentation fo result.) |
Drkameleon (talk | contribs) No edit summary |
||
Line 1: | Line 1: | ||
=={{header|Arturo}}== |
|||
{{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. |
|||
<lang rebol>toGray: function [n]-> xor n shr n 1 |
|||
fromGray: function [n][ |
|||
Create functions to encode a number to and decode a number from Gray code. |
|||
p: n |
|||
while [n > 0][ |
|||
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). |
|||
n: shr n 1 |
|||
p: xor p n |
|||
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): |
|||
<pre>if b[i-1] = 1 |
|||
g[i] = not b[i] |
|||
else |
|||
g[i] = b[i]</pre> |
|||
Or: |
|||
<pre>g = b xor (b logically right shifted 1 time)</pre> |
|||
Decoding (MSB is bit 0, b is binary, g is Gray code): |
|||
<pre>b[0] = g[0] |
|||
for other bits: |
|||
b[i] = g[i] xor b[i-1]</pre> |
|||
;Reference |
|||
* [http://www.wisc-online.com/Objects/ViewObject.aspx?ID=IAU8307 Converting Between Gray and Binary Codes]. It includes step-by-step animations. |
|||
=={{header|8080 Assembly}}== |
|||
<lang 8080asm> org 100h |
|||
xra a ; set A=0 |
|||
loop: push psw ; print number as decimal |
|||
call decout |
|||
call padding ; print padding |
|||
pop psw |
|||
push psw |
|||
call binout ; print number as binary |
|||
call padding |
|||
pop psw |
|||
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
mov b,a ; gray encode |
|||
ana a ; clear carry |
|||
rar ; shift right |
|||
xra b ; xor the original |
|||
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
push psw |
|||
call binout ; print gray number as binary |
|||
call padding |
|||
pop psw |
|||
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
mov b,a ; gray decode |
|||
decode: ana a ; clear carry |
|||
jz done ; when no more bits are left, stop |
|||
rar ; shift right |
|||
mov c,a ; keep that value |
|||
xra b ; xor into output value |
|||
mov b,a ; that is the output value |
|||
mov a,c ; restore intermediate |
|||
jmp decode ; do next bit |
|||
done: mov a,b ; give output value |
|||
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
|||
push psw |
|||
call binout ; print decoded number as binary |
|||
call padding |
|||
pop psw |
|||
push psw |
|||
call decout ; print decoded number as decimal |
|||
lxi d,nl |
|||
call strout |
|||
pop psw |
|||
inr a ; next number |
|||
ani 1fh ; are we there yet? |
|||
jnz loop ; if not, do next number |
|||
ret |
|||
;; Print A as two-digit number |
|||
decout: mvi c,10 |
|||
call dgtout |
|||
mvi c,1 |
|||
dgtout: mvi e,'0' - 1 |
|||
dgtloop: inr e |
|||
sub c |
|||
jnc dgtloop |
|||
add c |
|||
push psw |
|||
mvi c,2 |
|||
call 5 |
|||
pop psw |
|||
ret |
|||
;; Print A as five-bit binary number |
|||
binout: ani 1fh |
|||
ral |
|||
ral |
|||
ral |
|||
mvi c,5 |
|||
binloop: ral |
|||
push psw |
|||
push b |
|||
mvi c,2 |
|||
mvi a,0 |
|||
aci '0' |
|||
mov e,a |
|||
call 5 |
|||
pop b |
|||
pop psw |
|||
dcr c |
|||
jnz binloop |
|||
ret |
|||
;; Print padding |
|||
padding: lxi d,arrow |
|||
strout: mvi c,9 |
|||
jmp 5 |
|||
arrow: db ' ==> $' |
|||
nl: db 13,10,'$'</lang> |
|||
{{out}} |
|||
<pre> |
|||
00 ==> 00000 ==> 00000 ==> 00000 ==> 00 |
|||
01 ==> 00001 ==> 00001 ==> 00001 ==> 01 |
|||
02 ==> 00010 ==> 00011 ==> 00010 ==> 02 |
|||
03 ==> 00011 ==> 00010 ==> 00011 ==> 03 |
|||
04 ==> 00100 ==> 00110 ==> 00100 ==> 04 |
|||
05 ==> 00101 ==> 00111 ==> 00101 ==> 05 |
|||
06 ==> 00110 ==> 00101 ==> 00110 ==> 06 |
|||
07 ==> 00111 ==> 00100 ==> 00111 ==> 07 |
|||
08 ==> 01000 ==> 01100 ==> 01000 ==> 08 |
|||
09 ==> 01001 ==> 01101 ==> 01001 ==> 09 |
|||
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 |
|||
</pre> |
|||
=={{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). |
|||
<lang Ada>with Ada.Text_IO, Interfaces; |
|||
use Ada.Text_IO, Interfaces; |
|||
procedure Gray is |
|||
Bits : constant := 5; -- Change only this line for 6 or 7-bit encodings |
|||
subtype Values is Unsigned_8 range 0 .. 2 ** Bits - 1; |
|||
package Values_Io is new Ada.Text_IO.Modular_IO (Values); |
|||
function Encode (Binary : Values) return Values is |
|||
begin |
|||
return Binary xor Shift_Right (Binary, 1); |
|||
end Encode; |
|||
pragma Inline (Encode); |
|||
function Decode (Gray : Values) return Values is |
|||
Binary, Bit : Values; |
|||
Mask : Values := 2 ** (Bits - 1); |
|||
begin |
|||
Bit := Gray and Mask; |
|||
Binary := Bit; |
|||
for I in 2 .. Bits loop |
|||
Bit := Shift_Right (Bit, 1); |
|||
Mask := Shift_Right (Mask, 1); |
|||
Bit := (Gray and Mask) xor Bit; |
|||
Binary := Binary + Bit; |
|||
end loop; |
|||
return Binary; |
|||
end Decode; |
|||
pragma Inline (Decode); |
|||
HT : constant Character := Character'Val (9); |
|||
J : Values; |
|||
begin |
|||
Put_Line ("Num" & HT & "Binary" & HT & HT & "Gray" & HT & HT & "decoded"); |
|||
for I in Values'Range loop |
|||
J := Encode (I); |
|||
Values_Io.Put (I, 4); |
|||
Put (": " & HT); |
|||
Values_Io.Put (I, Bits + 2, 2); |
|||
Put (" =>" & HT); |
|||
Values_Io.Put (J, Bits + 2, 2); |
|||
Put (" => " & HT); |
|||
Values_Io.Put (Decode (J), 4); |
|||
New_Line; |
|||
end loop; |
|||
end Gray;</lang> |
|||
Check compactness of assembly code generated by GNAT :http://pastebin.com/qtNjeQk9<br> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;">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</pre> |
|||
=={{header|Aime}}== |
|||
{{trans|C}} |
|||
<lang aime>integer |
|||
gray_encode(integer n) |
|||
{ |
|||
n ^ (n >> 1); |
|||
} |
|||
integer |
|||
gray_decode(integer n) |
|||
{ |
|||
integer p; |
|||
p = n; |
|||
while (n >>= 1) { |
|||
p ^= n; |
|||
} |
|||
p; |
|||
}</lang> |
|||
Demonstration code: |
|||
<lang aime>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; |
|||
}</lang> |
|||
{{out}} |
|||
<pre> 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</pre> |
|||
=={{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. |
|||
<lang algol68>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</lang> |
|||
{{out}} |
|||
<pre> 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 |
|||
</pre> |
|||
=={{header|APL}}== |
|||
Generate the complete N-bit Gray sequence as a matrix:<sup>[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]</sup> |
|||
<lang apl>N←5 |
|||
({(0,⍵)⍪1,⊖⍵}⍣N)(1 0⍴⍬)</lang> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;">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</pre> |
|||
Encode and decode an individual integer:<sup>[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]</sup> |
|||
<lang apl>N←5 |
|||
grayEncode←{a≠N↑(0,a←(N⍴2)⊤⍵)} |
|||
grayDecode←{2⊥≠⌿N N↑N(2×N)⍴⍵,0,N⍴0} |
|||
grayEncode 19</lang> |
|||
{{out}} |
|||
<pre>1 1 0 1 0</pre> |
|||
=={{header|AutoHotkey}}== |
|||
<lang AHK>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</lang> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;">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</pre> |
|||
=={{header|AWK}}== |
|||
<lang awk># Tested using GAWK |
|||
function bits2str(bits, data, mask) |
|||
{ |
|||
# Source: https://www.gnu.org/software/gawk/manual/html_node/Bitwise-Functions.html |
|||
if (bits == 0) |
|||
return "0" |
|||
mask = 1 |
|||
for (; bits != 0; bits = rshift(bits, 1)) |
|||
data = (and(bits, mask) ? "1" : "0") data |
|||
while ((length(data) % 8) != 0) |
|||
data = "0" data |
|||
return data |
|||
} |
|||
function gray_encode(n){ |
|||
# Source: https://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code |
|||
return xor(n,rshift(n,1)) |
|||
} |
|||
function gray_decode(n){ |
|||
# Source: https://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code |
|||
mask = rshift(n,1) |
|||
while(mask != 0){ |
|||
n = xor(n,mask) |
|||
mask = rshift(mask,1) |
|||
} |
|||
return n |
|||
} |
|||
BEGIN{ |
|||
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))) |
|||
}</lang> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|Batch File}}== |
|||
<lang dos>:: Gray Code Task from Rosetta Code |
|||
:: Batch File Implementation |
|||
@echo off |
|||
rem -------------- define batch file macros with parameters appended |
|||
rem more info: https://www.dostips.com/forum/viewtopic.php?f=3&t=2518 |
|||
setlocal disabledelayedexpansion % == required for macro ==% |
|||
(set \n=^^^ |
|||
%== this creates escaped line feed for macro ==% |
|||
) |
|||
rem convert to binary (unsigned) |
|||
rem argument: natnum bitlength outputvar |
|||
rem note: if natnum is negative, then !outputvar! is empty |
|||
set tobinary=for %%# in (1 2) do if %%#==2 ( %\n% |
|||
for /f "tokens=1,2,3" %%a in ("!args!") do ( %\n% |
|||
set "natnum=%%a"^&set "bitlength=%%b"^&set "outputvar=%%c") %\n% |
|||
set "!outputvar!=" %\n% |
|||
if !natnum! geq 0 ( %\n% |
|||
set "currnum=!natnum!" %\n% |
|||
for /l %%m in (1,1,!bitlength!) do ( %\n% |
|||
set /a "bit=!currnum!%%2" %\n% |
|||
for %%v in (!outputvar!) do set "!outputvar!=!bit!!%%v!" %\n% |
|||
set /a "currnum/=2" %\n% |
|||
) %\n% |
|||
) %\n% |
|||
) else set args= |
|||
goto :main-thing %== jump to the main thing ==% |
|||
rem -------------- usual "call" sections |
|||
rem the sad disadvantage of using these is that they are slow (TnT) |
|||
rem gray code encoder |
|||
rem argument: natnum outputvar |
|||
:encoder |
|||
set /a "%~2=%~1^(%~1>>1)" |
|||
goto :eof |
|||
rem gray code decoder |
|||
rem argument: natnum outputvar |
|||
:decoder |
|||
set "inp=%~1" & set "%~2=0" |
|||
:while-loop-1 |
|||
if %inp% gtr 0 ( |
|||
set /a "%~2^=%inp%, inp>>=1" |
|||
goto while-loop-1 |
|||
) |
|||
goto :eof |
|||
rem -------------- main thing |
|||
:main-thing |
|||
setlocal enabledelayedexpansion |
|||
echo(# -^> bin -^> enc -^> dec |
|||
for /l %%n in (0,1,31) do ( |
|||
%tobinary% %%n 5 bin |
|||
call :encoder "%%n" "enc" |
|||
%tobinary% !enc! 5 gray |
|||
call :decoder "!enc!" "dec" |
|||
%tobinary% !dec! 5 rebin |
|||
echo(%%n -^> !bin! -^> !gray! -^> !rebin! |
|||
) |
|||
exit /b 0</lang> |
|||
{{Out}} |
|||
<pre style="overflow: auto; height: 20em;"># -> bin -> enc -> dec |
|||
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</pre> |
|||
=={{header|BBC BASIC}}== |
|||
{{works with|BBC BASIC for Windows}} |
|||
<lang bbcbasic> INSTALL @lib$+"STRINGLIB" |
|||
PRINT " Decimal Binary Gray Decoded" |
|||
FOR number% = 0 TO 31 |
|||
gray% = FNgrayencode(number%) |
|||
PRINT number% " " FN_tobase(number%, 2, 5) ; |
|||
PRINT " " FN_tobase(gray%, 2, 5) FNgraydecode(gray%) |
|||
NEXT |
|||
END |
|||
DEF FNgrayencode(B%) = B% EOR (B% >>> 1) |
|||
DEF FNgraydecode(G%) : LOCAL B% |
|||
REPEAT B% EOR= G% : G% = G% >>> 1 : UNTIL G% = 0 |
|||
= B%</lang> |
|||
=={{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. |
|||
<lang bc>scale = 0 /* to use integer division */ |
|||
/* encode Gray code */ |
|||
define e(i) { |
|||
auto h, r |
|||
if (i <= 0) return 0 |
|||
h = i / 2 |
|||
r = e(h) * 2 /* recurse */ |
|||
if (h % 2 != i % 2) r += 1 /* xor low bits of h, i */ |
|||
return r |
|||
} |
|||
/* decode Gray code */ |
|||
define d(i) { |
|||
auto h, r |
|||
if (i <= 0) return 0 |
|||
h = d(i / 2) /* recurse */ |
|||
r = h * 2 |
|||
if (h % 2 != i % 2) r += 1 /* xor low bits of h, i */ |
|||
return r |
|||
} |
|||
/* print i as 5 binary digits */ |
|||
define p(i) { |
|||
auto d, d[] |
|||
for (d = 0; d <= 4; d++) { |
|||
d[d] = i % 2 |
|||
i /= 2 |
|||
} |
|||
for (d = 4; d >= 0; d--) { |
|||
if(d[d] == 0) "0" |
|||
if(d[d] == 1) "1" |
|||
} |
|||
} |
|||
for (i = 0; i < 32; i++) { |
|||
/* original */ t = p(i); " => " |
|||
/* encoded */ e = e(i); t = p(e); " => " |
|||
/* decoded */ d = d(e); t = p(d); " |
|||
" |
|||
} |
|||
quit</lang> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;">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</pre> |
|||
=={{header|C}}== |
|||
{{trans|Tcl}} |
|||
<lang c>int gray_encode(int n) { |
|||
return n ^ (n >> 1); |
|||
} |
|||
int gray_decode(int n) { |
|||
int p = n; |
|||
while (n >>= 1) p ^= n; |
|||
return p; |
|||
}</lang> |
|||
Demonstration code: |
|||
<lang c>#include <stdio.h> |
|||
/* Simple bool formatter, only good on range 0..31 */ |
|||
void fmtbool(int n, char *buf) { |
|||
char *b = buf + 5; |
|||
*b=0; |
|||
do { |
|||
*--b = '0' + (n & 1); |
|||
n >>= 1; |
|||
} while (b != buf); |
|||
} |
|||
int main(int argc, char **argv) { |
|||
int i,g,b; |
|||
char bi[6],bg[6],bb[6]; |
|||
for (i=0 ; i<32 ; i++) { |
|||
g = gray_encode(i); |
|||
b = gray_decode(g); |
|||
fmtbool(i,bi); fmtbool(g,bg); fmtbool(b,bb); |
|||
printf("%2d : %5s => %5s => %5s : %2d\n", i, bi, bg, bb, b); |
|||
} |
|||
return 0; |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|C sharp}}== |
|||
<lang 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)))); |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|C++}}== |
|||
<lang cpp> |
|||
#include <bitset> |
|||
#include <iostream> |
|||
#include <string> |
|||
#include <assert.h> |
|||
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"; |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|CoffeeScript}}== |
|||
<lang 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) |
|||
</lang> |
|||
=={{header|Common Lisp}}== |
|||
<lang 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)))</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Component Pascal}}== |
|||
BlackBox Component Builder |
|||
<lang oberon2> |
|||
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. |
|||
</lang> |
|||
Execute: ^QGrayCodes.Do<br/> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Crystal}}== |
|||
{{trans|C}} |
|||
<lang ruby> |
|||
def gray_encode(bin) |
|||
bin ^ (bin >> 1) |
|||
end |
|||
def gray_decode(gray) |
|||
bin = gray |
|||
while gray > 0 |
|||
gray >>= 1 |
|||
bin ^= gray |
|||
end |
|||
bin |
|||
end |
|||
</lang> |
|||
Demonstration code: |
|||
<lang ruby> |
|||
(0..31).each do |n| |
|||
gr = gray_encode n |
|||
bin = gray_decode gr |
|||
printf "%2d : %05b => %05b => %05b : %2d\n", n, n, gr, bin, bin |
|||
end |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|D}}== |
|||
<lang 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); |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> 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</pre> |
|||
===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. |
|||
<lang d>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] ~= cast(T)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); |
|||
} |
|||
}</lang> |
|||
===Short Functional-Style Generator=== |
|||
<lang d>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; |
|||
}</lang> |
|||
{{out}} |
|||
<pre>["0000", "0001", "0011", "0010", "0110", "0111", "0101", "0100", "1100", "1101", "1111", "1110", "1010", "1011", "1001", "1000"]</pre> |
|||
=={{header|Delphi}}== |
|||
{{trans|DWScript}} |
|||
<lang delphi>program GrayCode; |
|||
{$APPTYPE CONSOLE} |
|||
uses SysUtils; |
|||
function Encode(v: Integer): Integer; |
|||
begin |
|||
Result := v xor (v shr 1); |
|||
end; |
|||
function Decode(v: Integer): Integer; |
|||
begin |
|||
Result := 0; |
|||
while v > 0 do |
|||
begin |
|||
Result := Result xor v; |
|||
v := v shr 1; |
|||
end; |
|||
end; |
|||
function IntToBin(aValue: LongInt; aDigits: Integer): string; |
|||
begin |
|||
Result := StringOfChar('0', aDigits); |
|||
while aValue > 0 do |
|||
begin |
|||
if (aValue and 1) = 1 then |
|||
Result[aDigits] := '1'; |
|||
Dec(aDigits); |
|||
aValue := aValue shr 1; |
|||
end; |
|||
end; |
|||
var |
|||
i, g, d: Integer; |
|||
begin |
|||
Writeln('decimal binary gray decoded'); |
|||
for i := 0 to 31 do |
|||
begin |
|||
g := Encode(i); |
|||
d := Decode(g); |
|||
Writeln(Format(' %2d %s %s %s %2d', [i, IntToBin(i, 5), IntToBin(g, 5), IntToBin(d, 5), d])); |
|||
end; |
|||
end.</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|DWScript}}== |
|||
<lang delphi>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;</lang> |
|||
=={{header|Elixir}}== |
|||
{{trans|Erlang}} |
|||
<lang elixir>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)</lang> |
|||
output is the same as "Erlang". |
|||
=={{header|Erlang}}== |
|||
{{trans|Euphoria}} |
|||
<lang erlang>-module(gray). |
|||
-export([encode/1, decode/1]). |
|||
encode(N) -> N bxor (N bsr 1). |
|||
decode(G) -> decode(G,0). |
|||
decode(0,N) -> N; |
|||
decode(G,N) -> decode(G bsr 1, G bxor N). |
|||
</lang> |
|||
Demonstration code: |
|||
<lang erlang>-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).</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Euphoria}}== |
|||
<lang 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</lang> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|F_Sharp|F#}}== |
|||
===The Function=== |
|||
<lang fsharp> |
|||
// 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)) |
|||
</lang> |
|||
===The Task=== |
|||
<lang fsharp> |
|||
[0uy..31uy]|>List.iter(fun n->let g=grayCode n in printfn "%2d -> %5s (%2d) -> %2d" n (System.Convert.ToString(g,2)) g (invGrayCode g))</lang> |
|||
{{out}} |
|||
<pre> |
|||
0 -> 0 ( 0) -> 0 |
|||
1 -> 1 ( 1) -> 1 |
|||
2 -> 11 ( 3) -> 2 |
|||
3 -> 10 ( 2) -> 3 |
|||
4 -> 110 ( 6) -> 4 |
|||
5 -> 111 ( 7) -> 5 |
|||
6 -> 101 ( 5) -> 6 |
|||
7 -> 100 ( 4) -> 7 |
|||
8 -> 1100 (12) -> 8 |
|||
9 -> 1101 (13) -> 9 |
|||
10 -> 1111 (15) -> 10 |
|||
11 -> 1110 (14) -> 11 |
|||
12 -> 1010 (10) -> 12 |
|||
13 -> 1011 (11) -> 13 |
|||
14 -> 1001 ( 9) -> 14 |
|||
15 -> 1000 ( 8) -> 15 |
|||
16 -> 11000 (24) -> 16 |
|||
17 -> 11001 (25) -> 17 |
|||
18 -> 11011 (27) -> 18 |
|||
19 -> 11010 (26) -> 19 |
|||
20 -> 11110 (30) -> 20 |
|||
21 -> 11111 (31) -> 21 |
|||
22 -> 11101 (29) -> 22 |
|||
23 -> 11100 (28) -> 23 |
|||
24 -> 10100 (20) -> 24 |
|||
25 -> 10101 (21) -> 25 |
|||
26 -> 10111 (23) -> 26 |
|||
27 -> 10110 (22) -> 27 |
|||
28 -> 10010 (18) -> 28 |
|||
29 -> 10011 (19) -> 29 |
|||
30 -> 10001 (17) -> 30 |
|||
31 -> 10000 (16) -> 31 |
|||
</pre> |
|||
=={{header|Factor}}== |
|||
Translation of C. |
|||
<lang factor>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 |
|||
</lang> |
|||
Running above code prints: |
|||
<lang factor>{ -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 }</lang> |
|||
=={{header|Forth}}== |
|||
As a low level language Forth provides efficient bit manipulation operators. |
|||
These functions take input parameters from the stack and return the result on the stack. |
|||
<lang forth>: >gray ( n -- n' ) dup 2/ xor ; \ n' = n xor (n logically right shifted 1 time) |
|||
\ 2/ is Forth divide by 2, ie: shift right 1 |
|||
: gray> ( n -- n ) |
|||
0 1 31 lshift ( -- g b mask ) |
|||
begin |
|||
>r \ save a copy of mask on return stack |
|||
2dup 2/ xor |
|||
r@ and or |
|||
r> 1 rshift |
|||
dup 0= |
|||
until |
|||
drop nip ; \ clean the parameter stack leaving result only |
|||
: test |
|||
2 base ! \ set system number base to 2. ie: Binary |
|||
32 0 do |
|||
cr I dup 5 .r ." ==> " \ print numbers (binary) right justified 5 places |
|||
>gray dup 5 .r ." ==> " |
|||
gray> 5 .r |
|||
loop |
|||
decimal ; \ revert to BASE 10 |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
FORTH> test |
|||
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 ok</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 : |
|||
<lang fortran> PROGRAM GRAY |
|||
IMPLICIT NONE |
|||
INTEGER IGRAY,I,J,K |
|||
CHARACTER*5 A,B,C |
|||
DO 10 I=0,31 |
|||
J=IGRAY(I,1) |
|||
K=IGRAY(J,-1) |
|||
CALL BINARY(A,I,5) |
|||
CALL BINARY(B,J,5) |
|||
CALL BINARY(C,K,5) |
|||
PRINT 99,I,A,B,C,K |
|||
10 CONTINUE |
|||
99 FORMAT(I2,3H : ,A5,4H => ,A5,4H => ,A5,3H : ,I2) |
|||
END |
|||
FUNCTION IGRAY(N,D) |
|||
IMPLICIT NONE |
|||
INTEGER D,K,N,IGRAY |
|||
IF(D.LT.0) GO TO 10 |
|||
IGRAY=IEOR(N,ISHFT(N,-1)) |
|||
RETURN |
|||
10 K=N |
|||
IGRAY=0 |
|||
20 IGRAY=IEOR(IGRAY,K) |
|||
K=K/2 |
|||
IF(K.NE.0) GO TO 20 |
|||
END |
|||
SUBROUTINE BINARY(S,N,K) |
|||
IMPLICIT NONE |
|||
INTEGER I,K,L,N |
|||
CHARACTER*(*) S |
|||
L=LEN(S) |
|||
DO 10 I=0,K-1 |
|||
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</lang> |
|||
<pre> 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</pre> |
|||
=={{header|FreeBASIC}}== |
|||
<lang freebasic>' version 18-01-2017 |
|||
' compile with: fbc -s console |
|||
Function gray2bin(g As UInteger) As UInteger |
|||
Dim As UInteger b = g |
|||
While g |
|||
g Shr= 1 |
|||
b Xor= g |
|||
Wend |
|||
Return b |
|||
End Function |
|||
Function bin2gray(b As UInteger) As UInteger |
|||
Return b Xor (b Shr 1) |
|||
End Function |
|||
' ------=< MAIN >=------ |
|||
Dim As UInteger i |
|||
Print " i binary gray gra2bin" |
|||
Print String(32,"=") |
|||
For i = 0 To 31 |
|||
Print Using "## --> "; i; |
|||
print Bin(i,5); " --> "; |
|||
Print Bin(bin2gray(i),5); " --> "; |
|||
Print Bin(gray2bin(bin2gray(i)),5) |
|||
Next |
|||
' empty keyboard buffer |
|||
While Inkey <> "" : Wend |
|||
Print : Print "hit any key to end program" |
|||
Sleep |
|||
End</lang> |
|||
{{out}} |
|||
<pre> i binary gray gra2bin |
|||
================================ |
|||
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</pre> |
|||
=={{header|Frink}}== |
|||
Frink has built-in functions to convert to and from binary reflected Gray code. |
|||
<lang frink> |
|||
for i=0 to 31 |
|||
{ |
|||
gray = binaryToGray[i] |
|||
back = grayToBinary[gray] |
|||
println[(i->binary) + "\t" + (gray->binary) + "\t" + (back->binary)] |
|||
} |
|||
</lang> |
|||
=={{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. |
|||
<lang go>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) |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Groovy}}== |
|||
Solution: |
|||
<lang groovy>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) |
|||
}</lang> |
|||
Test: |
|||
<lang groovy>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() |
|||
}</lang> |
|||
Results: |
|||
<pre style="overflow: auto; height: 20em;">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</pre> |
|||
=={{header|Haskell}}== |
|||
For zero padding, replace the %5s specifiers in the format string with %05s. |
|||
<lang Haskell>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</lang> |
|||
=={{header|Icon}} and {{header|Unicon}}== |
|||
The following works in both languages: |
|||
<lang unicon>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</lang> |
|||
Sample run: |
|||
<pre> |
|||
->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 |
|||
-> |
|||
</pre> |
|||
=={{header|J}}== |
|||
<code>G2B</code> is an invertible function which will translate Gray code to Binary: |
|||
<lang j>G2B=: ~:/\&.|:</lang> |
|||
Thus <code>G2B inv</code> will translate binary to Gray code. |
|||
Required example: |
|||
<lang j> n=:i.32 |
|||
G2B=: ~:/\&.|: |
|||
(,: ,.@".&.>) 'n';'#:n';'G2B inv#:n';'#.G2B G2B inv#:n' |
|||
+--+---------+----------+----------------+ |
|||
|n |#:n |G2B inv#:n|#.G2B G2B inv#:n| |
|||
+--+---------+----------+----------------+ |
|||
| 0|0 0 0 0 0|0 0 0 0 0 | 0 | |
|||
| 1|0 0 0 0 1|0 0 0 0 1 | 1 | |
|||
| 2|0 0 0 1 0|0 0 0 1 1 | 2 | |
|||
| 3|0 0 0 1 1|0 0 0 1 0 | 3 | |
|||
| 4|0 0 1 0 0|0 0 1 1 0 | 4 | |
|||
| 5|0 0 1 0 1|0 0 1 1 1 | 5 | |
|||
| 6|0 0 1 1 0|0 0 1 0 1 | 6 | |
|||
| 7|0 0 1 1 1|0 0 1 0 0 | 7 | |
|||
| 8|0 1 0 0 0|0 1 1 0 0 | 8 | |
|||
| 9|0 1 0 0 1|0 1 1 0 1 | 9 | |
|||
|10|0 1 0 1 0|0 1 1 1 1 |10 | |
|||
|11|0 1 0 1 1|0 1 1 1 0 |11 | |
|||
|12|0 1 1 0 0|0 1 0 1 0 |12 | |
|||
|13|0 1 1 0 1|0 1 0 1 1 |13 | |
|||
|14|0 1 1 1 0|0 1 0 0 1 |14 | |
|||
|15|0 1 1 1 1|0 1 0 0 0 |15 | |
|||
|16|1 0 0 0 0|1 1 0 0 0 |16 | |
|||
|17|1 0 0 0 1|1 1 0 0 1 |17 | |
|||
|18|1 0 0 1 0|1 1 0 1 1 |18 | |
|||
|19|1 0 0 1 1|1 1 0 1 0 |19 | |
|||
|20|1 0 1 0 0|1 1 1 1 0 |20 | |
|||
|21|1 0 1 0 1|1 1 1 1 1 |21 | |
|||
|22|1 0 1 1 0|1 1 1 0 1 |22 | |
|||
|23|1 0 1 1 1|1 1 1 0 0 |23 | |
|||
|24|1 1 0 0 0|1 0 1 0 0 |24 | |
|||
|25|1 1 0 0 1|1 0 1 0 1 |25 | |
|||
|26|1 1 0 1 0|1 0 1 1 1 |26 | |
|||
|27|1 1 0 1 1|1 0 1 1 0 |27 | |
|||
|28|1 1 1 0 0|1 0 0 1 0 |28 | |
|||
|29|1 1 1 0 1|1 0 0 1 1 |29 | |
|||
|30|1 1 1 1 0|1 0 0 0 1 |30 | |
|||
|31|1 1 1 1 1|1 0 0 0 0 |31 | |
|||
+--+---------+----------+----------------+</lang> |
|||
=={{header|Java}}== |
|||
{{trans|C}} |
|||
<lang java> |
|||
public class Gray { |
|||
public static long grayEncode(long n){ |
|||
return n ^ (n >>> 1); |
|||
} |
|||
public static long grayDecode(long n) { |
|||
long p = n; |
|||
while ((n >>>= 1) != 0) |
|||
p ^= n; |
|||
return p; |
|||
} |
|||
public static void main(String[] args){ |
|||
System.out.println("i\tBinary\tGray\tDecoded"); |
|||
for(int i = -1; i < 32;i++){ |
|||
System.out.print(i +"\t"); |
|||
System.out.print(Integer.toBinaryString(i) + "\t"); |
|||
System.out.print(Long.toBinaryString(grayEncode(i))+ "\t"); |
|||
System.out.println(grayDecode(grayEncode(i))); |
|||
} |
|||
} |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
Here is an example encoding function that does it in a bit-by-bit, more human way: |
|||
<lang java>public static long grayEncode(long n){ |
|||
long result = 0; |
|||
for(int exp = 0; n > 0; n /= 2, exp++){ |
|||
long nextHighestBit = (n >> 1) & 1; |
|||
if(nextHighestBit == 1){ |
|||
result += ((n & 1) == 0) ? (1 << exp) : 0; //flip the bit |
|||
}else{ |
|||
result += (n & 1) * (1 << exp); //"n & 1" is "this bit", don't flip it |
|||
} |
|||
} |
|||
return result; |
|||
}</lang> |
|||
This decoding function should work for gray codes of any size: |
|||
{{untested}} |
|||
<lang java>public static BigInteger grayDecode(BigInteger n){ |
|||
String nBits = n.toString(2); |
|||
String result = nBits.substring(0, 1); |
|||
for(int i = 1; i < nBits.length(); i++){ |
|||
//bin[i] = gray[i] ^ bin[i-1] |
|||
//XOR with characters |
|||
result += nBits.charAt(i) != result.charAt(i - 1) ? "1" : "0"; |
|||
} |
|||
return new BigInteger(result, 2); |
|||
}</lang> |
|||
=={{header|Javascript}}== |
|||
The following code is '''ES2015.''' |
|||
'''Module''' <code>gray-code.js</code> |
|||
<lang javascript>export function encode (number) { |
|||
return number ^ (number >> 1) |
|||
} |
|||
export function decode (encodedNumber) { |
|||
let number = encodedNumber |
|||
while (encodedNumber >>= 1) { |
|||
number ^= encodedNumber |
|||
} |
|||
return number |
|||
}</lang> |
|||
'''Test''' |
|||
<lang javascript>import printf from 'printf' // Module must be installed with npm first |
|||
import * as gray from './gray-code.js' |
|||
console.log( |
|||
'Number\t' + |
|||
'Binary\t' + |
|||
'Gray Code\t' + |
|||
'Decoded Gray Code' |
|||
) |
|||
for (let number = 0; number < 32; number++) { |
|||
const grayCode = gray.encode(number) |
|||
const decodedGrayCode = gray.decode(grayCode) |
|||
console.log(printf( |
|||
'%2d\t%05d\t%05d\t\t%2d', |
|||
number, |
|||
number.toString(2), |
|||
grayCode.toString(2), |
|||
decodedGrayCode |
|||
)) |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Number Binary Gray Code Decoded Gray Code |
|||
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 |
|||
</pre> |
|||
=={{header|Julia}}== |
|||
{{works with|Julia|0.6}} |
|||
{{trans|C}} |
|||
<lang julia>grayencode(n::Integer) = n ⊻ (n >> 1) |
|||
function graydecode(n::Integer) |
|||
r = n |
|||
while (n >>= 1) != 0 |
|||
r ⊻= n |
|||
end |
|||
return r |
|||
end</lang> |
|||
Note that these functions work for any integer type, including arbitrary-precision integers (the built-in <code>BigInt</code> type). |
|||
=={{header|K}}== |
|||
Binary to Gray code |
|||
<lang K> 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}</lang> |
|||
Gray code to binary |
|||
"Accumulated xor" |
|||
<lang K> g2b:xor\</lang> |
|||
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 |
|||
<lang K> 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) |
|||
</lang> |
|||
As a function (*| takes the last result) |
|||
<lang K> g2b1:*|{gray x}\</lang> |
|||
Iterative version with "do" |
|||
<lang K> 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}</lang> |
|||
Presentation |
|||
<lang K> 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</lang> |
|||
{{out}} |
|||
<pre> 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</pre> |
|||
=={{header|Kotlin}}== |
|||
<lang scala>// version 1.0.6 |
|||
object Gray { |
|||
fun encode(n: Int) = n xor (n shr 1) |
|||
fun decode(n: Int): Int { |
|||
var p = n |
|||
var nn = n |
|||
while (nn != 0) { |
|||
nn = nn shr 1 |
|||
p = p xor nn |
|||
} |
|||
return p |
|||
} |
|||
} |
|||
fun main(args: Array<String>) { |
|||
println("Number\tBinary\tGray\tDecoded") |
|||
for (i in 0..31) { |
|||
print("$i\t${Integer.toBinaryString(i)}\t") |
|||
val g = Gray.encode(i) |
|||
println("${Integer.toBinaryString(g)}\t${Gray.decode(g)}") |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Liberty BASIC}}== |
|||
<lang lb> |
|||
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 |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
Decimal 0 is binary 00000000. Binary 00000000 is 00000000 in Gray code, or 00000000 in pure binary. |
|||
Decimal 1 is binary 00000001. Binary 00000001 is 00000001 in Gray code, or 00000001 in pure binary. |
|||
Decimal 2 is binary 00000010. Binary 00000010 is 00000011 in Gray code, or 00000010 in pure binary. |
|||
Decimal 3 is binary 00000011. Binary 00000011 is 00000010 in Gray code, or 00000011 in pure binary. |
|||
Decimal 4 is binary 00000100. Binary 00000100 is 00000110 in Gray code, or 00000100 in pure binary. |
|||
Decimal 5 is binary 00000101. Binary 00000101 is 00000111 in Gray code, or 00000101 in pure binary. |
|||
Decimal 6 is binary 00000110. Binary 00000110 is 00000101 in Gray code, or 00000110 in pure binary. |
|||
Decimal 7 is binary 00000111. Binary 00000111 is 00000100 in Gray code, or 00000111 in pure binary. |
|||
Decimal 8 is binary 00001000. Binary 00001000 is 00001100 in Gray code, or 00001000 in pure binary. |
|||
Decimal 9 is binary 00001001. Binary 00001001 is 00001101 in Gray code, or 00001001 in pure binary. |
|||
Decimal 10 is binary 00001010. Binary 00001010 is 00001111 in Gray code, or 00001010 in pure binary. |
|||
Decimal 11 is binary 00001011. Binary 00001011 is 00001110 in Gray code, or 00001011 in pure binary. |
|||
Decimal 12 is binary 00001100. Binary 00001100 is 00001010 in Gray code, or 00001100 in pure binary. |
|||
Decimal 13 is binary 00001101. Binary 00001101 is 00001011 in Gray code, or 00001101 in pure binary. |
|||
Decimal 14 is binary 00001110. Binary 00001110 is 00001001 in Gray code, or 00001110 in pure binary. |
|||
Decimal 15 is binary 00001111. Binary 00001111 is 00001000 in Gray code, or 00001111 in pure binary. |
|||
Decimal 16 is binary 00010000. Binary 00010000 is 00011000 in Gray code, or 00010000 in pure binary. |
|||
Decimal 17 is binary 00010001. Binary 00010001 is 00011001 in Gray code, or 00010001 in pure binary. |
|||
Decimal 18 is binary 00010010. Binary 00010010 is 00011011 in Gray code, or 00010010 in pure binary. |
|||
Decimal 19 is binary 00010011. Binary 00010011 is 00011010 in Gray code, or 00010011 in pure binary. |
|||
Decimal 20 is binary 00010100. Binary 00010100 is 00011110 in Gray code, or 00010100 in pure binary. |
|||
Decimal 21 is binary 00010101. Binary 00010101 is 00011111 in Gray code, or 00010101 in pure binary. |
|||
Decimal 22 is binary 00010110. Binary 00010110 is 00011101 in Gray code, or 00010110 in pure binary. |
|||
Decimal 23 is binary 00010111. Binary 00010111 is 00011100 in Gray code, or 00010111 in pure binary. |
|||
Decimal 24 is binary 00011000. Binary 00011000 is 00010100 in Gray code, or 00011000 in pure binary. |
|||
Decimal 25 is binary 00011001. Binary 00011001 is 00010101 in Gray code, or 00011001 in pure binary. |
|||
Decimal 26 is binary 00011010. Binary 00011010 is 00010111 in Gray code, or 00011010 in pure binary. |
|||
Decimal 27 is binary 00011011. Binary 00011011 is 00010110 in Gray code, or 00011011 in pure binary. |
|||
Decimal 28 is binary 00011100. Binary 00011100 is 00010010 in Gray code, or 00011100 in pure binary. |
|||
Decimal 29 is binary 00011101. Binary 00011101 is 00010011 in Gray code, or 00011101 in pure binary. |
|||
Decimal 30 is binary 00011110. Binary 00011110 is 00010001 in Gray code, or 00011110 in pure binary. |
|||
Decimal 31 is binary 00011111. Binary 00011111 is 00010000 in Gray code, or 00011111 in pure binary. |
|||
</pre> |
|||
=={{header|Limbo}}== |
|||
{{trans|Go}} |
|||
<lang limbo>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; |
|||
}</lang> |
|||
{{out}} |
|||
<code> |
|||
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 |
|||
</code> |
|||
=={{header|Lobster}}== |
|||
{{trans|C}} |
|||
<lang Lobster>def grey_encode(n) -> int: |
|||
return n ^ (n >> 1) |
|||
def grey_decode(n) -> int: |
|||
var p = n |
|||
n = n >> 1 |
|||
while n != 0: |
|||
p = p ^ n |
|||
n = n >> 1 |
|||
return p |
return p |
||
] |
|||
loop 0..31 'num [ |
|||
for(32) i: |
|||
encoded: toGray num |
|||
let g = grey_encode(i) |
|||
decoded: fromGray encoded |
|||
let b = grey_decode(g) |
|||
print(number_to_string(i, 10, 2) + " : " + |
|||
number_to_string(i, 2, 5) + " ⇾ " + |
|||
number_to_string(g, 2, 5) + " ⇾ " + |
|||
number_to_string(b, 2, 5) + " : " + |
|||
number_to_string(b, 10, 2))</lang> |
|||
{{out}} |
|||
<pre> |
|||
00 : 00000 ⇾ 00000 ⇾ 00000 : 00 |
|||
01 : 00001 ⇾ 00001 ⇾ 00001 : 01 |
|||
02 : 00010 ⇾ 00011 ⇾ 00010 : 02 |
|||
03 : 00011 ⇾ 00010 ⇾ 00011 : 03 |
|||
04 : 00100 ⇾ 00110 ⇾ 00100 : 04 |
|||
05 : 00101 ⇾ 00111 ⇾ 00101 : 05 |
|||
06 : 00110 ⇾ 00101 ⇾ 00110 : 06 |
|||
07 : 00111 ⇾ 00100 ⇾ 00111 : 07 |
|||
08 : 01000 ⇾ 01100 ⇾ 01000 : 08 |
|||
09 : 01001 ⇾ 01101 ⇾ 01001 : 09 |
|||
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 |
|||
</pre> |
|||
print [ |
|||
=={{header|Logo}}== |
|||
pad to :string num 2 ":" |
|||
{{trans|Euphoria}} |
|||
pad as.binary num 5 "=>" |
|||
<lang logo>to gray_encode :number |
|||
pad as.binary encoded 5 "=>" |
|||
output bitxor :number lshift :number -1 |
|||
pad as.binary decoded 5 ":" |
|||
end |
|||
pad to :string decoded 2 |
|||
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</lang> |
|||
Demonstration code, including formatters: |
|||
<lang logo>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 |
|||
] |
] |
||
]</lang> |
|||
] |
|||
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</lang> |
|||
{{out}} |
|||
<pre> 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 |
|||
</pre> |
|||
=={{header|Lua}}== |
|||
{{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>. |
|||
<lang 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</lang> |
|||
Demonstration code: |
|||
<lang lua>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</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|M2000 Interpreter}}== |
|||
{{trans|C}} |
|||
Additions to showing the modules/functions replacement mechanism of M2000 |
|||
<lang M2000 Interpreter> |
|||
Module Code32 (&code(), &decode()){ |
|||
Const d$="{0::-2} {1:-6} {2:-6} {3:-6} {4::-2}" |
|||
For i=0 to 32 |
|||
g=code(i) |
|||
b=decode(g) |
|||
Print format$(d$, i, @bin$(i), @bin$(g), @bin$(b), b) |
|||
Next |
|||
// static function |
|||
Function bin$(a) |
|||
a$="" |
|||
Do n= a mod 2 : a$=if$(n=1->"1", "0")+a$ : a|div 2 : Until a==0 |
|||
=a$ |
|||
End Function |
|||
} |
|||
Module GrayCode { |
|||
Module doit (&a(), &b()) { } |
|||
Function GrayEncode(a) { |
|||
=binary.xor(a, binary.shift(a,-1)) |
|||
} |
|||
Function GrayDecode(a) { |
|||
b=0 |
|||
Do b=binary.xor(a, b) : a=binary.shift(a,-1) : Until a==0 |
|||
=b |
|||
} |
|||
// pass 2 functions to Code32 |
|||
doit &GrayEncode(), &GrayDecode() |
|||
} |
|||
// pass Code32 to GrayCode in place of doit |
|||
GrayCode ; doit as Code32 |
|||
</lang> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;"> |
|||
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 |
|||
32 100000 110000 100000 32 |
|||
</pre > |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
|||
<lang Mathematica>graycode[n_]:=BitXor[n,BitShiftRight[n]] |
|||
graydecode[n_]:=Fold[BitXor,0,FixedPointList[BitShiftRight,n]]</lang> |
|||
{{out}} |
|||
<pre>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}</pre> |
|||
=={{header|MATLAB}}== |
|||
<lang 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 |
|||
</lang> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;"> |
|||
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 |
|||
</pre> |
|||
=={{header|Mercury}}== |
|||
The following is a full implementation of Gray encoding and decoding. |
|||
It publicly exposes the <tt>gray</tt> type along with the following |
|||
value conversion functions: |
|||
* <tt>gray.from_int/1</tt> |
|||
* <tt>gray.to_int/1</tt> |
|||
The <tt>from_int/1</tt> and <tt>to_int/1</tt> functions are ''value'' conversion functions. <tt>from_int/1</tt> converts an <tt>int</tt> value into the enclosing <tt>gray</tt> type. <tt>to_int/1</tt> converts a <tt>gray</tt> value back into a regular <tt>int</tt> type. |
|||
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. |
|||
<lang mercury>:- 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.</lang> |
|||
The following program tests the above code: |
|||
<lang mercury>:- 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.</lang> |
|||
The <tt>main/2</tt> 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 <tt>check_conversion/2</tt> 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. |
|||
<tt>gray.from_int/1</tt> is mapped over the <tt>Numbers</tt> (input) list and placed into the <tt>Grays</tt> (output) list. |
|||
Then <tt>gray.to_int</tt> is mapped over the <tt>Grays</tt> list and placed into the <tt>Numbers</tt> (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 <tt>Grays</tt> list is not yet populated, unification is very similar notionally to assignment in other languages. |
|||
<tt>Numbers</tt>, however, '''is''' instantiated and thus unification is more like testing for equality. |
|||
If the conversions check out, <tt>main/2</tt> prints off some headers and then displays the lists. Here we're cluttering up the namespace of the <tt>gray_test</tt> 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 <tt>display_lists</tt> 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 <tt>display_record/4</tt>. In that predicate the aforementioned <tt>coerce/2</tt> predicate extracts, in this case, the Gray value's representation. |
|||
This value and the corresponding <tt>int</tt> value are then converted into a string showing the base-2 representation of their values. |
|||
<tt>io.format/4</tt> then prints them off in a nice format. |
|||
The output of the program looks like this: |
|||
<tt>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</tt> |
|||
=={{header|Nim}}== |
|||
{{trans|C}} |
|||
<lang nim>proc grayEncode(n: int): int = |
|||
n xor (n shr 1) |
|||
proc grayDecode(n: int): int = |
|||
result = n |
|||
var t = n |
|||
while t > 0: |
|||
t = t shr 1 |
|||
result = result xor t</lang> |
|||
Demonstration code: |
|||
<lang nim>import strutils, strformat |
|||
for i in 0 .. 32: |
|||
echo &"{i:>2} => {toBin(grayEncode(i), 6)} => {grayDecode(grayEncode(i)):>2}"</lang> |
|||
{{out}} |
|||
<pre> 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</pre> |
|||
=={{header|OCaml}}== |
|||
<lang 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</lang> |
|||
=={{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>. |
|||
<lang parigp>toGray(n)=bitxor(n,n>>1); |
|||
fromGray(n)=my(k=1,m=n);while(m>>k,n=bitxor(n,n>>k);k+=k);n; |
|||
bin(n)=concat(apply(k->Str(k),binary(n))) |
|||
for(n=0,31,print(n"\t"bin(n)"\t"bin(g=toGray(n))"\t"fromGray(g)))</lang> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|Pascal}}== |
|||
See [[Gray_code#Delphi | Delphi]] |
|||
=={{header|Perl}}== |
|||
<lang 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); |
|||
}</lang> |
|||
=={{header|Phix}}== |
|||
{{Trans|Delphi}} (turned out to be almost the same as Euphoria) |
|||
<lang Phix>function gray_encode(integer n) |
|||
return xor_bits(n,floor(n/2)) |
|||
end function |
|||
function gray_decode(integer n) |
|||
integer r = 0 |
|||
while n>0 do |
|||
r = xor_bits(r,n) |
|||
n = floor(n/2) |
|||
end while |
|||
return r |
|||
end function |
|||
integer e,d |
|||
puts(1," N Binary Gray Decoded\n"& |
|||
"== ===== ===== =======\n") |
|||
for i=0 to 31 do |
|||
e = gray_encode(i) |
|||
d = gray_decode(e) |
|||
printf(1,"%2d %05b %05b %2d\n",{i,i,e,d}) |
|||
end for</lang> |
|||
{{out}} |
|||
<pre> |
|||
N 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 |
|||
</pre> |
|||
=={{header|PHP}}== |
|||
<lang php> |
|||
<?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)); |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|PicoLisp}}== |
|||
<lang PicoLisp>(de grayEncode (N) |
|||
(bin (x| N (>> 1 N))) ) |
|||
(de grayDecode (G) |
|||
(bin |
|||
(pack |
|||
(let X 0 |
|||
(mapcar |
|||
'((C) (setq X (x| X (format C)))) |
|||
(chop G) ) ) ) ) )</lang> |
|||
Test: |
|||
<lang PicoLisp>(prinl " Binary Gray Decoded") |
|||
(for I (range 0 31) |
|||
(let G (grayEncode I) |
|||
(tab (4 9 9 9) I (bin I) G (grayDecode G)) ) )</lang> |
|||
{{out}} |
|||
<pre> 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</pre> |
|||
=={{header|PL/I}}== |
|||
<lang 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;</lang> |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|PowerBASIC}}== |
|||
<lang 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</lang> |
|||
=={{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}} |
|||
<lang Prolog>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 ).</lang> |
|||
=== 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}} |
|||
<lang Prolog>:- 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). |
|||
</lang> |
|||
{{out}} |
|||
Putting all of this in a file, we execute it, getting the following results: |
|||
<pre>% 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</pre> |
|||
=={{header|PureBasic}}== |
|||
<lang PureBasic>Procedure.i gray_encode(n) |
|||
ProcedureReturn n ! (n >> 1) |
|||
EndProcedure |
|||
Procedure.i gray_decode(g) |
|||
Protected bit = 1 << (8 * SizeOf(Integer) - 2) |
|||
Protected b = g & bit, p = b >> 1 |
|||
While bit > 1 |
|||
bit >> 1 |
|||
b | (p ! (g & bit)) |
|||
p = (b & bit) >> 1 |
|||
Wend |
|||
ProcedureReturn b |
|||
EndProcedure |
|||
If OpenConsole() |
|||
PrintN("Number Gray Binary Decoded") |
|||
Define i, n |
|||
For i = 0 To 31 |
|||
g = gray_encode(i) |
|||
Print(RSet(Str(i), 2, "0") + Space(5)) |
|||
Print(RSet(Bin(g, #PB_Byte), 5, "0") + Space(2)) |
|||
n = gray_decode(g) |
|||
Print(RSet(Bin(n, #PB_Byte), 5, "0") + Space(3)) |
|||
PrintN(RSet(Str(n), 2, "0")) |
|||
Next |
|||
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() |
|||
CloseConsole() |
|||
EndIf</lang> |
|||
{{out}} |
|||
<pre>Number Gray Binary 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</pre> |
|||
=={{header|Python}}== |
|||
===Python: on integers=== |
|||
Works with python integers |
|||
<lang>def gray_encode(n): |
|||
return n ^ n >> 1 |
|||
def gray_decode(n): |
|||
m = n >> 1 |
|||
while m: |
|||
n ^= m |
|||
m >>= 1 |
|||
return n |
|||
if __name__ == '__main__': |
|||
print("DEC, BIN => GRAY => DEC") |
|||
for i in range(32): |
|||
gray = gray_encode(i) |
|||
dec = gray_decode(gray) |
|||
print(f" {i:>2d}, {i:>05b} => {gray:>05b} => {dec:>2d}")</lang> |
|||
{{out}} |
|||
<pre>DEC, BIN => GRAY => DEC |
|||
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</pre> |
|||
===Python: on lists of bits=== |
|||
This example works with lists of discrete binary digits. |
|||
;First some int<>bin conversion routines: |
|||
<lang python>>>> def int2bin(n): |
|||
'From positive integer to list of binary bits, msb at index 0' |
|||
if n: |
|||
bits = [] |
|||
while n: |
|||
n,remainder = divmod(n, 2) |
|||
bits.insert(0, remainder) |
|||
return bits |
|||
else: return [0] |
|||
>>> def bin2int(bits): |
|||
'From binary bits, msb at index 0 to integer' |
|||
i = 0 |
|||
for bit in bits: |
|||
i = i * 2 + bit |
|||
return i</lang> |
|||
;Now the bin<>gray converters. |
|||
These follow closely the methods in the animation seen here: [http://www.wisc-online.com/Objects/ViewObject.aspx?ID=IAU8307 Converting Between Gray and Binary Codes]. |
|||
<lang python>>>> def bin2gray(bits): |
|||
return bits[:1] + [i ^ ishift for i, ishift in zip(bits[:-1], bits[1:])] |
|||
>>> def gray2bin(bits): |
|||
b = [bits[0]] |
|||
for nextb in bits[1:]: b.append(b[-1] ^ nextb) |
|||
return b</lang> |
|||
;Sample output |
|||
<lang python>>>> for i in range(16): |
|||
print('int:%2i -> bin:%12r -> gray:%12r -> bin:%12r -> int:%2i' % |
|||
( i, |
|||
int2bin(i), |
|||
bin2gray(int2bin(i)), |
|||
gray2bin(bin2gray(int2bin(i))), |
|||
bin2int(gray2bin(bin2gray(int2bin(i)))) |
|||
)) |
|||
int: 0 -> bin: [0] -> gray: [0] -> bin: [0] -> int: 0 |
|||
int: 1 -> bin: [1] -> gray: [1] -> bin: [1] -> int: 1 |
|||
int: 2 -> bin: [1, 0] -> gray: [1, 1] -> bin: [1, 0] -> int: 2 |
|||
int: 3 -> bin: [1, 1] -> gray: [1, 0] -> bin: [1, 1] -> int: 3 |
|||
int: 4 -> bin: [1, 0, 0] -> gray: [1, 1, 0] -> bin: [1, 0, 0] -> int: 4 |
|||
int: 5 -> bin: [1, 0, 1] -> gray: [1, 1, 1] -> bin: [1, 0, 1] -> int: 5 |
|||
int: 6 -> bin: [1, 1, 0] -> gray: [1, 0, 1] -> bin: [1, 1, 0] -> int: 6 |
|||
int: 7 -> bin: [1, 1, 1] -> gray: [1, 0, 0] -> bin: [1, 1, 1] -> int: 7 |
|||
int: 8 -> bin:[1, 0, 0, 0] -> gray:[1, 1, 0, 0] -> bin:[1, 0, 0, 0] -> int: 8 |
|||
int: 9 -> bin:[1, 0, 0, 1] -> gray:[1, 1, 0, 1] -> bin:[1, 0, 0, 1] -> int: 9 |
|||
int:10 -> bin:[1, 0, 1, 0] -> gray:[1, 1, 1, 1] -> bin:[1, 0, 1, 0] -> int:10 |
|||
int:11 -> bin:[1, 0, 1, 1] -> gray:[1, 1, 1, 0] -> bin:[1, 0, 1, 1] -> int:11 |
|||
int:12 -> bin:[1, 1, 0, 0] -> gray:[1, 0, 1, 0] -> bin:[1, 1, 0, 0] -> int:12 |
|||
int:13 -> bin:[1, 1, 0, 1] -> gray:[1, 0, 1, 1] -> bin:[1, 1, 0, 1] -> int:13 |
|||
int:14 -> bin:[1, 1, 1, 0] -> gray:[1, 0, 0, 1] -> bin:[1, 1, 1, 0] -> int:14 |
|||
int:15 -> bin:[1, 1, 1, 1] -> gray:[1, 0, 0, 0] -> bin:[1, 1, 1, 1] -> int:15 |
|||
>>> </lang> |
|||
=={{header|R}}== |
|||
<lang 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) |
|||
} |
|||
</lang> |
|||
=={{header|Racket}}== |
|||
<lang 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")))) |
|||
</lang> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;">> (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 |
|||
</pre> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
<lang perl6>sub gray_encode ( Int $n --> Int ) { |
|||
return $n +^ ( $n +> 1 ); |
|||
} |
|||
sub gray_decode ( Int $n is copy --> Int ) { |
|||
my $mask = 1 +< (32-2); |
|||
$n +^= $mask +> 1 if $n +& $mask while $mask +>= 1; |
|||
return $n; |
|||
} |
|||
for ^32 -> $n { |
|||
my $g = gray_encode($n); |
|||
my $d = gray_decode($g); |
|||
printf "%2d: %5b => %5b => %5b: %2d\n", $n, $n, $g, $d, $d; |
|||
die if $d != $n; |
|||
}</lang> |
|||
{{out}} |
|||
<pre> 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 |
|||
</pre> |
|||
Raku distinguishes numeric bitwise operators with a leading <tt>+</tt> sign, |
|||
so <tt>+<</tt> and <tt>+></tt> are left and right shift, |
|||
while <tt>+&</tt> is a bitwise AND, while <tt>+^</tt> is bitwise XOR |
|||
(here used as part of an assignment metaoperator). |
|||
=={{header|REXX}}== |
|||
The leading zeroes for the binary numbers and the gray code could've easily been elided. |
|||
<lang rexx>/*REXX program converts decimal number ───► binary ───► gray code ───► binary.*/ |
|||
parse arg N . /*get the optional argument from the CL*/ |
|||
if N=='' | N=="," then N=31 /*Not specified? Then use the default.*/ |
|||
L=max(1,length(strip(x2b(d2x(N)),'L',0))) /*find the max binary length of N.*/ |
|||
w=14 /*used for the formatting of cell width*/ |
|||
_=center('binary',w,'─') /*the 2nd and 4th part of the header.*/ |
|||
say center('decimal', w, "─")'►' _"►" center('gray code', w, '─')"►" _ |
|||
/* [+] the output header*/ |
|||
do j=0 to N; b=right(x2b(d2x(j)),L,0) /*process 0 ──► N. */ |
|||
g=b2gray(b) /*convert binary number to gray code. */ |
|||
a=gray2b(g) /*convert the gray code to binary. */ |
|||
say center(j,w+1) center(b,w+1) center(g,w+1) center(a,w+1) |
|||
end /*j*/ |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
b2gray: procedure; parse arg x 1 $ 2; do b=2 to length(x) |
|||
$=$||(substr(x,b-1,1) && substr(x,b,1)) |
|||
end /*b*/ |
|||
return $ |
|||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
gray2b: procedure; parse arg x 1 $ 2; do g=2 to length(x) |
|||
$=$ || (right($,1) && substr(x,g,1)) |
|||
end /*g*/ /* ↑ */ |
|||
/* │ */ |
|||
return $ /*this is an eXclusive OR ►─────────┘ */</lang> |
|||
'''output''' when using the default input: |
|||
<pre> |
|||
───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 |
|||
</pre> |
|||
=={{header|Ring}}== |
|||
<lang ring> |
|||
# Project : Gray code |
|||
pos = 5 |
|||
see "0 : 00000 => 00000 => 00000" + nl |
|||
for n = 1 to 31 |
|||
res1 = tobase(n, 2, pos) |
|||
res2 = tobase(grayencode(n), 2, pos) |
|||
res3 = tobase(graydecode(n), 2, pos) |
|||
see "" + n + " : " + res1 + " => " + res2 + " => " + res3 + nl |
|||
next |
|||
func grayencode(n) |
|||
return n ^ (n >> 1) |
|||
func graydecode(n) |
|||
p = n |
|||
while (n = n >> 1) |
|||
p = p ^ n |
|||
end |
|||
return p |
|||
func tobase(nr, base, pos) |
|||
binary = 0 |
|||
i = 1 |
|||
while(nr != 0) |
|||
remainder = nr % base |
|||
nr = floor(nr/base) |
|||
binary= binary + (remainder*i) |
|||
i = i*10 |
|||
end |
|||
result = "" |
|||
for nr = 1 to pos - len(string(binary)) |
|||
result = result + "0" |
|||
next |
|||
result = result + string(binary) |
|||
return result |
|||
</lang> |
|||
Output: |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Ruby}}== |
|||
<tt>Integer#from_gray</tt> has recursion so it can use each bit of the answer to compute the next bit. |
|||
<lang ruby>class Integer |
|||
# Converts a normal integer to a Gray code. |
|||
def to_gray |
|||
raise Math::DomainError, "integer is negative" if self < 0 |
|||
self ^ (self >> 1) |
|||
end |
|||
# Converts a Gray code to a normal integer. |
|||
def from_gray |
|||
raise Math::DomainError, "integer is negative" if self < 0 |
|||
recurse = proc do |i| |
|||
next 0 if i == 0 |
|||
o = recurse[i >> 1] << 1 |
|||
o | (i[0] ^ o[1]) |
|||
end |
|||
recurse[self] |
|||
end |
|||
end |
|||
(0..31).each do |number| |
|||
encoded = number.to_gray |
|||
decoded = encoded.from_gray |
|||
printf "%2d : %5b => %5b => %5b : %2d\n", |
|||
number, number, encoded, decoded, decoded |
|||
end</lang> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;"> |
|||
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 |
|||
</pre> |
|||
=={{header|Rust}}== |
|||
{{works with|Rust|1.1}} |
|||
<lang rust>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)); |
|||
} |
|||
}</lang> |
|||
=={{header|Scala}}== |
|||
Functional style: the Gray code is encoded to, and decoded from a String. |
|||
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). |
|||
<lang scala>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))) |
|||
</lang> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;">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 |
|||
</pre> |
|||
Alternatively, more imperative style: |
|||
<lang scala>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))) |
|||
}</lang> |
|||
Improved version of decode using functional style (recursion+local method). |
|||
No vars and mutations. |
|||
<lang scala>def decode(n:Long)={ |
|||
def calc(g:Long,bits:Long):Long=if (bits>0) calc(g^bits, bits>>1) else g |
|||
calc(0, n) |
|||
}</lang> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;">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 |
|||
</pre> |
|||
=={{header|Scratch}}== |
|||
<div style="overflow: auto;"> |
|||
[http://i.imgur.com/0sw5D4T.png] |
|||
</div> |
|||
=={{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. |
|||
<lang seed7>$ 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;</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|SenseTalk}}== |
|||
Note: Inputs and outputs as strings |
|||
<lang sensetalk> |
|||
function BinaryToGray param1 |
|||
set theResult to "" |
|||
repeat for each character in param1 |
|||
if the counter is equal to 1 |
|||
put it after theResult |
|||
else |
|||
if it is equal to previousCharacter |
|||
put "0" after theResult |
|||
else |
|||
put "1" after theResult |
|||
end if |
|||
end if |
|||
set previousCharacter to it |
|||
end repeat |
|||
return theResult |
|||
end BinaryToGray |
|||
function GrayToBinary param1 |
|||
set theResult to param1 |
|||
repeat for each character in param1 |
|||
if the counter is equal to 1 |
|||
next repeat |
|||
end if |
|||
set currentChar to it |
|||
set lastCharInd to the counter - 1 |
|||
repeat for lastCharInd down to 1 |
|||
if currentChar is equal to character it of param1 |
|||
set currentChar to "0" |
|||
else |
|||
set currentChar to "1" |
|||
end if |
|||
end repeat |
|||
set character the counter of theResult to currentChar |
|||
end repeat |
|||
return theResult |
|||
end GrayToBinary |
|||
</lang> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;">binary => gray => decoded |
|||
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 |
|||
101001110101111 => 111101001111000 => 101001110101111 |
|||
101001110110000 => 111101001101000 => 101001110110000 |
|||
101001110110001 => 111101001101001 => 101001110110001 |
|||
101001110110010 => 111101001101011 => 101001110110010 |
|||
</pre> |
|||
=={{header|Sidef}}== |
|||
{{trans|Perl}} |
|||
<lang ruby>func bin2gray(n) { |
|||
n ^ (n >> 1) |
|||
} |
|||
func gray2bin(num) { |
|||
var bin = num |
|||
while (num >>= 1) { bin ^= num } |
|||
return bin |
|||
} |
|||
{ |i| |
|||
var gr = bin2gray(i) |
|||
printf("%d\t%b\t%b\t%b\n", i, i, gr, gray2bin(gr)) |
|||
} << ^32</lang> |
|||
{{out}} |
|||
<pre> |
|||
0 0 0 0 |
|||
1 1 1 1 |
|||
2 10 11 10 |
|||
3 11 10 11 |
|||
4 100 110 100 |
|||
5 101 111 101 |
|||
6 110 101 110 |
|||
7 111 100 111 |
|||
8 1000 1100 1000 |
|||
9 1001 1101 1001 |
|||
10 1010 1111 1010 |
|||
11 1011 1110 1011 |
|||
12 1100 1010 1100 |
|||
13 1101 1011 1101 |
|||
14 1110 1001 1110 |
|||
15 1111 1000 1111 |
|||
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 |
|||
</pre> |
|||
=={{header|SQL}}== |
|||
<lang 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 |
|||
</lang> |
|||
=={{header|Standard ML}}== |
|||
<lang sml>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</lang> |
|||
=={{header|Swift}}== |
|||
<lang swift>func grayEncode(_ i: Int) -> Int { |
|||
return (i >> 1) ^ i |
|||
} |
|||
func grayDecode(_ i: Int) -> Int { |
|||
switch i { |
|||
case 0: |
|||
return 0 |
|||
case _: |
|||
return i ^ grayDecode(i >> 1) |
|||
} |
|||
} |
|||
for i in 0..<32 { |
|||
let iStr = String(i, radix: 2) |
|||
let encode = grayEncode(i) |
|||
let encodeStr = String(encode, radix: 2) |
|||
let decode = grayDecode(encode) |
|||
let decodeStr = String(decode, radix: 2) |
|||
print("\(i) (\(iStr)) => \(encode) (\(encodeStr)) => \(decode) (\(decodeStr))") |
|||
}</lang> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;">0 (0) => 0 (0) => 0 (0) |
|||
1 (1) => 1 (1) => 1 (1) |
|||
2 (10) => 3 (11) => 2 (10) |
|||
3 (11) => 2 (10) => 3 (11) |
|||
4 (100) => 6 (110) => 4 (100) |
|||
5 (101) => 7 (111) => 5 (101) |
|||
6 (110) => 5 (101) => 6 (110) |
|||
7 (111) => 4 (100) => 7 (111) |
|||
8 (1000) => 12 (1100) => 8 (1000) |
|||
9 (1001) => 13 (1101) => 9 (1001) |
|||
10 (1010) => 15 (1111) => 10 (1010) |
|||
11 (1011) => 14 (1110) => 11 (1011) |
|||
12 (1100) => 10 (1010) => 12 (1100) |
|||
13 (1101) => 11 (1011) => 13 (1101) |
|||
14 (1110) => 9 (1001) => 14 (1110) |
|||
15 (1111) => 8 (1000) => 15 (1111) |
|||
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)</pre> |
|||
=={{header|Tcl}}== |
|||
<lang tcl>namespace eval gray { |
|||
proc encode n { |
|||
expr {$n ^ $n >> 1} |
|||
} |
|||
proc decode n { |
|||
# Compute some bit at least as large as MSB |
|||
set i [expr {2**int(ceil(log($n+1)/log(2)))}] |
|||
set b [set bprev [expr {$n & $i}]] |
|||
while {[set i [expr {$i >> 1}]]} { |
|||
set b [expr {$b | [set bprev [expr {$n & $i ^ $bprev >> 1}]]}] |
|||
} |
|||
return $b |
|||
} |
|||
}</lang> |
|||
Demonstrating: |
|||
<lang tcl>package require Tcl 8.6; # Just for %b format specifier |
|||
for {set i 0} {$i < 32} {incr i} { |
|||
set g [gray::encode $i] |
|||
set b [gray::decode $g] |
|||
puts [format "%2d: %05b => %05b => %05b : %2d" $i $i $g $b $b] |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Ursala}}== |
|||
<lang 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</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|VBScript}}== |
|||
<lang vb>Function Encoder(ByVal n) |
|||
Encoder = n Xor (n \ 2) |
|||
End Function |
|||
Function Decoder(ByVal n) |
|||
Dim g : g = 0 |
|||
Do While n > 0 |
|||
g = g Xor n |
|||
n = n \ 2 |
|||
Loop |
|||
Decoder = g |
|||
End Function |
|||
' Decimal to Binary |
|||
Function Dec2bin(ByVal n, ByVal length) |
|||
Dim i, strbin : strbin = "" |
|||
For i = 1 to 5 |
|||
strbin = (n Mod 2) & strbin |
|||
n = n \ 2 |
|||
Next |
|||
Dec2Bin = strbin |
|||
End Function |
|||
WScript.StdOut.WriteLine("Binary -> Gray Code -> Binary") |
|||
For i = 0 to 31 |
|||
encoded = Encoder(i) |
|||
decoded = Decoder(encoded) |
|||
WScript.StdOut.WriteLine(Dec2Bin(i, 5) & " -> " & Dec2Bin(encoded, 5) & " -> " & Dec2Bin(decoded, 5)) |
|||
Next</lang> |
|||
{{Out}} |
|||
<pre style="overflow: auto; height: 20em;">Binary -> Gray Code -> Binary |
|||
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</pre> |
|||
=={{header|Verilog}}== |
|||
'''Function Based Approach:''' |
|||
<lang Verilog> |
|||
`timescale 1ns/10ps |
|||
`default_nettype wire |
|||
module graytestbench; |
|||
localparam aw = 8; |
|||
function [aw:0] binn_to_gray; |
|||
input [aw:0] binn; |
|||
begin :b2g |
|||
binn_to_gray = binn ^ (binn >> 1); |
|||
end |
|||
endfunction |
|||
function [aw:0] gray_to_binn; |
|||
input [aw:0] gray; |
|||
begin :g2b |
|||
reg [aw:0] binn; |
|||
integer i; |
|||
for(i=0; i <= aw; i = i+1) begin |
|||
binn[i] = ^(gray >> i); |
|||
end |
|||
gray_to_binn = binn; |
|||
end |
|||
endfunction |
|||
initial begin :test_graycode |
|||
integer ii; |
|||
reg[aw:0] gray; |
|||
reg[aw:0] binn; |
|||
for(ii=0; ii < 10; ii=ii+1) begin |
|||
gray = binn_to_gray(ii[aw:0]); |
|||
binn = gray_to_binn(gray); |
|||
$display("test_graycode: i:%x gray:%x:%b binn:%x", ii[aw:0], gray, gray, binn); |
|||
end |
|||
$stop; |
|||
end |
|||
endmodule |
|||
`default_nettype none |
|||
</lang> |
|||
'''Module Based Approach:''' |
|||
<lang Verilog> |
|||
`timescale 1ns/10ps |
|||
`default_nettype none |
|||
module gray_counter #( |
|||
parameter SIZE=4 |
|||
) ( |
|||
input wire i_clk, |
|||
input wire i_rst_n, |
|||
input wire i_inc, |
|||
output wire [SIZE-1:0] o_count_gray, |
|||
output wire [SIZE-1:0] o_count_binn |
|||
); |
|||
reg [SIZE-1:0] state_gray; |
|||
reg [SIZE-1:0] state_binn; |
|||
reg [SIZE-1:0] logic_gray; |
|||
reg [SIZE-1:0] logic_binn; |
|||
always @(posedge i_clk or negedge i_rst_n) begin |
|||
if (!i_rst_n) begin |
|||
state_gray <= 0; |
|||
state_binn <= 0; |
|||
end |
|||
else begin |
|||
state_gray <= logic_gray; |
|||
state_binn <= logic_binn; |
|||
end |
|||
end |
|||
always @* begin |
|||
logic_binn = state_binn + i_inc; |
|||
logic_gray = (logic_binn>>1) ^ logic_binn; |
|||
end |
|||
assign o_count_gray = state_gray; |
|||
assign o_count_binn = state_binn; |
|||
endmodule |
|||
`default_nettype none |
|||
</lang> |
|||
=={{header|VHDL}}== |
|||
Combinatorial encoder: |
|||
<lang VHDL>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;</lang> |
|||
Combinatorial decoder: |
|||
<lang VHDL>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;</lang> |
|||
=={{header|Wren}}== |
|||
{{libheader|Wren-fmt}} |
|||
<lang ecmascript>import "/fmt" for Fmt |
|||
var toGray = Fn.new { |n| n ^ (n>>1) } |
|||
var fromGray = Fn.new { |g| |
|||
var b = 0 |
|||
while (g != 0) { |
|||
b = b ^ g |
|||
g = g >> 1 |
|||
} |
|||
return b |
|||
} |
|||
System.print("decimal binary gray decoded") |
|||
for (b in 0..31) { |
|||
System.write(" %(Fmt.d(2, b)) %(Fmt.bz(5, b))") |
|||
var g = toGray.call(b) |
|||
System.write(" %(Fmt.bz(5, g))") |
|||
System.print(" %(Fmt.bz(5, fromGray.call(g)))") |
|||
}</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
|||
decimal binary gray decoded |
|||
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 |
|||
</pre> |
|||
<pre> 0 : 0 => 0 => 0 : 0 |
|||
=={{header|XBasic}}== |
|||
1 : 1 => 1 => 1 : 1 |
|||
{{trans|DWScript}} |
|||
2 : 10 => 11 => 10 : 2 |
|||
Intrinsic function <code>BIN$</code> has been used. |
|||
3 : 11 => 10 => 11 : 3 |
|||
{{works with|Windows XBasic}} |
|||
4 : 100 => 110 => 100 : 4 |
|||
<lang xbasic> |
|||
5 : 101 => 111 => 101 : 5 |
|||
PROGRAM "graycode" |
|||
6 : 110 => 101 => 110 : 6 |
|||
VERSION "0.0001" |
|||
7 : 111 => 100 => 111 : 7 |
|||
8 : 1000 => 1100 => 1000 : 8 |
|||
DECLARE FUNCTION Entry() |
|||
9 : 1001 => 1101 => 1001 : 9 |
|||
INTERNAL FUNCTION Encode(v&) |
|||
10 : 1010 => 1111 => 1010 : 10 |
|||
INTERNAL FUNCTION Decode(v&) |
|||
11 : 1011 => 1110 => 1011 : 11 |
|||
12 : 1100 => 1010 => 1100 : 12 |
|||
FUNCTION Entry() |
|||
13 : 1101 => 1011 => 1101 : 13 |
|||
PRINT "decimal binary gray decoded" |
|||
14 : 1110 => 1001 => 1110 : 14 |
|||
FOR i& = 0 TO 31 |
|||
15 : 1111 => 1000 => 1111 : 15 |
|||
g& = Encode(i&) |
|||
16 : 10000 => 11000 => 10000 : 16 |
|||
d& = Decode(g&) |
|||
17 : 10001 => 11001 => 10001 : 17 |
|||
PRINT FORMAT$(" ##", i&); " "; BIN$(i&, 5); " "; BIN$(g&, 5); |
|||
18 : 10010 => 11011 => 10010 : 18 |
|||
PRINT " "; BIN$(d&, 5); FORMAT$(" ##", d&) |
|||
19 : 10011 => 11010 => 10011 : 19 |
|||
NEXT i& |
|||
20 : 10100 => 11110 => 10100 : 20 |
|||
END FUNCTION |
|||
21 : 10101 => 11111 => 10101 : 21 |
|||
22 : 10110 => 11101 => 10110 : 22 |
|||
FUNCTION Encode(v&) |
|||
23 : 10111 => 11100 => 10111 : 23 |
|||
END FUNCTION v& ^ (v& >> 1) |
|||
24 : 11000 => 10100 => 11000 : 24 |
|||
25 : 11001 => 10101 => 11001 : 25 |
|||
FUNCTION Decode(v&) |
|||
26 : 11010 => 10111 => 11010 : 26 |
|||
result& = 0 |
|||
27 : 11011 => 10110 => 11011 : 27 |
|||
DO WHILE v& > 0 |
|||
28 : 11100 => 10010 => 11100 : 28 |
|||
29 : 11101 => 10011 => 11101 : 29 |
|||
30 : 11110 => 10001 => 11110 : 30 |
|||
LOOP |
|||
31 : 11111 => 10000 => 11111 : 31 </pre> |
|||
END FUNCTION result& |
|||
END PROGRAM |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
<lang 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); |
|||
]; |
|||
]</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|zkl}}== |
|||
<lang zkl>fcn grayEncode(n){ n.bitXor(n.shiftRight(1)) } |
|||
fcn grayDecode(g){ b:=g; while(g/=2){ b=b.bitXor(g) } b }</lang> |
|||
<lang zkl>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)); |
|||
}</lang> |
|||
{{out}} |
|||
<pre style="overflow: auto; height: 20em;"> |
|||
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) |
|||
</pre> |