Gray code
You are encouraged to solve this task according to the task description, using any language you may know.
Gray code is a form of binary encoding where transitions between consecutive numbers differ by only one bit. This is a useful encoding for reducing hardware data hazards with values that change rapidly and/or connect to slower hardware as inputs. It is also useful for generating inputs for Karnaugh maps in order from left to right or top to bottom.
Create functions to encode a number to and decode a number from Gray code.
Display the normal binary representations, Gray code representations, and decoded Gray code values for all 5-bit binary numbers (0-31 inclusive, leading 0's not necessary).
There are many possible Gray codes. The following encodes what is called "binary reflected Gray code."
Encoding (MSB is bit 0, b is binary, g is Gray code):
if b[i-1] = 1 g[i] = not b[i] else g[i] = b[i]
Or:
g = b xor (b logically right shifted 1 time)
Decoding (MSB is bit 0, b is binary, g is Gray code):
b[0] = g[0] for other bits: b[i] = g[i] xor b[i-1]
- Reference
- Converting Between Gray and Binary Codes. It includes step-by-step animations.
11l
F gray_encode(n)
R n (+) n >> 1
F gray_decode(=n)
V m = n >> 1
L m != 0
n (+)= m
m >>= 1
R n
print(‘DEC, BIN => GRAY => DEC’)
L(i) 32
V gray = gray_encode(i)
V dec = gray_decode(gray)
print(‘ #2, #. => #. => #2’.format(i, bin(i).zfill(5), bin(gray).zfill(5), dec))- Output:
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
8080 Assembly
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,'$'- Output:
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
8051 Assembly
.equ cin, 0x0032
.equ cout, 0x0030
.equ phex, 0x0034
.equ phex16, 0x0036
.equ nl, 0x0048
.org 0x2000
main:
mov r7, #0
next:
mov a, r7
lcall phex
mov a, #' '
lcall cout
mov a, r7
acall genc
lcall phex
mov r6, a
mov a, #' '
lcall cout
mov a, r6
acall gdec
lcall phex
lcall nl
inc r7
cjne r7, #0, next
lcall cin
ljmp 0x0000
;--------
genc:
mov r0, a
clr c
rrc a
xrl a, r0
ret
;--------
;--------
gdec:
mov r0, a
gdec_shift_xor:
clr c
rrc a
jz gdec_out
xch a, r0
xrl a, r0
xch a, r0
sjmp gdec_shift_xor
gdec_out:
xch a, r0
ret
;--------- Output:
00 00 00 01 01 01 02 03 02 03 02 03 04 06 04 05 07 05 06 05 06 07 04 07 08 0C 08 09 0D 09 0A 0F 0A 0B 0E 0B 0C 0A 0C 0D 0B 0D 0E 09 0E 0F 08 0F 10 18 10 11 19 11 12 1B 12 13 1A 13 14 1E 14 15 1F 15 16 1D 16 17 1C 17 18 14 18 19 15 19 1A 17 1A 1B 16 1B 1C 12 1C 1D 13 1D 1E 11 1E 1F 10 1F 20 30 20 21 31 21 22 33 22 23 32 23 24 36 24 25 37 25 26 35 26 27 34 27 28 3C 28 29 3D 29 2A 3F 2A 2B 3E 2B 2C 3A 2C 2D 3B 2D 2E 39 2E 2F 38 2F 30 28 30 31 29 31 32 2B 32 33 2A 33 34 2E 34 35 2F 35 36 2D 36 37 2C 37 38 24 38 39 25 39 3A 27 3A 3B 26 3B 3C 22 3C 3D 23 3D 3E 21 3E 3F 20 3F 40 60 40 41 61 41 42 63 42 43 62 43 44 66 44 45 67 45 46 65 46 47 64 47 48 6C 48 49 6D 49 4A 6F 4A 4B 6E 4B 4C 6A 4C 4D 6B 4D 4E 69 4E 4F 68 4F 50 78 50 51 79 51 52 7B 52 53 7A 53 54 7E 54 55 7F 55 56 7D 56 57 7C 57 58 74 58 59 75 59 5A 77 5A 5B 76 5B 5C 72 5C 5D 73 5D 5E 71 5E 5F 70 5F 60 50 60 61 51 61 62 53 62 63 52 63 64 56 64 65 57 65 66 55 66 67 54 67 68 5C 68 69 5D 69 6A 5F 6A 6B 5E 6B 6C 5A 6C 6D 5B 6D 6E 59 6E 6F 58 6F 70 48 70 71 49 71 72 4B 72 73 4A 73 74 4E 74 75 4F 75 76 4D 76 77 4C 77 78 44 78 79 45 79 7A 47 7A 7B 46 7B 7C 42 7C 7D 43 7D 7E 41 7E 7F 40 7F 80 C0 80 81 C1 81 82 C3 82 83 C2 83 84 C6 84 85 C7 85 86 C5 86 87 C4 87 88 CC 88 89 CD 89 8A CF 8A 8B CE 8B 8C CA 8C 8D CB 8D 8E C9 8E 8F C8 8F 90 D8 90 91 D9 91 92 DB 92 93 DA 93 94 DE 94 95 DF 95 96 DD 96 97 DC 97 98 D4 98 99 D5 99 9A D7 9A 9B D6 9B 9C D2 9C 9D D3 9D 9E D1 9E 9F D0 9F A0 F0 A0 A1 F1 A1 A2 F3 A2 A3 F2 A3 A4 F6 A4 A5 F7 A5 A6 F5 A6 A7 F4 A7 A8 FC A8 A9 FD A9 AA FF AA AB FE AB AC FA AC AD FB AD AE F9 AE AF F8 AF B0 E8 B0 B1 E9 B1 B2 EB B2 B3 EA B3 B4 EE B4 B5 EF B5 B6 ED B6 B7 EC B7 B8 E4 B8 B9 E5 B9 BA E7 BA BB E6 BB BC E2 BC BD E3 BD BE E1 BE BF E0 BF C0 A0 C0 C1 A1 C1 C2 A3 C2 C3 A2 C3 C4 A6 C4 C5 A7 C5 C6 A5 C6 C7 A4 C7 C8 AC C8 C9 AD C9 CA AF CA CB AE CB CC AA CC CD AB CD CE A9 CE CF A8 CF D0 B8 D0 D1 B9 D1 D2 BB D2 D3 BA D3 D4 BE D4 D5 BF D5 D6 BD D6 D7 BC D7 D8 B4 D8 D9 B5 D9 DA B7 DA DB B6 DB DC B2 DC DD B3 DD DE B1 DE DF B0 DF E0 90 E0 E1 91 E1 E2 93 E2 E3 92 E3 E4 96 E4 E5 97 E5 E6 95 E6 E7 94 E7 E8 9C E8 E9 9D E9 EA 9F EA EB 9E EB EC 9A EC ED 9B ED EE 99 EE EF 98 EF F0 88 F0 F1 89 F1 F2 8B F2 F3 8A F3 F4 8E F4 F5 8F F5 F6 8D F6 F7 8C F7 F8 84 F8 F9 85 F9 FA 87 FA FB 86 FB FC 82 FC FD 83 FD FE 81 FE FF 80 FF
Action!
PROC ToBinaryStr(BYTE n CHAR ARRAY s)
BYTE i
s(0)=8 i=8
SetBlock(s+1,8,'0)
WHILE n
DO
s(i)=(n&1)+'0
n==RSH 1
i==-1
OD
RETURN
PROC PrintB2(BYTE n)
IF n<10 THEN Put(32) FI
PrintB(n)
RETURN
PROC PrintBin5(BYTE n)
CHAR ARRAY s(9),sub(6)
ToBinaryStr(n,s)
SCopyS(sub,s,4,s(0))
Print(sub)
RETURN
BYTE FUNC Encode(BYTE n)
RETURN (n XOR (n RSH 1))
BYTE FUNC Decode(BYTE n)
BYTE res
res=n
DO
n==RSH 1
IF n THEN
res==XOR n
ELSE
EXIT
FI
OD
RETURN (res)
PROC Main()
BYTE i,g,b
CHAR ARRAY sep=" -> "
FOR i=0 TO 31
DO
PrintB2(i) Print(sep)
PrintBin5(i) Print(sep)
g=Encode(i)
PrintBin5(g) Print(sep)
b=Decode(g)
PrintBin5(b) Print(sep)
PrintB2(b) PutE()
OD
RETURN- Output:
Screenshot from Atari 8-bit computer
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
Ada
Demonstrates the use of shift operators. Code scalable to 6, 7 or 8 bits. Values are implemented with 8 bits according to representation clause of Unsigned_8 (check package Interfaces).
with Ada.Text_IO, Interfaces;
use Ada.Text_IO, Interfaces;
procedure Gray is
Bits : constant := 5; -- Change only this line for 6 or 7-bit encodings
subtype Values is Unsigned_8 range 0 .. 2 ** Bits - 1;
package Values_Io is new Ada.Text_IO.Modular_IO (Values);
function Encode (Binary : Values) return Values is
begin
return Binary xor Shift_Right (Binary, 1);
end Encode;
pragma Inline (Encode);
function Decode (Gray : Values) return Values is
Binary, Bit : Values;
Mask : Values := 2 ** (Bits - 1);
begin
Bit := Gray and Mask;
Binary := Bit;
for I in 2 .. Bits loop
Bit := Shift_Right (Bit, 1);
Mask := Shift_Right (Mask, 1);
Bit := (Gray and Mask) xor Bit;
Binary := Binary + Bit;
end loop;
return Binary;
end Decode;
pragma Inline (Decode);
HT : constant Character := Character'Val (9);
J : Values;
begin
Put_Line ("Num" & HT & "Binary" & HT & HT & "Gray" & HT & HT & "decoded");
for I in Values'Range loop
J := Encode (I);
Values_Io.Put (I, 4);
Put (": " & HT);
Values_Io.Put (I, Bits + 2, 2);
Put (" =>" & HT);
Values_Io.Put (J, Bits + 2, 2);
Put (" => " & HT);
Values_Io.Put (Decode (J), 4);
New_Line;
end loop;
end Gray;
Check compactness of assembly code generated by GNAT :http://pastebin.com/qtNjeQk9
- Output:
Num Binary Gray decoded 0: 2#0# => 2#0# => 0 1: 2#1# => 2#1# => 1 2: 2#10# => 2#11# => 2 3: 2#11# => 2#10# => 3 4: 2#100# => 2#110# => 4 5: 2#101# => 2#111# => 5 6: 2#110# => 2#101# => 6 7: 2#111# => 2#100# => 7 8: 2#1000# => 2#1100# => 8 9: 2#1001# => 2#1101# => 9 10: 2#1010# => 2#1111# => 10 11: 2#1011# => 2#1110# => 11 12: 2#1100# => 2#1010# => 12 13: 2#1101# => 2#1011# => 13 14: 2#1110# => 2#1001# => 14 15: 2#1111# => 2#1000# => 15 16: 2#10000# => 2#11000# => 16 17: 2#10001# => 2#11001# => 17 18: 2#10010# => 2#11011# => 18 19: 2#10011# => 2#11010# => 19 20: 2#10100# => 2#11110# => 20 21: 2#10101# => 2#11111# => 21 22: 2#10110# => 2#11101# => 22 23: 2#10111# => 2#11100# => 23 24: 2#11000# => 2#10100# => 24 25: 2#11001# => 2#10101# => 25 26: 2#11010# => 2#10111# => 26 27: 2#11011# => 2#10110# => 27 28: 2#11100# => 2#10010# => 28 29: 2#11101# => 2#10011# => 29 30: 2#11110# => 2#10001# => 30 31: 2#11111# => 2#10000# => 31
Aime
integer
gray_encode(integer n)
{
n ^ (n >> 1);
}
integer
gray_decode(integer n)
{
integer p;
p = n;
while (n >>= 1) {
p ^= n;
}
p;
}Demonstration code:
integer
main(void)
{
integer i, g, b;
i = 0;
while (i < 32) {
g = gray_encode(i);
b = gray_decode(g);
o_winteger(2, i);
o_text(": ");
o_fxinteger(5, 2, i);
o_text(" => ");
o_fxinteger(5, 2, g);
o_text(" => ");
o_fxinteger(5, 2, b);
o_text(": ");
o_winteger(2, b);
o_byte('\n');
i += 1;
}
return 0;
}- Output:
0: 00000 => 00000 => 00000: 0 1: 00001 => 00001 => 00001: 1 2: 00010 => 00011 => 00010: 2 3: 00011 => 00010 => 00011: 3 4: 00100 => 00110 => 00100: 4 5: 00101 => 00111 => 00101: 5 6: 00110 => 00101 => 00110: 6 7: 00111 => 00100 => 00111: 7 8: 01000 => 01100 => 01000: 8 9: 01001 => 01101 => 01001: 9 10: 01010 => 01111 => 01010: 10 11: 01011 => 01110 => 01011: 11 12: 01100 => 01010 => 01100: 12 13: 01101 => 01011 => 01101: 13 14: 01110 => 01001 => 01110: 14 15: 01111 => 01000 => 01111: 15 16: 10000 => 11000 => 10000: 16 17: 10001 => 11001 => 10001: 17 18: 10010 => 11011 => 10010: 18 19: 10011 => 11010 => 10011: 19 20: 10100 => 11110 => 10100: 20 21: 10101 => 11111 => 10101: 21 22: 10110 => 11101 => 10110: 22 23: 10111 => 11100 => 10111: 23 24: 11000 => 10100 => 11000: 24 25: 11001 => 10101 => 11001: 25 26: 11010 => 10111 => 11010: 26 27: 11011 => 10110 => 11011: 27 28: 11100 => 10010 => 11100: 28 29: 11101 => 10011 => 11101: 29 30: 11110 => 10001 => 11110: 30 31: 11111 => 10000 => 11111: 31
ALGOL 68
In Algol 68 the BITS mode is specifically designed for manipulating machine words as a row of bits so it is natural to treat Gray encoded integers as values of MODE BITS. The standard operator BIN (INT) : BITS converts an INT value to a BITS value. The ABS (BITS) : INT operator performs the reverse conversion, though it has not been needed for this task. It is also natural in the language for simple operations on values to be implemented as operators, rather than as functions, as in the program below.
BEGIN
OP GRAY = (BITS b) BITS : b XOR (b SHR 1); CO Convert to Gray code CO
OP YARG = (BITS g) BITS : CO Convert from Gray code CO
BEGIN
BITS b := g, mask := g SHR 1;
WHILE mask /= 2r0 DO b := b XOR mask; mask := mask SHR 1 OD;
b
END;
FOR i FROM 0 TO 31 DO
printf (($zd, ": ", 2(2r5d, " >= "), 2r5dl$, i, BIN i, GRAY BIN i, YARG GRAY BIN i))
OD
END- Output:
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
Amazing Hopper
Version: Hopper-BASIC.
#proto GrayEncode(_X_)
#synon _GrayEncode *getGrayEncode
#proto GrayDecode(_X_)
#synon _GrayDecode *getGrayDecode
#include <hbasic.h>
Begin
Gray=0
SizeBin(4) // size 5 bits: 0->4
Take (" # BINARY GRAY DECODE\n")
Take ("------------------------------\n"), and Print It
For Up( i := 0, 31, 1)
Print( LPad$(" ",2,Str$(i))," => ", Bin$(i)," => ")
get Gray Encode(i) and Copy to (Gray), get Binary; then Take(" => ")
now get Gray Decode( Gray ), get Binary, and Print It with a Newl
Next
End
Subrutines
Gray Encode(n)
Return (XorBit( RShift(1,n), n ))
Gray Decode(n)
p = n
While ( n )
n >>= 1
p != n
Wend
Return (p)- Output:
# BINARY GRAY DECODE ------------------------------ 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
APL
Generate the complete N-bit Gray sequence as a matrix:run
N←5
({(0,⍵)⍪1,⊖⍵}⍣N)(1 0⍴⍬)
- Output:
0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0
Encode and decode an individual integer:run
N←5
grayEncode←{a≠N↑(0,a←(N⍴2)⊤⍵)}
grayDecode←{2⊥≠⌿N N↑N(2×N)⍴⍵,0,N⍴0}
grayEncode 19
- Output:
1 1 0 1 0
Arturo
toGray: function [n]-> xor n shr n 1
fromGray: function [n][
p: n
while [n > 0][
n: shr n 1
p: xor p n
]
return p
]
loop 0..31 'num [
encoded: toGray num
decoded: fromGray encoded
print [
pad to :string num 2 ":"
pad as.binary num 5 "=>"
pad as.binary encoded 5 "=>"
pad as.binary decoded 5 ":"
pad to :string decoded 2
]
]
- Output:
0 : 0 => 0 => 0 : 0 1 : 1 => 1 => 1 : 1 2 : 10 => 11 => 10 : 2 3 : 11 => 10 => 11 : 3 4 : 100 => 110 => 100 : 4 5 : 101 => 111 => 101 : 5 6 : 110 => 101 => 110 : 6 7 : 111 => 100 => 111 : 7 8 : 1000 => 1100 => 1000 : 8 9 : 1001 => 1101 => 1001 : 9 10 : 1010 => 1111 => 1010 : 10 11 : 1011 => 1110 => 1011 : 11 12 : 1100 => 1010 => 1100 : 12 13 : 1101 => 1011 => 1101 : 13 14 : 1110 => 1001 => 1110 : 14 15 : 1111 => 1000 => 1111 : 15 16 : 10000 => 11000 => 10000 : 16 17 : 10001 => 11001 => 10001 : 17 18 : 10010 => 11011 => 10010 : 18 19 : 10011 => 11010 => 10011 : 19 20 : 10100 => 11110 => 10100 : 20 21 : 10101 => 11111 => 10101 : 21 22 : 10110 => 11101 => 10110 : 22 23 : 10111 => 11100 => 10111 : 23 24 : 11000 => 10100 => 11000 : 24 25 : 11001 => 10101 => 11001 : 25 26 : 11010 => 10111 => 11010 : 26 27 : 11011 => 10110 => 11011 : 27 28 : 11100 => 10010 => 11100 : 28 29 : 11101 => 10011 => 11101 : 29 30 : 11110 => 10001 => 11110 : 30 31 : 11111 => 10000 => 11111 : 31
AutoHotkey
gray_encode(n){
return n ^ (n >> 1)
}
gray_decode(n){
p := n
while (n >>= 1)
p ^= n
return p
}
BinString(n){
Loop 5
If ( n & ( 1 << (A_Index-1) ) )
o := "1" . o
else o := "0" . o
return o
}
Loop 32
n:=A_Index-1, out .= n " : " BinString(n) " => " BinString(e:=gray_encode(n))
. " => " BinString(gray_decode(e)) " => " BinString(n) "`n"
MsgBox % clipboard := out
- Output:
0 : 00000 => 00000 => 00000 => 00000 1 : 00001 => 00001 => 00001 => 00001 2 : 00010 => 00011 => 00010 => 00010 3 : 00011 => 00010 => 00011 => 00011 4 : 00100 => 00110 => 00100 => 00100 5 : 00101 => 00111 => 00101 => 00101 6 : 00110 => 00101 => 00110 => 00110 7 : 00111 => 00100 => 00111 => 00111 8 : 01000 => 01100 => 01000 => 01000 9 : 01001 => 01101 => 01001 => 01001 10 : 01010 => 01111 => 01010 => 01010 11 : 01011 => 01110 => 01011 => 01011 12 : 01100 => 01010 => 01100 => 01100 13 : 01101 => 01011 => 01101 => 01101 14 : 01110 => 01001 => 01110 => 01110 15 : 01111 => 01000 => 01111 => 01111 16 : 10000 => 11000 => 10000 => 10000 17 : 10001 => 11001 => 10001 => 10001 18 : 10010 => 11011 => 10010 => 10010 19 : 10011 => 11010 => 10011 => 10011 20 : 10100 => 11110 => 10100 => 10100 21 : 10101 => 11111 => 10101 => 10101 22 : 10110 => 11101 => 10110 => 10110 23 : 10111 => 11100 => 10111 => 10111 24 : 11000 => 10100 => 11000 => 11000 25 : 11001 => 10101 => 11001 => 11001 26 : 11010 => 10111 => 11010 => 11010 27 : 11011 => 10110 => 11011 => 11011 28 : 11100 => 10010 => 11100 => 11100 29 : 11101 => 10011 => 11101 => 11101 30 : 11110 => 10001 => 11110 => 11110 31 : 11111 => 10000 => 11111 => 11111
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)))
}
- Output:
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
BASIC
BBC BASIC
INSTALL @lib$+"STRINGLIB"
PRINT " Decimal Binary Gray Decoded"
FOR number% = 0 TO 31
gray% = FNgrayencode(number%)
PRINT number% " " FN_tobase(number%, 2, 5) ;
PRINT " " FN_tobase(gray%, 2, 5) FNgraydecode(gray%)
NEXT
END
DEF FNgrayencode(B%) = B% EOR (B% >>> 1)
DEF FNgraydecode(G%) : LOCAL B%
REPEAT B% EOR= G% : G% = G% >>> 1 : UNTIL G% = 0
= B%
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
- Output:
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
GW-BASIC
10 DEFINT A-Z
20 FOR I=0 TO 31
30 N=I:GOSUB 200:E=R:REM Encode
40 N=E:GOSUB 300:D=R:REM Decode
50 N=I:GOSUB 400:I$=R$:REM Binary format of input
60 N=E:GOSUB 400:E$=R$:REM Binary format of encoded value
70 N=D:GOSUB 400:D$=R$:REM Binary format of decoded value
80 PRINT USING "##: \ \ => \ \ => \ \ => ##";I;I$;E$;D$;D
90 NEXT
100 END
200 REM Gray encode
210 R = N XOR N\2
220 RETURN
300 REM Gray decode
310 R = N
320 N = N\2
330 IF N=0 THEN RETURN
340 R = R XOR N
350 GOTO 320
400 REM Binary format
410 R$ = ""
420 R$ = CHR$(48+(N AND 1))+R$
430 N = N\2
440 IF N=0 THEN RETURN ELSE 420
- Output:
0: 0 => 0 => 0 => 0 1: 1 => 1 => 1 => 1 2: 10 => 11 => 10 => 2 3: 11 => 10 => 11 => 3 4: 100 => 110 => 100 => 4 5: 101 => 111 => 101 => 5 6: 110 => 101 => 110 => 6 7: 111 => 100 => 111 => 7 8: 1000 => 1100 => 1000 => 8 9: 1001 => 1101 => 1001 => 9 10: 1010 => 1111 => 1010 => 10 11: 1011 => 1110 => 1011 => 11 12: 1100 => 1010 => 1100 => 12 13: 1101 => 1011 => 1101 => 13 14: 1110 => 1001 => 1110 => 14 15: 1111 => 1000 => 1111 => 15 16: 10000 => 11000 => 10000 => 16 17: 10001 => 11001 => 10001 => 17 18: 10010 => 11011 => 10010 => 18 19: 10011 => 11010 => 10011 => 19 20: 10100 => 11110 => 10100 => 20 21: 10101 => 11111 => 10101 => 21 22: 10110 => 11101 => 10110 => 22 23: 10111 => 11100 => 10111 => 23 24: 11000 => 10100 => 11000 => 24 25: 11001 => 10101 => 11001 => 25 26: 11010 => 10111 => 11010 => 26 27: 11011 => 10110 => 11011 => 27 28: 11100 => 10010 => 11100 => 28 29: 11101 => 10011 => 11101 => 29 30: 11110 => 10001 => 11110 => 30 31: 11111 => 10000 => 11111 => 31
Liberty BASIC
for r =0 to 31
print " Decimal "; using( "###", r); " is ";
B$ =dec2Bin$( r)
print " binary "; B$; ". Binary "; B$;
G$ =Bin2Gray$( dec2Bin$( r))
print " is "; G$; " in Gray code, or ";
B$ =Gray2Bin$( G$)
print B$; " in pure binary."
next r
end
function Bin2Gray$( bin$) ' Given a binary number as a string, returns Gray code as a string.
g$ =left$( bin$, 1)
for i =2 to len( bin$)
bitA =val( mid$( bin$, i -1, 1))
bitB =val( mid$( bin$, i, 1))
AXorB =bitA xor bitB
g$ =g$ +str$( AXorB)
next i
Bin2Gray$ =g$
end function
function Gray2Bin$( g$) ' Given a Gray code as a string, returns equivalent binary num.
' as a string
gl =len( g$)
b$ =left$( g$, 1)
for i =2 to len( g$)
bitA =val( mid$( b$, i -1, 1))
bitB =val( mid$( g$, i, 1))
AXorB =bitA xor bitB
b$ =b$ +str$( AXorB)
next i
Gray2Bin$ =right$( b$, gl)
end function
function dec2Bin$( num) ' Given an integer decimal, returns binary equivalent as a string
n =num
dec2Bin$ =""
while ( num >0)
dec2Bin$ =str$( num mod 2) +dec2Bin$
num =int( num /2)
wend
if ( n >255) then nBits =16 else nBits =8
dec2Bin$ =right$( "0000000000000000" +dec2Bin$, nBits) ' Pad to 8 bit or 16 bit
end function
function bin2Dec( b$) ' Given a binary number as a string, returns decimal equivalent num.
t =0
d =len( b$)
for k =d to 1 step -1
t =t +val( mid$( b$, k, 1)) *2^( d -k)
next k
bin2Dec =t
end function- Output:
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.
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%))
nextPureBasic
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
- Output:
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
VBScript
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
- Output:
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
XBasic
Intrinsic function BIN$ has been used.
' Gray code
PROGRAM "graycode"
VERSION "0.0001"
DECLARE FUNCTION Entry()
INTERNAL FUNCTION Encode(v&)
INTERNAL FUNCTION Decode(v&)
FUNCTION Entry()
PRINT "decimal binary gray decoded"
FOR i& = 0 TO 31
g& = Encode(i&)
d& = Decode(g&)
PRINT FORMAT$(" ##", i&); " "; BIN$(i&, 5); " "; BIN$(g&, 5);
PRINT " "; BIN$(d&, 5); FORMAT$(" ##", d&)
NEXT i&
END FUNCTION
FUNCTION Encode(v&)
END FUNCTION v& ^ (v& >> 1)
FUNCTION Decode(v&)
result& = 0
DO WHILE v& > 0
result& = result& ^ v&
v& = v& >> 1
LOOP
END FUNCTION result&
END PROGRAM
- Output:
decimal binary gray decoded 0 00000 00000 00000 0 1 00001 00001 00001 1 2 00010 00011 00010 2 3 00011 00010 00011 3 4 00100 00110 00100 4 5 00101 00111 00101 5 6 00110 00101 00110 6 7 00111 00100 00111 7 8 01000 01100 01000 8 9 01001 01101 01001 9 10 01010 01111 01010 10 11 01011 01110 01011 11 12 01100 01010 01100 12 13 01101 01011 01101 13 14 01110 01001 01110 14 15 01111 01000 01111 15 16 10000 11000 10000 16 17 10001 11001 10001 17 18 10010 11011 10010 18 19 10011 11010 10011 19 20 10100 11110 10100 20 21 10101 11111 10101 21 22 10110 11101 10110 22 23 10111 11100 10111 23 24 11000 10100 11000 24 25 11001 10101 11001 25 26 11010 10111 11010 26 27 11011 10110 11011 27 28 11100 10010 11100 28 29 11101 10011 11101 29 30 11110 10001 11110 30 31 11111 10000 11111 31
Batch File
:: 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
- Output:
# -> 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
bc
This language has no bitwise logic. We must repeat, with each bit, the exclusive-or calculation. This solution uses h % 2 and i % 2 to grab the low bits, and repeats if (h % 2 != i % 2) to check if the exclusive-or is one. Our encoding and decoding functions are identical except that h always comes from the decoded integer.
scale = 0 /* to use integer division */
/* encode Gray code */
define e(i) {
auto h, r
if (i <= 0) return 0
h = i / 2
r = e(h) * 2 /* recurse */
if (h % 2 != i % 2) r += 1 /* xor low bits of h, i */
return r
}
/* decode Gray code */
define d(i) {
auto h, r
if (i <= 0) return 0
h = d(i / 2) /* recurse */
r = h * 2
if (h % 2 != i % 2) r += 1 /* xor low bits of h, i */
return r
}
/* print i as 5 binary digits */
define p(i) {
auto d, d[]
for (d = 0; d <= 4; d++) {
d[d] = i % 2
i /= 2
}
for (d = 4; d >= 0; d--) {
if(d[d] == 0) "0"
if(d[d] == 1) "1"
}
}
for (i = 0; i < 32; i++) {
/* original */ t = p(i); " => "
/* encoded */ e = e(i); t = p(e); " => "
/* decoded */ d = d(e); t = p(d); "
"
}
quit
- Output:
00000 => 00000 => 00000 00001 => 00001 => 00001 00010 => 00011 => 00010 00011 => 00010 => 00011 00100 => 00110 => 00100 00101 => 00111 => 00101 00110 => 00101 => 00110 00111 => 00100 => 00111 01000 => 01100 => 01000 01001 => 01101 => 01001 01010 => 01111 => 01010 01011 => 01110 => 01011 01100 => 01010 => 01100 01101 => 01011 => 01101 01110 => 01001 => 01110 01111 => 01000 => 01111 10000 => 11000 => 10000 10001 => 11001 => 10001 10010 => 11011 => 10010 10011 => 11010 => 10011 10100 => 11110 => 10100 10101 => 11111 => 10101 10110 => 11101 => 10110 10111 => 11100 => 10111 11000 => 10100 => 11000 11001 => 10101 => 11001 11010 => 10111 => 11010 11011 => 10110 => 11011 11100 => 10010 => 11100 11101 => 10011 => 11101 11110 => 10001 => 11110 11111 => 10000 => 11111
BCPL
get "libhdr"
let grayEncode(n) = n neqv (n >> 1)
let grayDecode(n) = grayDecodeStep(0, n)
and grayDecodeStep(r, n) =
n = 0 -> r,
grayDecodeStep(r neqv n, n >> 1)
let binfmt(n) =
n = 0 -> 0,
(n & 1) + 10 * binfmt(n >> 1)
let printRow(n) be
$( let enc = grayEncode(n)
let dec = grayDecode(enc)
writef("%I2: %I5 => %I5 => %I5 => %I2*N",
n, binfmt(n), binfmt(enc), binfmt(dec), dec)
$)
let start() be
for i = 0 to 31 do printRow(i)- Output:
0: 0 => 0 => 0 => 0 1: 1 => 1 => 1 => 1 2: 10 => 11 => 10 => 2 3: 11 => 10 => 11 => 3 4: 100 => 110 => 100 => 4 5: 101 => 111 => 101 => 5 6: 110 => 101 => 110 => 6 7: 111 => 100 => 111 => 7 8: 1000 => 1100 => 1000 => 8 9: 1001 => 1101 => 1001 => 9 10: 1010 => 1111 => 1010 => 10 11: 1011 => 1110 => 1011 => 11 12: 1100 => 1010 => 1100 => 12 13: 1101 => 1011 => 1101 => 13 14: 1110 => 1001 => 1110 => 14 15: 1111 => 1000 => 1111 => 15 16: 10000 => 11000 => 10000 => 16 17: 10001 => 11001 => 10001 => 17 18: 10010 => 11011 => 10010 => 18 19: 10011 => 11010 => 10011 => 19 20: 10100 => 11110 => 10100 => 20 21: 10101 => 11111 => 10101 => 21 22: 10110 => 11101 => 10110 => 22 23: 10111 => 11100 => 10111 => 23 24: 11000 => 10100 => 11000 => 24 25: 11001 => 10101 => 11001 => 25 26: 11010 => 10111 => 11010 => 26 27: 11011 => 10110 => 11011 => 27 28: 11100 => 10010 => 11100 => 28 29: 11101 => 10011 => 11101 => 29 30: 11110 => 10001 => 11110 => 30 31: 11111 => 10000 => 11111 => 31
C
int gray_encode(int n) {
return n ^ (n >> 1);
}
int gray_decode(int n) {
int p = n;
while (n >>= 1) p ^= n;
return p;
}
Demonstration code:
#include <stdio.h>
/* Simple bool formatter, only good on range 0..31 */
void fmtbool(int n, char *buf) {
char *b = buf + 5;
*b=0;
do {
*--b = '0' + (n & 1);
n >>= 1;
} while (b != buf);
}
int main(int argc, char **argv) {
int i,g,b;
char bi[6],bg[6],bb[6];
for (i=0 ; i<32 ; i++) {
g = gray_encode(i);
b = gray_decode(g);
fmtbool(i,bi); fmtbool(g,bg); fmtbool(b,bb);
printf("%2d : %5s => %5s => %5s : %2d\n", i, bi, bg, bb, b);
}
return 0;
}
- Output:
0 : 00000 => 00000 => 00000 : 0 1 : 00001 => 00001 => 00001 : 1 2 : 00010 => 00011 => 00010 : 2 3 : 00011 => 00010 => 00011 : 3 4 : 00100 => 00110 => 00100 : 4 5 : 00101 => 00111 => 00101 : 5 6 : 00110 => 00101 => 00110 : 6 7 : 00111 => 00100 => 00111 : 7 8 : 01000 => 01100 => 01000 : 8 9 : 01001 => 01101 => 01001 : 9 10 : 01010 => 01111 => 01010 : 10 11 : 01011 => 01110 => 01011 : 11 12 : 01100 => 01010 => 01100 : 12 13 : 01101 => 01011 => 01101 : 13 14 : 01110 => 01001 => 01110 : 14 15 : 01111 => 01000 => 01111 : 15 16 : 10000 => 11000 => 10000 : 16 17 : 10001 => 11001 => 10001 : 17 18 : 10010 => 11011 => 10010 : 18 19 : 10011 => 11010 => 10011 : 19 20 : 10100 => 11110 => 10100 : 20 21 : 10101 => 11111 => 10101 : 21 22 : 10110 => 11101 => 10110 : 22 23 : 10111 => 11100 => 10111 : 23 24 : 11000 => 10100 => 11000 : 24 25 : 11001 => 10101 => 11001 : 25 26 : 11010 => 10111 => 11010 : 26 27 : 11011 => 10110 => 11011 : 27 28 : 11100 => 10010 => 11100 : 28 29 : 11101 => 10011 => 11101 : 29 30 : 11110 => 10001 => 11110 : 30 31 : 11111 => 10000 => 11111 : 31
C#
using System;
public class Gray {
public static ulong grayEncode(ulong n) {
return n^(n>>1);
}
public static ulong grayDecode(ulong n) {
ulong i=1<<8*64-2; //long is 64-bit
ulong p, b=p=n&i;
while((i>>=1)>0)
b|=p=n&i^p>>1;
return b;
}
public static void Main(string[] args) {
Console.WriteLine("Number\tBinary\tGray\tDecoded");
for(ulong i=0;i<32;i++) {
Console.WriteLine(string.Format("{0}\t{1}\t{2}\t{3}", i, Convert.ToString((long)i, 2), Convert.ToString((long)grayEncode(i), 2), grayDecode(grayEncode(i))));
}
}
}- Output:
Number Binary Gray Decoded 0 0 0 0 1 1 1 1 2 10 11 2 3 11 10 3 4 100 110 4 5 101 111 5 6 110 101 6 7 111 100 7 8 1000 1100 8 9 1001 1101 9 10 1010 1111 10 11 1011 1110 11 12 1100 1010 12 13 1101 1011 13 14 1110 1001 14 15 1111 1000 15 16 10000 11000 16 17 10001 11001 17 18 10010 11011 18 19 10011 11010 19 20 10100 11110 20 21 10101 11111 21 22 10110 11101 22 23 10111 11100 23 24 11000 10100 24 25 11001 10101 25 26 11010 10111 26 27 11011 10110 27 28 11100 10010 28 29 11101 10011 29 30 11110 10001 30 31 11111 10000 31
C++
#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";
}
}
- Output:
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
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)
Common Lisp
(defun gray-encode (n)
(logxor n (ash n -1)))
(defun gray-decode (n)
(do ((p n (logxor p n)))
((zerop n) p)
(setf n (ash n -1))))
(loop for i to 31 do
(let* ((g (gray-encode i)) (b (gray-decode g)))
(format t "~2d:~6b =>~6b =>~6b :~2d~%" i i g b b)))
- Output:
0: 0 => 0 => 0 : 0 1: 1 => 1 => 1 : 1 2: 10 => 11 => 10 : 2 3: 11 => 10 => 11 : 3 4: 100 => 110 => 100 : 4 5: 101 => 111 => 101 : 5 6: 110 => 101 => 110 : 6 7: 111 => 100 => 111 : 7 8: 1000 => 1100 => 1000 : 8 9: 1001 => 1101 => 1001 : 9 10: 1010 => 1111 => 1010 :10 11: 1011 => 1110 => 1011 :11 12: 1100 => 1010 => 1100 :12 13: 1101 => 1011 => 1101 :13 14: 1110 => 1001 => 1110 :14 15: 1111 => 1000 => 1111 :15 16: 10000 => 11000 => 10000 :16 17: 10001 => 11001 => 10001 :17 18: 10010 => 11011 => 10010 :18 19: 10011 => 11010 => 10011 :19 20: 10100 => 11110 => 10100 :20 21: 10101 => 11111 => 10101 :21 22: 10110 => 11101 => 10110 :22 23: 10111 => 11100 => 10111 :23 24: 11000 => 10100 => 11000 :24 25: 11001 => 10101 => 11001 :25 26: 11010 => 10111 => 11010 :26 27: 11011 => 10110 => 11011 :27 28: 11100 => 10010 => 11100 :28 29: 11101 => 10011 => 11101 :29 30: 11110 => 10001 => 11110 :30 31: 11111 => 10000 => 11111 :31
Component Pascal
BlackBox Component Builder
MODULE GrayCodes;
IMPORT StdLog,SYSTEM;
PROCEDURE Encode*(i: INTEGER; OUT x: INTEGER);
VAR
j: INTEGER;
s,r: SET;
BEGIN
s := BITS(i);j := MAX(SET);
WHILE (j >= 0) & ~(j IN s) DO DEC(j) END;
r := {};IF j >= 0 THEN INCL(r,j) END;
WHILE j > 0 DO
IF ((j IN s) & ~(j - 1 IN s)) OR (~(j IN s) & (j - 1 IN s)) THEN INCL(r,j-1) END;
DEC(j)
END;
x := SYSTEM.VAL(INTEGER,r)
END Encode;
PROCEDURE Decode*(x: INTEGER; OUT i: INTEGER);
VAR
j: INTEGER;
s,r: SET;
BEGIN
s := BITS(x);r:={};j := MAX(SET);
WHILE (j >= 0) & ~(j IN s) DO DEC(j) END;
IF j >= 0 THEN INCL(r,j) END;
WHILE j > 0 DO
IF ((j IN r) & ~(j - 1 IN s)) OR (~(j IN r) & (j - 1 IN s)) THEN INCL(r,j-1) END;
DEC(j)
END;
i := SYSTEM.VAL(INTEGER,r);
END Decode;
PROCEDURE Do*;
VAR
grayCode,binCode: INTEGER;
i: INTEGER;
BEGIN
StdLog.String(" i ");StdLog.String(" bin code ");StdLog.String(" gray code ");StdLog.Ln;
StdLog.String("---");StdLog.String(" ----------------");StdLog.String(" ---------------");StdLog.Ln;
FOR i := 0 TO 32 DO;
Encode(i,grayCode);Decode(grayCode,binCode);
StdLog.IntForm(i,10,3,' ',FALSE);
StdLog.IntForm(binCode,2,16,' ',TRUE);
StdLog.IntForm(grayCode,2,16,' ',TRUE);
StdLog.Ln;
END
END Do;
END GrayCodes.
Execute: ^QGrayCodes.Do
- Output:
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
Cowgol
include "cowgol.coh";
sub gray_encode(n: uint8): (r: uint8) is
r := n ^ n >> 1;
end sub;
sub gray_decode(n: uint8): (r: uint8) is
r := n;
while n > 0 loop
n := n >> 1;
r := r ^ n;
end loop;
end sub;
sub print_binary(n: uint8) is
var buf: uint8[9];
var ptr := &buf[8];
[ptr] := 0;
loop
ptr := @prev ptr;
[ptr] := (n & 1) + '0';
n := n >> 1;
if n == 0 then break; end if;
end loop;
print(ptr);
end sub;
sub print_row(n: uint8) is
print_i8(n);
print(":\t");
print_binary(n);
print("\t=>\t");
var gray_code := gray_encode(n);
print_binary(gray_code);
print("\t=>\t");
var decoded := gray_decode(gray_code);
print_i8(decoded);
print_nl();
end sub;
var i: uint8 := 0;
while i <= 31 loop
print_row(i);
i := i + 1;
end loop;- Output:
0: 0 => 0 => 0 1: 1 => 1 => 1 2: 10 => 11 => 2 3: 11 => 10 => 3 4: 100 => 110 => 4 5: 101 => 111 => 5 6: 110 => 101 => 6 7: 111 => 100 => 7 8: 1000 => 1100 => 8 9: 1001 => 1101 => 9 10: 1010 => 1111 => 10 11: 1011 => 1110 => 11 12: 1100 => 1010 => 12 13: 1101 => 1011 => 13 14: 1110 => 1001 => 14 15: 1111 => 1000 => 15 16: 10000 => 11000 => 16 17: 10001 => 11001 => 17 18: 10010 => 11011 => 18 19: 10011 => 11010 => 19 20: 10100 => 11110 => 20 21: 10101 => 11111 => 21 22: 10110 => 11101 => 22 23: 10111 => 11100 => 23 24: 11000 => 10100 => 24 25: 11001 => 10101 => 25 26: 11010 => 10111 => 26 27: 11011 => 10110 => 27 28: 11100 => 10010 => 28 29: 11101 => 10011 => 29 30: 11110 => 10001 => 30 31: 11111 => 10000 => 31
Crystal
def gray_encode(bin)
bin ^ (bin >> 1)
end
def gray_decode(gray)
bin = gray
while gray > 0
gray >>= 1
bin ^= gray
end
bin
end
Demonstration code:
(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
- Output:
0 : 00000 => 00000 => 00000 : 0 1 : 00001 => 00001 => 00001 : 1 2 : 00010 => 00011 => 00010 : 2 3 : 00011 => 00010 => 00011 : 3 4 : 00100 => 00110 => 00100 : 4 5 : 00101 => 00111 => 00101 : 5 6 : 00110 => 00101 => 00110 : 6 7 : 00111 => 00100 => 00111 : 7 8 : 01000 => 01100 => 01000 : 8 9 : 01001 => 01101 => 01001 : 9 10 : 01010 => 01111 => 01010 : 10 11 : 01011 => 01110 => 01011 : 11 12 : 01100 => 01010 => 01100 : 12 13 : 01101 => 01011 => 01101 : 13 14 : 01110 => 01001 => 01110 : 14 15 : 01111 => 01000 => 01111 : 15 16 : 10000 => 11000 => 10000 : 16 17 : 10001 => 11001 => 10001 : 17 18 : 10010 => 11011 => 10010 : 18 19 : 10011 => 11010 => 10011 : 19 20 : 10100 => 11110 => 10100 : 20 21 : 10101 => 11111 => 10101 : 21 22 : 10110 => 11101 => 10110 : 22 23 : 10111 => 11100 => 10111 : 23 24 : 11000 => 10100 => 11000 : 24 25 : 11001 => 10101 => 11001 : 25 26 : 11010 => 10111 => 11010 : 26 27 : 11011 => 10110 => 11011 : 27 28 : 11100 => 10010 => 11100 : 28 29 : 11101 => 10011 => 11101 : 29 30 : 11110 => 10001 => 11110 : 30 31 : 11111 => 10000 => 11111 : 31
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);
}
}
- Output:
N N2 enc dec2 dec 0: 0 => 0 => 0: 0 1: 1 => 1 => 1: 1 2: 10 => 11 => 10: 2 3: 11 => 10 => 11: 3 4: 100 => 110 => 100: 4 5: 101 => 111 => 101: 5 6: 110 => 101 => 110: 6 7: 111 => 100 => 111: 7 8: 1000 => 1100 => 1000: 8 9: 1001 => 1101 => 1001: 9 10: 1010 => 1111 => 1010: 10 11: 1011 => 1110 => 1011: 11 12: 1100 => 1010 => 1100: 12 13: 1101 => 1011 => 1101: 13 14: 1110 => 1001 => 1110: 14 15: 1111 => 1000 => 1111: 15 16: 10000 => 11000 => 10000: 16 17: 10001 => 11001 => 10001: 17 18: 10010 => 11011 => 10010: 18 19: 10011 => 11010 => 10011: 19 20: 10100 => 11110 => 10100: 20 21: 10101 => 11111 => 10101: 21 22: 10110 => 11101 => 10110: 22 23: 10111 => 11100 => 10111: 23 24: 11000 => 10100 => 11000: 24 25: 11001 => 10101 => 11001: 25 26: 11010 => 10111 => 11010: 26 27: 11011 => 10110 => 11011: 27 28: 11100 => 10010 => 11100: 28 29: 11101 => 10011 => 11101: 29 30: 11110 => 10001 => 11110: 30 31: 11111 => 10000 => 11111: 31
Compile-Time version
This version uses a compile time generated translation table, if maximum bit width of the numbers is a constant. The encoding table is generated recursively, then the decode table is calculated and appended. Same output.
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);
}
}
Short Functional-Style Generator
import std.stdio, std.algorithm, std.range;
string[] g(in uint n) pure nothrow {
return n ? g(n - 1).map!q{'0' ~ a}.array ~
g(n - 1).retro.map!q{'1' ~ a}.array
: [""];
}
void main() {
4.g.writeln;
}
- Output:
["0000", "0001", "0011", "0010", "0110", "0111", "0101", "0100", "1100", "1101", "1111", "1110", "1010", "1011", "1001", "1000"]
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.
- Output:
decimal binary gray decoded 0 00000 00000 00000 0 1 00001 00001 00001 1 2 00010 00011 00010 2 3 00011 00010 00011 3 4 00100 00110 00100 4 5 00101 00111 00101 5 6 00110 00101 00110 6 7 00111 00100 00111 7 8 01000 01100 01000 8 9 01001 01101 01001 9 10 01010 01111 01010 10 11 01011 01110 01011 11 12 01100 01010 01100 12 13 01101 01011 01101 13 14 01110 01001 01110 14 15 01111 01000 01111 15 16 10000 11000 10000 16 17 10001 11001 10001 17 18 10010 11011 10010 18 19 10011 11010 10011 19 20 10100 11110 10100 20 21 10101 11111 10101 21 22 10110 11101 10110 22 23 10111 11100 10111 23 24 11000 10100 11000 24 25 11001 10101 11001 25 26 11010 10111 11010 26 27 11011 10110 11011 27 28 11100 10010 11100 28 29 11101 10011 11101 29 30 11110 10001 11110 30 31 11111 10000 11111 31
Draco
proc gray_encode(word n) word:
n >< (n >> 1)
corp
proc gray_decode(word n) word:
word r;
r := n;
while
n := n >> 1;
n > 0
do
r := r >< n
od;
r
corp
proc main() void:
word i, enc, dec;
for i from 0 upto 31 do
enc := gray_encode(i);
dec := gray_decode(enc);
writeln(i:2, ": ",
i:b:5, " => ",
enc:b:5, " => ",
dec:b:5, " => ",
dec:2)
od
corp- Output:
0: 0 => 0 => 0 => 0 1: 1 => 1 => 1 => 1 2: 10 => 11 => 10 => 2 3: 11 => 10 => 11 => 3 4: 100 => 110 => 100 => 4 5: 101 => 111 => 101 => 5 6: 110 => 101 => 110 => 6 7: 111 => 100 => 111 => 7 8: 1000 => 1100 => 1000 => 8 9: 1001 => 1101 => 1001 => 9 10: 1010 => 1111 => 1010 => 10 11: 1011 => 1110 => 1011 => 11 12: 1100 => 1010 => 1100 => 12 13: 1101 => 1011 => 1101 => 13 14: 1110 => 1001 => 1110 => 14 15: 1111 => 1000 => 1111 => 15 16: 10000 => 11000 => 10000 => 16 17: 10001 => 11001 => 10001 => 17 18: 10010 => 11011 => 10010 => 18 19: 10011 => 11010 => 10011 => 19 20: 10100 => 11110 => 10100 => 20 21: 10101 => 11111 => 10101 => 21 22: 10110 => 11101 => 10110 => 22 23: 10111 => 11100 => 10111 => 23 24: 11000 => 10100 => 11000 => 24 25: 11001 => 10101 => 11001 => 25 26: 11010 => 10111 => 11010 => 26 27: 11011 => 10110 => 11011 => 27 28: 11100 => 10010 => 11100 => 28 29: 11101 => 10011 => 11101 => 29 30: 11110 => 10001 => 11110 => 30 31: 11111 => 10000 => 11111 => 31
DWScript
function Encode(v : Integer) : Integer;
begin
Result := v xor (v shr 1);
end;
function Decode(v : Integer) : Integer;
begin
Result := 0;
while v>0 do begin
Result := Result xor v;
v := v shr 1;
end;
end;
PrintLn('decimal binary gray decoded');
var i : Integer;
for i:=0 to 31 do begin
var g := Encode(i);
var d := Decode(g);
PrintLn(Format(' %2d %s %s %s %2d',
[i, IntToBin(i, 5), IntToBin(g, 5), IntToBin(d, 5), d]));
end;
EasyLang
func$ bin n .
for i to 5
r$ = n mod 2 & r$
n = n div 2
.
return r$
.
func gray_encode b .
return bitxor b bitshift b -1
.
func gray_decode g .
b = g
while g > 0
g = bitshift g -1
b = bitxor b g
.
return b
.
for n = 0 to 31
g = gray_encode n
b = gray_decode g
print bin n & " -> " & bin g & " -> " & bin b
.
- Output:
00000 -> 00000 -> 00000 00001 -> 00001 -> 00001 00010 -> 00011 -> 00010 00011 -> 00010 -> 00011 00100 -> 00110 -> 00100 00101 -> 00111 -> 00101 00110 -> 00101 -> 00110 00111 -> 00100 -> 00111 01000 -> 01100 -> 01000 01001 -> 01101 -> 01001 01010 -> 01111 -> 01010 01011 -> 01110 -> 01011 01100 -> 01010 -> 01100 01101 -> 01011 -> 01101 01110 -> 01001 -> 01110 01111 -> 01000 -> 01111 10000 -> 11000 -> 10000 10001 -> 11001 -> 10001 10010 -> 11011 -> 10010 10011 -> 11010 -> 10011 10100 -> 11110 -> 10100 10101 -> 11111 -> 10101 10110 -> 11101 -> 10110 10111 -> 11100 -> 10111 11000 -> 10100 -> 11000 11001 -> 10101 -> 11001 11010 -> 10111 -> 11010 11011 -> 10110 -> 11011 11100 -> 10010 -> 11100 11101 -> 10011 -> 11101 11110 -> 10001 -> 11110 11111 -> 10000 -> 11111
EDSAC order code
The only logical operation on EDSAC was AND, or "collate" as it was called, but it's possible to calculate XOR from AND together with arithmetical operations. For converting Gray code to binary on EDSAC, I couldn't think up any shorter method than the one below.
[Gray code task for Rosetta Code.
EDSAC program, Initial Orders 2.]
[Library subroutine M3. Prints header at load time,
then M3 and header are overwritten.]
PFGKIFAFRDLFUFOFE@A6FG@E8FEZPF
*BINARY!!GRAY!!!!ROUND!TRIP@&
..PK [after header, blank tape and PK (WWG, 1951, p. 91)]
T64K [load at location 64 (arbitrary choice)]
GK [set @ (theta) parameter]
[Subroutine to print 5-bit number in binary.
Input: 1F = number (preserved) in low 5 bits.
Workspace: 0F, 4F.]
[0] A3F T17@ [plant return link as usual]
H19@ [mult reg := mask to remove top 4 bits]
A1F [acc := code in low 5 bits]
L32F [shift 7 left]
TF [store in workspace]
S18@ [initialize negative count of digits]
[7] T4F [update negative count]
AF LD TF [shift workspace 1 left]
CF [remove top 4 bits]
TF [store result]
OF [print character '0' or '1' in top 5 bits]
A4F A2F G7@ [inc count, loop if not yet 0]
[17] ZF [{planted} jump back to caller]
[18] P5F [addres field = number of bits]
[19] Q2047D [00001111111111111 binary]
[Subroutine to convert binary code to Gray code.
Input: 1F = binary code (preserved).
Output: 0F = Gray code.]
[20] A3F T33@ [plant return link as usual]
A1F RD TF [0F := binary shifted 1 right]
[One way to get p XOR q on EDSAC: Let r = p AND q.
Then p XOR q = (p - r) + (q - r) = -(2r - p - q).]
HF [mult reg := 0F]
C1F [acc := 0F AND 1F]
LD [times 2]
SF S1F [subtract 0F and 1F]
TF SF TF [return result negated]
[33] ZF [{planted} jump back to caller]
[Subroutine to convert 5-digit Gray code to binary.
Uses a chain of XORs.
If bits in Gray code are ghijk then bits in binary are
g, g.h, g.h.i, g.h.i.j, g.h.i.j.k where dot means XOR.
Input: 1F = Gray code (preserved).
Output: 0F = binary code.
Workspace: 4F, 5F.]
[34] A3F T55@ [plant return link as usual]
A1F UF [initialize result to Gray code]
T5F [5F = shifted Gray code, shift = 0 initialiy]
S56@ [initialize negative count]
[40] T4F [update negative count]
HF [mult reg := partial result]
A5F RD T5F [shift Gray code 1 right]
[Form 5F XOR 0F as in the previous subroutine]
C5F LD SF S5F TF SF
TF [update partial result]
A4F A2F G40@ [inc count, loop back if not yet 0]
[55] ZF [{planted} jump back to caller]
[56] P4F [address field = 1 less than number of bits]
[Main routine]
[Variable]
[57] PF [binary code is in low 5 bits]
[Constants]
[58] P16F [exclusive maximum code, 100000 binary]
[59] PD [17-bit 1]
[60] #F [teleprinter figures mode]
[61] !F [space]
[62] @F [carriage return]
[63] &F [line feed]
[Enter with acc = 0]
[64] O60@ [set teleprinter to figures]
S58@ [to make acc = 0 after next instruction]
[66] A58@ [loop: restore acc after test below]
U57@ T1F [save binary code, and pass it to print soubroutine]
[69] A69@ G@ [print binary code]
O61@ O61@ O61@ [print 3 spaces]
[74] A74@ G20@ [convert binary (still in 1F) to Gray]
AF T1F [pass Gray code to print subroutine]
[78] A78@ G@ [print Gray code]
O61@ O61@ O61@ [print 3 spaces]
[83] A83@ G34@ [convert Gray (still in 1F) back to binary]
AF T1F [pass binary code to print subroutine]
[87] A87@ G@ [print binary]
O62@ O63@ [print CR, LF]
A57@ A59@ [inc binary]
S58@ [test for all done]
G66@ [loop back if not]
O60@ [dummy character to flush teleprinter buffer]
ZF [stop]
E64Z [define entry point]
PF [acc = 0 on entry]
[end]- Output:
BINARY GRAY ROUND TRIP 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
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)
output is the same as "Erlang".
Erlang
-module(gray).
-export([encode/1, decode/1]).
encode(N) -> N bxor (N bsr 1).
decode(G) -> decode(G,0).
decode(0,N) -> N;
decode(G,N) -> decode(G bsr 1, G bxor N).
Demonstration code:
-module(testgray).
test_encode(N) ->
G = gray:encode(N),
D = gray:decode(G),
io:fwrite("~2B : ~5.2.0B : ~5.2.0B : ~5.2.0B : ~2B~n", [N, N, G, D, D]).
test_encode(N, N) -> [];
test_encode(I, N) when I < N -> test_encode(I), test_encode(I+1, N).
main(_) -> test_encode(0,32).
- Output:
0 : 00000 : 00000 : 00000 : 0 1 : 00001 : 00001 : 00001 : 1 2 : 00010 : 00011 : 00010 : 2 3 : 00011 : 00010 : 00011 : 3 4 : 00100 : 00110 : 00100 : 4 5 : 00101 : 00111 : 00101 : 5 6 : 00110 : 00101 : 00110 : 6 7 : 00111 : 00100 : 00111 : 7 8 : 01000 : 01100 : 01000 : 8 9 : 01001 : 01101 : 01001 : 9 10 : 01010 : 01111 : 01010 : 10 11 : 01011 : 01110 : 01011 : 11 12 : 01100 : 01010 : 01100 : 12 13 : 01101 : 01011 : 01101 : 13 14 : 01110 : 01001 : 01110 : 14 15 : 01111 : 01000 : 01111 : 15 16 : 10000 : 11000 : 10000 : 16 17 : 10001 : 11001 : 10001 : 17 18 : 10010 : 11011 : 10010 : 18 19 : 10011 : 11010 : 10011 : 19 20 : 10100 : 11110 : 10100 : 20 21 : 10101 : 11111 : 10101 : 21 22 : 10110 : 11101 : 10110 : 22 23 : 10111 : 11100 : 10111 : 23 24 : 11000 : 10100 : 11000 : 24 25 : 11001 : 10101 : 11001 : 25 26 : 11010 : 10111 : 11010 : 26 27 : 11011 : 10110 : 11011 : 27 28 : 11100 : 10010 : 11100 : 28 29 : 11101 : 10011 : 11101 : 29 30 : 11110 : 10001 : 11110 : 30 31 : 11111 : 10000 : 11111 : 31
Euphoria
function gray_encode(integer n)
return xor_bits(n,floor(n/2))
end function
function gray_decode(integer n)
integer g
g = 0
while n > 0 do
g = xor_bits(g,n)
n = floor(n/2)
end while
return g
end function
function dcb(integer n)
atom d,m
d = 0
m = 1
while n do
d += remainder(n,2)*m
n = floor(n/2)
m *= 10
end while
return d
end function
integer j
for i = #0 to #1F do
printf(1,"%05d => ",dcb(i))
j = gray_encode(i)
printf(1,"%05d => ",dcb(j))
j = gray_decode(j)
printf(1,"%05d\n",dcb(j))
end for- Output:
00000 => 00000 => 00000 00001 => 00001 => 00001 00010 => 00011 => 00010 00011 => 00010 => 00011 00100 => 00110 => 00100 00101 => 00111 => 00101 00110 => 00101 => 00110 00111 => 00100 => 00111 01000 => 01100 => 01000 01001 => 01101 => 01001 01010 => 01111 => 01010 01011 => 01110 => 01011 01100 => 01010 => 01100 01101 => 01011 => 01101 01110 => 01001 => 01110 01111 => 01000 => 01111 10000 => 11000 => 10000 10001 => 11001 => 10001 10010 => 11011 => 10010 10011 => 11010 => 10011 10100 => 11110 => 10100 10101 => 11111 => 10101 10110 => 11101 => 10110 10111 => 11100 => 10111 11000 => 10100 => 11000 11001 => 10101 => 11001 11010 => 10111 => 11010 11011 => 10110 => 11011 11100 => 10010 => 11100 11101 => 10011 => 11101 11110 => 10001 => 11110 11111 => 10000 => 11111
F#
The Function
// Functıons to translate bınary to grey code and vv. Nigel Galloway: December 7th., 2018
let grayCode,invGrayCode=let fN g (n:uint8)=n^^^(n>>>g) in ((fN 1),(fN 1>>fN 2>>fN 4))
The Task
[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))
- Output:
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
Factor
Translation of C.
USING: math.ranges locals ;
IN: rosetta-gray
: gray-encode ( n -- n' ) dup -1 shift bitxor ;
:: gray-decode ( n! -- n' )
n :> p!
[ n -1 shift dup n! 0 = not ] [
p n bitxor p!
] while
p ;
: main ( -- )
-1 32 [a,b] [ dup [ >bin ] [ gray-encode ] bi [ >bin ] [ gray-decode ] bi 4array . ] each ;
MAIN: main
Running above code prints:
{ -1 "-1" "0" 0 }
{ 0 "0" "0" 0 }
{ 1 "1" "1" 1 }
{ 2 "10" "11" 2 }
{ 3 "11" "10" 3 }
{ 4 "100" "110" 4 }
{ 5 "101" "111" 5 }
{ 6 "110" "101" 6 }
{ 7 "111" "100" 7 }
{ 8 "1000" "1100" 8 }
{ 9 "1001" "1101" 9 }
{ 10 "1010" "1111" 10 }
{ 11 "1011" "1110" 11 }
{ 12 "1100" "1010" 12 }
{ 13 "1101" "1011" 13 }
{ 14 "1110" "1001" 14 }
{ 15 "1111" "1000" 15 }
{ 16 "10000" "11000" 16 }
{ 17 "10001" "11001" 17 }
{ 18 "10010" "11011" 18 }
{ 19 "10011" "11010" 19 }
{ 20 "10100" "11110" 20 }
{ 21 "10101" "11111" 21 }
{ 22 "10110" "11101" 22 }
{ 23 "10111" "11100" 23 }
{ 24 "11000" "10100" 24 }
{ 25 "11001" "10101" 25 }
{ 26 "11010" "10111" 26 }
{ 27 "11011" "10110" 27 }
{ 28 "11100" "10010" 28 }
{ 29 "11101" "10011" 29 }
{ 30 "11110" "10001" 30 }
{ 31 "11111" "10000" 31 }
{ 32 "100000" "110000" 32 }
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.
: >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
- Output:
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
Fortran
Using MIL-STD-1753 extensions in Fortran 77, and formulas found at OEIS for direct and inverse Gray code :
PROGRAM GRAY
IMPLICIT NONE
INTEGER IGRAY,I,J,K
CHARACTER*5 A,B,C
DO 10 I=0,31
J=IGRAY(I,1)
K=IGRAY(J,-1)
CALL BINARY(A,I,5)
CALL BINARY(B,J,5)
CALL BINARY(C,K,5)
PRINT 99,I,A,B,C,K
10 CONTINUE
99 FORMAT(I2,3H : ,A5,4H => ,A5,4H => ,A5,3H : ,I2)
END
FUNCTION IGRAY(N,D)
IMPLICIT NONE
INTEGER D,K,N,IGRAY
IF(D.LT.0) GO TO 10
IGRAY=IEOR(N,ISHFT(N,-1))
RETURN
10 K=N
IGRAY=0
20 IGRAY=IEOR(IGRAY,K)
K=K/2
IF(K.NE.0) GO TO 20
END
SUBROUTINE BINARY(S,N,K)
IMPLICIT NONE
INTEGER I,K,L,N
CHARACTER*(*) S
L=LEN(S)
DO 10 I=0,K-1
C The following line may replace the next block-if,
C on machines using ASCII code :
C S(L-I:L-I)=CHAR(48+IAND(1,ISHFT(N,-I)))
C On EBCDIC machines, use 240 instead of 48.
IF(BTEST(N,I)) THEN
S(L-I:L-I)='1'
ELSE
S(L-I:L-I)='0'
END IF
10 CONTINUE
S(1:L-K)=''
END
0 : 00000 => 00000 => 00000 : 0 1 : 00001 => 00001 => 00001 : 1 2 : 00010 => 00011 => 00010 : 2 3 : 00011 => 00010 => 00011 : 3 4 : 00100 => 00110 => 00100 : 4 5 : 00101 => 00111 => 00101 : 5 6 : 00110 => 00101 => 00110 : 6 7 : 00111 => 00100 => 00111 : 7 8 : 01000 => 01100 => 01000 : 8 9 : 01001 => 01101 => 01001 : 9 10 : 01010 => 01111 => 01010 : 10 11 : 01011 => 01110 => 01011 : 11 12 : 01100 => 01010 => 01100 : 12 13 : 01101 => 01011 => 01101 : 13 14 : 01110 => 01001 => 01110 : 14 15 : 01111 => 01000 => 01111 : 15 16 : 10000 => 11000 => 10000 : 16 17 : 10001 => 11001 => 10001 : 17 18 : 10010 => 11011 => 10010 : 18 19 : 10011 => 11010 => 10011 : 19 20 : 10100 => 11110 => 10100 : 20 21 : 10101 => 11111 => 10101 : 21 22 : 10110 => 11101 => 10110 : 22 23 : 10111 => 11100 => 10111 : 23 24 : 11000 => 10100 => 11000 : 24 25 : 11001 => 10101 => 11001 : 25 26 : 11010 => 10111 => 11010 : 26 27 : 11011 => 10110 => 11011 : 27 28 : 11100 => 10010 => 11100 : 28 29 : 11101 => 10011 => 11101 : 29 30 : 11110 => 10001 => 11110 : 30 31 : 11111 => 10000 => 11111 : 31
Frink
Frink has built-in functions to convert to and from binary reflected Gray code.
for i=0 to 31
{
gray = binaryToGray[i]
back = grayToBinary[gray]
println[(i->binary) + "\t" + (gray->binary) + "\t" + (back->binary)]
}Go
Binary reflected, as described in the task. Reading down through the solutions, the Euphoria decode algorithm caught my eye as being concise and easy to read.
package main
import "fmt"
func enc(b int) int {
return b ^ b>>1
}
func dec(g int) (b int) {
for ; g != 0; g >>= 1 {
b ^= g
}
return
}
func main() {
fmt.Println("decimal binary gray decoded")
for b := 0; b < 32; b++ {
g := enc(b)
d := dec(g)
fmt.Printf(" %2d %05b %05b %05b %2d\n", b, b, g, d, d)
}
}
- Output:
decimal binary gray decoded 0 00000 00000 00000 0 1 00001 00001 00001 1 2 00010 00011 00010 2 3 00011 00010 00011 3 4 00100 00110 00100 4 5 00101 00111 00101 5 6 00110 00101 00110 6 7 00111 00100 00111 7 8 01000 01100 01000 8 9 01001 01101 01001 9 10 01010 01111 01010 10 11 01011 01110 01011 11 12 01100 01010 01100 12 13 01101 01011 01101 13 14 01110 01001 01110 14 15 01111 01000 01111 15 16 10000 11000 10000 16 17 10001 11001 10001 17 18 10010 11011 10010 18 19 10011 11010 10011 19 20 10100 11110 10100 20 21 10101 11111 10101 21 22 10110 11101 10110 22 23 10111 11100 10111 23 24 11000 10100 11000 24 25 11001 10101 11001 25 26 11010 10111 11010 26 27 11011 10110 11011 27 28 11100 10010 11100 28 29 11101 10011 11101 29 30 11110 10001 11110 30 31 11111 10000 11111 31
Groovy
Solution:
def grayEncode = { i ->
i ^ (i >>> 1)
}
def grayDecode;
grayDecode = { int code ->
if(code <= 0) return 0
def h = grayDecode(code >>> 1)
return (h << 1) + ((code ^ h) & 1)
}
Test:
def binary = { i, minBits = 1 ->
def remainder = i
def bin = []
while (remainder > 0 || bin.size() <= minBits) {
bin << (remainder & 1)
remainder >>>= 1
}
bin
}
println "number binary gray code decode"
println "====== ====== ========= ======"
(0..31).each {
def code = grayEncode(it)
def decode = grayDecode(code)
def iB = binary(it, 5)
def cB = binary(code, 5)
printf(" %2d %1d%1d%1d%1d%1d %1d%1d%1d%1d%1d %2d",
it, iB[4],iB[3],iB[2],iB[1],iB[0], cB[4],cB[3],cB[2],cB[1],cB[0], decode)
println()
}
Results:
number binary gray code decode
====== ====== ========= ======
0 00000 00000 0
1 00001 00001 1
2 00010 00011 2
3 00011 00010 3
4 00100 00110 4
5 00101 00111 5
6 00110 00101 6
7 00111 00100 7
8 01000 01100 8
9 01001 01101 9
10 01010 01111 10
11 01011 01110 11
12 01100 01010 12
13 01101 01011 13
14 01110 01001 14
15 01111 01000 15
16 10000 11000 16
17 10001 11001 17
18 10010 11011 18
19 10011 11010 19
20 10100 11110 20
21 10101 11111 21
22 10110 11101 22
23 10111 11100 23
24 11000 10100 24
25 11001 10101 25
26 11010 10111 26
27 11011 10110 27
28 11100 10010 28
29 11101 10011 29
30 11110 10001 30
31 11111 10000 31
Haskell
For zero padding, replace the %5s specifiers in the format string with %05s.
import Data.Bits
import Data.Char
import Numeric
import Control.Monad
import Text.Printf
grayToBin :: (Integral t, Bits t) => t -> t
grayToBin 0 = 0
grayToBin g = g `xor` (grayToBin $ g `shiftR` 1)
binToGray :: (Integral t, Bits t) => t -> t
binToGray b = b `xor` (b `shiftR` 1)
showBinary :: (Integral t, Show t) => t -> String
showBinary n = showIntAtBase 2 intToDigit n ""
showGrayCode :: (Integral t, Bits t, PrintfArg t, Show t) => t -> IO ()
showGrayCode num = do
let bin = showBinary num
let gray = showBinary (binToGray num)
printf "int: %2d -> bin: %5s -> gray: %5s\n" num bin gray
main = forM_ [0..31::Int] showGrayCode
Icon and Unicon
The following works in both languages:
link bitint
procedure main()
every write(right(i := 0 to 10,4),":",right(int2bit(i),10)," -> ",
right(g := gEncode(i),10)," -> ",
right(b := gDecode(g),10)," -> ",
right(bit2int(b),10))
end
procedure gEncode(b)
return int2bit(ixor(b, ishift(b,-1)))
end
procedure gDecode(g)
b := g[1]
every i := 2 to *g do b ||:= if g[i] == b[i-1] then "0" else "1"
return b
end
Sample run:
->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 ->
J
G2B is an invertible function which will translate Gray code to Binary:
G2B=: ~:/\&.|:
Thus G2B inv will translate binary to Gray code.
Required example:
n=:i.32
G2B=: ~:/\&.|:
(,: ,.@".&.>) 'n';'#:n';'G2B inv#:n';'#.G2B G2B inv#:n'
+--+---------+----------+----------------+
|n |#:n |G2B inv#:n|#.G2B G2B inv#:n|
+--+---------+----------+----------------+
| 0|0 0 0 0 0|0 0 0 0 0 | 0 |
| 1|0 0 0 0 1|0 0 0 0 1 | 1 |
| 2|0 0 0 1 0|0 0 0 1 1 | 2 |
| 3|0 0 0 1 1|0 0 0 1 0 | 3 |
| 4|0 0 1 0 0|0 0 1 1 0 | 4 |
| 5|0 0 1 0 1|0 0 1 1 1 | 5 |
| 6|0 0 1 1 0|0 0 1 0 1 | 6 |
| 7|0 0 1 1 1|0 0 1 0 0 | 7 |
| 8|0 1 0 0 0|0 1 1 0 0 | 8 |
| 9|0 1 0 0 1|0 1 1 0 1 | 9 |
|10|0 1 0 1 0|0 1 1 1 1 |10 |
|11|0 1 0 1 1|0 1 1 1 0 |11 |
|12|0 1 1 0 0|0 1 0 1 0 |12 |
|13|0 1 1 0 1|0 1 0 1 1 |13 |
|14|0 1 1 1 0|0 1 0 0 1 |14 |
|15|0 1 1 1 1|0 1 0 0 0 |15 |
|16|1 0 0 0 0|1 1 0 0 0 |16 |
|17|1 0 0 0 1|1 1 0 0 1 |17 |
|18|1 0 0 1 0|1 1 0 1 1 |18 |
|19|1 0 0 1 1|1 1 0 1 0 |19 |
|20|1 0 1 0 0|1 1 1 1 0 |20 |
|21|1 0 1 0 1|1 1 1 1 1 |21 |
|22|1 0 1 1 0|1 1 1 0 1 |22 |
|23|1 0 1 1 1|1 1 1 0 0 |23 |
|24|1 1 0 0 0|1 0 1 0 0 |24 |
|25|1 1 0 0 1|1 0 1 0 1 |25 |
|26|1 1 0 1 0|1 0 1 1 1 |26 |
|27|1 1 0 1 1|1 0 1 1 0 |27 |
|28|1 1 1 0 0|1 0 0 1 0 |28 |
|29|1 1 1 0 1|1 0 0 1 1 |29 |
|30|1 1 1 1 0|1 0 0 0 1 |30 |
|31|1 1 1 1 1|1 0 0 0 0 |31 |
+--+---------+----------+----------------+
Java
import java.math.BigInteger;
public class GrayCode {
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 BigInteger grayEncode(BigInteger n) {
return n.xor(n.shiftRight(1));
}
public static BigInteger grayDecode(BigInteger n) {
BigInteger p = n;
while ( ( n = n.shiftRight(1) ).signum() != 0 ) {
p = p.xor(n);
}
return p;
}
/**
* An alternative version of grayDecode,
* less efficient, but demonstrates the principal of gray decoding.
*/
public static BigInteger grayDecode2(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 using characters
result += nBits.charAt(i) != result.charAt(i - 1) ? "1" : "0";
}
return new BigInteger(result, 2);
}
/**
* An alternative version of grayEncode,
* less efficient, but demonstrates the principal of gray encoding.
*/
public static long grayEncode2(long n) {
long result = 0;
for ( int exp = 0; n > 0; n >>= 1, exp++ ) {
long nextHighestBit = ( n >> 1 ) & 1;
if ( nextHighestBit == 1 ) {
result += ( ( n & 1 ) == 0 ) ? ( 1 << exp ) : 0; // flip this bit
} else {
result += ( n & 1 ) * ( 1 << exp ); // don't flip this bit
}
}
return result;
}
public static void main(String[] args){
System.out.println("i\tBinary\tGray\tGray2\tDecoded");
System.out.println("=======================================");
for ( int i = 0; i < 32; i++ ) {
System.out.print(i + "\t");
System.out.print(Integer.toBinaryString(i) + "\t");
System.out.print(Long.toBinaryString(grayEncode(i)) + "\t");
System.out.print(Long.toBinaryString(grayEncode2(i)) + "\t");
System.out.println(grayDecode(grayEncode(i)));
}
System.out.println();
final BigInteger base = BigInteger.TEN.pow(25).add( new BigInteger("12345678901234567890") );
for ( int i = 0; i < 5; i++ ) {
BigInteger test = base.add(BigInteger.valueOf(i));
System.out.println("test decimal = " + test);
System.out.println("gray code decimal = " + grayEncode(test));
System.out.println("gray code binary = " + grayEncode(test).toString(2));
System.out.println("decoded decimal = " + grayDecode(grayEncode(test)));
System.out.println("decoded2 decimal = " + grayDecode2(grayEncode(test)));
System.out.println();
}
}
}
- Output:
i Binary Gray Gray2 Decoded ======================================= 0 0 0 0 0 1 1 1 1 1 2 10 11 11 2 3 11 10 10 3 4 100 110 110 4 5 101 111 111 5 6 110 101 101 6 7 111 100 100 7 8 1000 1100 1100 8 9 1001 1101 1101 9 10 1010 1111 1111 10 11 1011 1110 1110 11 12 1100 1010 1010 12 13 1101 1011 1011 13 14 1110 1001 1001 14 15 1111 1000 1000 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 test decimal = 10000012345678901234567890 gray code decimal = 14995268463904422838177723 gray code binary = 110001100111010111110010000111011100111111111011111110101111100100001000111110111011 decoded decimal = 10000012345678901234567890 decoded2 decimal = 10000012345678901234567890 test decimal = 10000012345678901234567891 gray code decimal = 14995268463904422838177722 gray code binary = 110001100111010111110010000111011100111111111011111110101111100100001000111110111010 decoded decimal = 10000012345678901234567891 decoded2 decimal = 10000012345678901234567891 test decimal = 10000012345678901234567892 gray code decimal = 14995268463904422838177726 gray code binary = 110001100111010111110010000111011100111111111011111110101111100100001000111110111110 decoded decimal = 10000012345678901234567892 decoded2 decimal = 10000012345678901234567892 test decimal = 10000012345678901234567893 gray code decimal = 14995268463904422838177727 gray code binary = 110001100111010111110010000111011100111111111011111110101111100100001000111110111111 decoded decimal = 10000012345678901234567893 decoded2 decimal = 10000012345678901234567893 test decimal = 10000012345678901234567894 gray code decimal = 14995268463904422838177725 gray code binary = 110001100111010111110010000111011100111111111011111110101111100100001000111110111101 decoded decimal = 10000012345678901234567894 decoded2 decimal = 10000012345678901234567894
JavaScript
The following code is ES2015.
Module gray-code.js
export function encode (number) {
return number ^ (number >> 1)
}
export function decode (encodedNumber) {
let number = encodedNumber
while (encodedNumber >>= 1) {
number ^= encodedNumber
}
return number
}
Test
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
))
}
- Output:
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
jq
Works with gojq, the Go implementation of jq
Works with jaq, the Rust implementation of jq
The following is slightly more verbose than it need be but for the sake of jaq.
def encode:
def flip: if . == 1 then 0 else 1 end;
. as $b
| reduce range(1; length) as $i ($b;
if $b[$i-1] == 1 then .[$i] |= flip
else .
end ) ;
def decode:
def xor($a;$b): ($a + $b) % 2;
. as $g
| reduce range(1; length) as $i (.[:1];
.[$i] = xor($g[$i]; .[$i-1]) ) ;
# input: a non-negative integer
# output: a binary array, least-significant bit first
def to_binary:
if . == 0 then [0]
else [recurse( if . == 0 then empty else ./2 | floor end ) % 2]
| .[:-1] # remove the uninteresting 0
end ;
def lpad($len; $fill):
tostring
| ($len - length) as $l
| if $l <= 0 then .
else ($fill * $l)[:$l] + .
end;
def pp: map(tostring) | join("") | lpad(5; "0");
### The task
"decimal binary gray roundtrip",
(range(0; 32) as $i
| ($i | to_binary | reverse) as $b
| ($b|encode) as $g
| " \($i|lpad(2;" ")) \($b|pp) \($g|pp) \($g|decode == $b)" )- Output:
decimal binary gray roundtrip 0 00000 00000 true 1 00001 00001 true 2 00010 00011 true 3 00011 00010 true 4 00100 00110 true 5 00101 00111 true 6 00110 00101 true 7 00111 00100 true 8 01000 01100 true 9 01001 01101 true 10 01010 01111 true 11 01011 01110 true 12 01100 01010 true 13 01101 01011 true 14 01110 01001 true 15 01111 01000 true 16 10000 11000 true 17 10001 11001 true 18 10010 11011 true 19 10011 11010 true 20 10100 11110 true 21 10101 11111 true 22 10110 11101 true 23 10111 11100 true 24 11000 10100 true 25 11001 10101 true 26 11010 10111 true 27 11011 10110 true 28 11100 10010 true 29 11101 10011 true 30 11110 10001 true 31 11111 10000 true
Julia
grayencode(n::Integer) = n ⊻ (n >> 1)
function graydecode(n::Integer)
r = n
while (n >>= 1) != 0
r ⊻= n
end
return r
end
Note that these functions work for any integer type, including arbitrary-precision integers (the built-in BigInt type).
K
Binary to Gray code
xor: {~x=y}
gray:{x[0],xor':x}
/ variant: using shift
gray1:{(x[0],xor[1_ x;-1_ x])}
/ variant: iterative
gray2:{x[0],{:[x[y-1]=1;~x[y];x[y]]}[x]'1+!(#x)-1}
Gray code to binary
"Accumulated xor"
g2b:xor\
An alternative is to find the inverse of the gray code by tracing until fixpoint. Here we find that 1 1 1 1 1 is the inverse of 1 0 0 0 0
gray\1 0 0 0 0
(1 0 0 0 0
1 1 0 0 0
1 0 1 0 0
1 1 1 1 0
1 0 0 0 1
1 1 0 0 1
1 0 1 0 1
1 1 1 1 1)
As a function (*| takes the last result)
g2b1:*|{gray x}\
Iterative version with "do"
g2b2:{c:#x;b:c#0;b[0]:x[0];i:1;do[#x;b[i]:xor[x[i];b[i-1]];i+:1];b}
Presentation
gray:{x[0],xor':x}
g2b:xor\
/ using allcomb instead of 2_vs'!32 for nicer presentation
allcomb:{+(x#y)_vs!_ y^x}
a:(+allcomb . 5 2)
`0:,/{n:2_sv x;gg:gray x;gb:g2b gg;n2:2_sv gb;
,/$((2$n)," : ",$x," -> ",$gg," -> ",$gb," : ",(2$n2),"\n") }'a
- Output:
0 : 00000 -> 00000 -> 00000 : 0 1 : 00001 -> 00001 -> 00001 : 1 2 : 00010 -> 00011 -> 00010 : 2 3 : 00011 -> 00010 -> 00011 : 3 4 : 00100 -> 00110 -> 00100 : 4 5 : 00101 -> 00111 -> 00101 : 5 6 : 00110 -> 00101 -> 00110 : 6 7 : 00111 -> 00100 -> 00111 : 7 8 : 01000 -> 01100 -> 01000 : 8 9 : 01001 -> 01101 -> 01001 : 9 10 : 01010 -> 01111 -> 01010 : 10 11 : 01011 -> 01110 -> 01011 : 11 12 : 01100 -> 01010 -> 01100 : 12 13 : 01101 -> 01011 -> 01101 : 13 14 : 01110 -> 01001 -> 01110 : 14 15 : 01111 -> 01000 -> 01111 : 15 16 : 10000 -> 11000 -> 10000 : 16 17 : 10001 -> 11001 -> 10001 : 17 18 : 10010 -> 11011 -> 10010 : 18 19 : 10011 -> 11010 -> 10011 : 19 20 : 10100 -> 11110 -> 10100 : 20 21 : 10101 -> 11111 -> 10101 : 21 22 : 10110 -> 11101 -> 10110 : 22 23 : 10111 -> 11100 -> 10111 : 23 24 : 11000 -> 10100 -> 11000 : 24 25 : 11001 -> 10101 -> 11001 : 25 26 : 11010 -> 10111 -> 11010 : 26 27 : 11011 -> 10110 -> 11011 : 27 28 : 11100 -> 10010 -> 11100 : 28 29 : 11101 -> 10011 -> 11101 : 29 30 : 11110 -> 10001 -> 11110 : 30 31 : 11111 -> 10000 -> 11111 : 31
Kotlin
// 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)}")
}
}
- Output:
Number Binary Gray Decoded 0 0 0 0 1 1 1 1 2 10 11 2 3 11 10 3 4 100 110 4 5 101 111 5 6 110 101 6 7 111 100 7 8 1000 1100 8 9 1001 1101 9 10 1010 1111 10 11 1011 1110 11 12 1100 1010 12 13 1101 1011 13 14 1110 1001 14 15 1111 1000 15 16 10000 11000 16 17 10001 11001 17 18 10010 11011 18 19 10011 11010 19 20 10100 11110 20 21 10101 11111 21 22 10110 11101 22 23 10111 11100 23 24 11000 10100 24 25 11001 10101 25 26 11010 10111 26 27 11011 10110 27 28 11100 10010 28 29 11101 10011 29 30 11110 10001 30 31 11111 10000 31
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;
}
- Output:
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
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
for(32) i:
let g = grey_encode(i)
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))- Output:
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
Logo
to gray_encode :number
output bitxor :number lshift :number -1
end
to gray_decode :code
local "value
make "value 0
while [:code > 0] [
make "value bitxor :code :value
make "code lshift :code -1
]
output :value
endDemonstration code, including formatters:
to format :str :width [pad (char 32)]
while [(count :str) < :width] [
make "str word :pad :str
]
output :str
end
; Output binary representation of a number
to binary :number [:width 1]
local "bits
ifelse [:number = 0] [
make "bits 0
] [
make "bits "
while [:number > 0] [
make "bits word (bitand :number 1) :bits
make "number lshift :number -1
]
]
output (format :bits :width 0)
end
repeat 32 [
make "num repcount - 1
make "gray gray_encode :num
make "decoded gray_decode :gray
print (sentence (format :num 2) ": (binary :num 5) ": (binary :gray 5) ":
(binary :decoded 5) ": (format :decoded 2)) ]
bye- Output:
0 : 00000 : 00000 : 00000 : 0 1 : 00001 : 00001 : 00001 : 1 2 : 00010 : 00011 : 00010 : 2 3 : 00011 : 00010 : 00011 : 3 4 : 00100 : 00110 : 00100 : 4 5 : 00101 : 00111 : 00101 : 5 6 : 00110 : 00101 : 00110 : 6 7 : 00111 : 00100 : 00111 : 7 8 : 01000 : 01100 : 01000 : 8 9 : 01001 : 01101 : 01001 : 9 10 : 01010 : 01111 : 01010 : 10 11 : 01011 : 01110 : 01011 : 11 12 : 01100 : 01010 : 01100 : 12 13 : 01101 : 01011 : 01101 : 13 14 : 01110 : 01001 : 01110 : 14 15 : 01111 : 01000 : 01111 : 15 16 : 10000 : 11000 : 10000 : 16 17 : 10001 : 11001 : 10001 : 17 18 : 10010 : 11011 : 10010 : 18 19 : 10011 : 11010 : 10011 : 19 20 : 10100 : 11110 : 10100 : 20 21 : 10101 : 11111 : 10101 : 21 22 : 10110 : 11101 : 10110 : 22 23 : 10111 : 11100 : 10111 : 23 24 : 11000 : 10100 : 11000 : 24 25 : 11001 : 10101 : 11001 : 25 26 : 11010 : 10111 : 11010 : 26 27 : 11011 : 10110 : 11011 : 27 28 : 11100 : 10010 : 11100 : 28 29 : 11101 : 10011 : 11101 : 29 30 : 11110 : 10001 : 11110 : 30 31 : 11111 : 10000 : 11111 : 31
Lua
This code uses the Lua BitOp module. Designed to be a module named gray.lua.
local _M = {}
local bit = require('bit')
local math = require('math')
_M.encode = function(number)
return bit.bxor(number, bit.rshift(number, 1));
end
_M.decode = function(gray_code)
local value = 0
while gray_code > 0 do
gray_code, value = bit.rshift(gray_code, 1), bit.bxor(gray_code, value)
end
return value
end
return _M
Demonstration code:
local bit = require 'bit'
local gray = require 'gray'
-- simple binary string formatter
local function to_bit_string(n, width)
width = width or 1
local output = ""
while n > 0 do
output = bit.band(n,1) .. output
n = bit.rshift(n,1)
end
while #output < width do
output = '0' .. output
end
return output
end
for i = 0,31 do
g = gray.encode(i);
gd = gray.decode(g);
print(string.format("%2d : %s => %s => %s : %2d", i,
to_bit_string(i,5), to_bit_string(g, 5),
to_bit_string(gd,5), gd))
end
- Output:
0 : 00000 => 00000 => 00000 : 0 1 : 00001 => 00001 => 00001 : 1 2 : 00010 => 00011 => 00010 : 2 3 : 00011 => 00010 => 00011 : 3 4 : 00100 => 00110 => 00100 : 4 5 : 00101 => 00111 => 00101 : 5 6 : 00110 => 00101 => 00110 : 6 7 : 00111 => 00100 => 00111 : 7 8 : 01000 => 01100 => 01000 : 8 9 : 01001 => 01101 => 01001 : 9 10 : 01010 => 01111 => 01010 : 10 11 : 01011 => 01110 => 01011 : 11 12 : 01100 => 01010 => 01100 : 12 13 : 01101 => 01011 => 01101 : 13 14 : 01110 => 01001 => 01110 : 14 15 : 01111 => 01000 => 01111 : 15 16 : 10000 => 11000 => 10000 : 16 17 : 10001 => 11001 => 10001 : 17 18 : 10010 => 11011 => 10010 : 18 19 : 10011 => 11010 => 10011 : 19 20 : 10100 => 11110 => 10100 : 20 21 : 10101 => 11111 => 10101 : 21 22 : 10110 => 11101 => 10110 : 22 23 : 10111 => 11100 => 10111 : 23 24 : 11000 => 10100 => 11000 : 24 25 : 11001 => 10101 => 11001 : 25 26 : 11010 => 10111 => 11010 : 26 27 : 11011 => 10110 => 11011 : 27 28 : 11100 => 10010 => 11100 : 28 29 : 11101 => 10011 => 11101 : 29 30 : 11110 => 10001 => 11110 : 30 31 : 11111 => 10000 => 11111 : 31
M2000 Interpreter
Additions to showing the modules/functions replacement mechanism of M2000
Module Code32 (&code(), &decode()){
Const d$="{0::-2} {1:-6} {2:-6} {3:-6} {4::-2}"
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- Output:
0 0 0 0 0 1 1 1 1 1 2 10 11 10 2 3 11 10 11 3 4 100 110 100 4 5 101 111 101 5 6 110 101 110 6 7 111 100 111 7 8 1000 1100 1000 8 9 1001 1101 1001 9 10 1010 1111 1010 10 11 1011 1110 1011 11 12 1100 1010 1100 12 13 1101 1011 1101 13 14 1110 1001 1110 14 15 1111 1000 1111 15 16 10000 11000 10000 16 17 10001 11001 10001 17 18 10010 11011 10010 18 19 10011 11010 10011 19 20 10100 11110 10100 20 21 10101 11111 10101 21 22 10110 11101 10110 22 23 10111 11100 10111 23 24 11000 10100 11000 24 25 11001 10101 11001 25 26 11010 10111 11010 26 27 11011 10110 11011 27 28 11100 10010 11100 28 29 11101 10011 11101 29 30 11110 10001 11110 30 31 11111 10000 11111 31 32 100000 110000 100000 32
Mathematica / Wolfram Language
graycode[n_]:=BitXor[n,BitShiftRight[n]]
graydecode[n_]:=Fold[BitXor,0,FixedPointList[BitShiftRight,n]]
- Output:
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}
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
- Output:
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
Mercury
The following is a full implementation of Gray encoding and decoding. It publicly exposes the gray type along with the following value conversion functions:
- gray.from_int/1
- gray.to_int/1
The from_int/1 and to_int/1 functions are value conversion functions. from_int/1 converts an int value into the enclosing gray type. to_int/1 converts a gray value back into a regular int type.
The additional gray.coerce/2 predicate converts the representation underlying a gray value into an int value or vice versa (it is moded in both directions). For type safety reasons we do not wish to generally expose the underlying representation, but for some purposes, most notably I/O or storage or their ilk we have to break the type safety. The coerce/2 predicate is used for this purpose.
:- module gray.
:- interface.
:- import_module int.
:- type gray.
% VALUE conversion functions
:- func gray.from_int(int) = gray.
:- func gray.to_int(gray) = int.
% REPRESENTATION conversion predicate
:- pred gray.coerce(gray, int).
:- mode gray.coerce(in, out) is det.
:- mode gray.coerce(out, in) is det.
:- implementation.
:- import_module list.
:- type gray
---> gray(int).
gray.from_int(X) = gray(X `xor` (X >> 1)).
gray.to_int(gray(G)) = (G > 0 -> G `xor` gray.to_int(gray(G >> 1))
; G).
gray.coerce(gray(I), I).
:- end_module gray.The following program tests the above code:
:- module gray_test.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module gray.
:- import_module int, list, string.
:- pred check_conversion(list(int)::in, list(gray)::out) is semidet.
:- pred display_lists(list(int)::in, list(gray)::in, io::di, io::uo) is det.
:- pred display_record(int::in, gray::in, io::di, io::uo) is det.
main(!IO) :-
Numbers = 0..31,
( check_conversion(Numbers, Grays) ->
io.format("%8s %8s %8s\n", [s("Number"), s("Binary"), s("Gray")], !IO),
io.format("%8s %8s %8s\n", [s("------"), s("------"), s("----")], !IO),
display_lists(Numbers, Grays, !IO)
; io.write("Either conversion or back-conversion failed.\n", !IO)).
check_conversion(Numbers, Grays) :-
Grays = list.map(gray.from_int, Numbers),
Numbers = list.map(gray.to_int, Grays).
display_lists(Numbers, Grays, !IO) :-
list.foldl_corresponding(display_record, Numbers, Grays, !IO).
display_record(Number, Gray, !IO) :-
gray.coerce(Gray, GrayRep),
NumBin = string.int_to_base_string(Number, 2),
GrayBin = string.int_to_base_string(GrayRep, 2),
io.format("%8d %8s %8s\n", [i(Number), s(NumBin), s(GrayBin)], !IO).
:- end_module gray_test.The main/2 predicate generates a list of numbers from 0 to 31 inclusive and then checks that conversion is working properly. It does so by calling the check_conversion/2 predicate with the list of numbers as an input and the list of Gray-encoded numbers as an output. Note the absence of the usual kinds of testing you'd see in most programming languages. gray.from_int/1 is mapped over the Numbers (input) list and placed into the Grays (output) list. Then gray.to_int is mapped over the Grays list and placed into the Numbers (input) list. Or so it would seem to those used to imperative or functional languages.
In reality what's happening is unification. Since the Grays list is not yet populated, unification is very similar notionally to assignment in other languages. Numbers, however, is instantiated and thus unification is more like testing for equality.
If the conversions check out, main/2 prints off some headers and then displays the lists. Here we're cluttering up the namespace of the gray_test module a little by providing a one-line predicate. While it is true that we could just take the contents of that predicate and place it inline, we've chosen not to do that because the name display_lists communicates more effectively what we intend. The compiler is smart enough to automatically inline that predicate call so there's no efficiency reason not to do it.
However we choose to do that, the result is the same: repeated calls to display_record/4. In that predicate the aforementioned coerce/2 predicate extracts, in this case, the Gray value's representation. This value and the corresponding int value are then converted into a string showing the base-2 representation of their values. io.format/4 then prints them off in a nice format.
The output of the program looks like this:
Number Binary Gray
------ ------ ----
0 0 0
1 1 1
2 10 11
3 11 10
4 100 110
5 101 111
6 110 101
7 111 100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
16 10000 11000
17 10001 11001
18 10010 11011
19 10011 11010
20 10100 11110
21 10101 11111
22 10110 11101
23 10111 11100
24 11000 10100
25 11001 10101
26 11010 10111
27 11011 10110
28 11100 10010
29 11101 10011
30 11110 10001
31 11111 10000
Modula-2
MODULE GrayCode;
FROM STextIO IMPORT
WriteString, WriteLn;
FROM SWholeIO IMPORT
WriteInt;
FROM Conversions IMPORT
LongBaseToStr;
FROM FormatString IMPORT
FormatString; (* for justifying *)
VAR
I, G, D: CARDINAL;
Ok: BOOLEAN;
BinS, OutBinS: ARRAY[0 .. 5] OF CHAR;
PROCEDURE Encode(V: CARDINAL): CARDINAL;
BEGIN
RETURN V BXOR (V SHR 1)
END Encode;
PROCEDURE Decode(V: CARDINAL): CARDINAL;
VAR
Result: CARDINAL;
BEGIN
Result := 0;
WHILE V > 0 DO
Result := Result BXOR V;
V := V SHR 1
END;
RETURN Result
END Decode;
BEGIN
WriteString("decimal binary gray decoded");
WriteLn;
FOR I := 0 TO 31 DO
G := Encode(I);
D := Decode(G);
WriteInt(I, 4);
WriteString(" ");
Ok := LongBaseToStr(I, 2, BinS);
Ok := FormatString("%'05s", OutBinS, BinS);
(* Padded with 0; width: 5; type: string *)
WriteString(OutBinS);
WriteString(" ");
Ok := LongBaseToStr(G, 2, BinS);
Ok := FormatString("%'05s", OutBinS, BinS);
WriteString(OutBinS);
WriteString(" ");
Ok := LongBaseToStr(D, 2, BinS);
Ok := FormatString("%'05s", OutBinS, BinS);
WriteString(OutBinS);
WriteInt(D, 4);
WriteLn;
END
END GrayCode.
- Output:
decimal binary gray decoded 0 00000 00000 00000 0 1 00001 00001 00001 1 2 00010 00011 00010 2 3 00011 00010 00011 3 4 00100 00110 00100 4 5 00101 00111 00101 5 6 00110 00101 00110 6 7 00111 00100 00111 7 8 01000 01100 01000 8 9 01001 01101 01001 9 10 01010 01111 01010 10 11 01011 01110 01011 11 12 01100 01010 01100 12 13 01101 01011 01101 13 14 01110 01001 01110 14 15 01111 01000 01111 15 16 10000 11000 10000 16 17 10001 11001 10001 17 18 10010 11011 10010 18 19 10011 11010 10011 19 20 10100 11110 10100 20 21 10101 11111 10101 21 22 10110 11101 10110 22 23 10111 11100 10111 23 24 11000 10100 11000 24 25 11001 10101 11001 25 26 11010 10111 11010 26 27 11011 10110 11011 27 28 11100 10010 11100 28 29 11101 10011 11101 29 30 11110 10001 11110 30 31 11111 10000 11111 31
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
Demonstration code:
import strutils, strformat
for i in 0 .. 32:
echo &"{i:>2} => {toBin(grayEncode(i), 6)} => {grayDecode(grayEncode(i)):>2}"
- Output:
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
NOWUT
adapted from C
; link with PIOxxx.OBJ
sectiondata
output: db " : "
inbinary: db "00000 => "
graybinary: db "00000 => "
outbinary: db "00000"
db 13,10,0 ; carriage return and null terminator
sectioncode
start!
gosub initplatform
beginfunc
localvar i.d,g.d,b.d
i=0
whileless i,32
callex g,gray_encode,i
callex b,gray_decode,g
callex ,bin2string,i,inbinary,5 ; 5 = number of binary digits
callex ,bin2string,g,graybinary,5
callex ,bin2string,b,outbinary,5
callex ,printhex8,i ; display hex value
; because there is no PIO routine for decimals...
callex ,printnt,output.a
i=_+1
wend
endfunc
end
gray_encode:
beginfunc n.d
n=_ xor (n shr 1)
endfunc n
returnex 4 ; clean off 1 parameter from the stack
gray_decode:
beginfunc n.d
localvar p.d
p=n
whilegreater n,1
n=_ shr 1 > p=_ xor n
wend
endfunc p
returnex 4 ; clean off 1 parameter from the stack
bin2string:
beginfunc digits.d,straddr.d,value.d
whilegreater digits,0
digits=_-1
[straddr].b=value shr digits and 1+$30 ; write an ASCII '0' or '1'
straddr=_+1 ; increment the pointer
wend
endfunc
returnex $0C ; clean off 3 parameters from the stack- Output:
00 : 00000 => 00000 => 00000 01 : 00001 => 00001 => 00001 02 : 00010 => 00011 => 00010 03 : 00011 => 00010 => 00011 04 : 00100 => 00110 => 00100 05 : 00101 => 00111 => 00101 06 : 00110 => 00101 => 00110 07 : 00111 => 00100 => 00111 08 : 01000 => 01100 => 01000 09 : 01001 => 01101 => 01001 0A : 01010 => 01111 => 01010 0B : 01011 => 01110 => 01011 0C : 01100 => 01010 => 01100 0D : 01101 => 01011 => 01101 0E : 01110 => 01001 => 01110 0F : 01111 => 01000 => 01111 10 : 10000 => 11000 => 10000 11 : 10001 => 11001 => 10001 12 : 10010 => 11011 => 10010 13 : 10011 => 11010 => 10011 14 : 10100 => 11110 => 10100 15 : 10101 => 11111 => 10101 16 : 10110 => 11101 => 10110 17 : 10111 => 11100 => 10111 18 : 11000 => 10100 => 11000 19 : 11001 => 10101 => 11001 1A : 11010 => 10111 => 11010 1B : 11011 => 10110 => 11011 1C : 11100 => 10010 => 11100 1D : 11101 => 10011 => 11101 1E : 11110 => 10001 => 11110 1F : 11111 => 10000 => 11111
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 = Bytes.make len '0' in
let rec aux i n =
if n land 1 = 1 then Bytes.set s i '1';
if i <= 0 then (Bytes.to_string 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
PARI/GP
This code may have exposed a bug in PARI 2.4.4: apply(Str, 1) fails.
As a workaround I used a closure: apply(k->Str(k), 1).
toGray(n)=bitxor(n,n>>1);
fromGray(n)=my(k=1,m=n);while(m>>k,n=bitxor(n,n>>k);k+=k);n;
bin(n)=concat(apply(k->Str(k),binary(n)))
for(n=0,31,print(n"\t"bin(n)"\t"bin(g=toGray(n))"\t"fromGray(g)))- Output:
0 0 0 0 1 1 1 1 2 10 11 2 3 11 10 3 4 100 110 4 5 101 111 5 6 110 101 6 7 111 100 7 8 1000 1100 8 9 1001 1101 9 10 1010 1111 10 11 1011 1110 11 12 1100 1010 12 13 1101 1011 13 14 1110 1001 14 15 1111 1000 15 16 10000 11000 16 17 10001 11001 17 18 10010 11011 18 19 10011 11010 19 20 10100 11110 20 21 10101 11111 21 22 10110 11101 22 23 10111 11100 23 24 11000 10100 24 25 11001 10101 25 26 11010 10111 26 27 11011 10110 27 28 11100 10010 28 29 11101 10011 29 30 11110 10001 30 31 11111 10000 31
Pascal
See Delphi
PascalABC.NET
uses School;
function GrayEncode(n: longword): longword := n xor (n shr 1);
function GrayDecode(n: longword): longword;
begin
Result := 0;
while n > 0 do
begin
Result := Result xor n;
n := n shr 1;
end;
end;
begin
for var i := 0 to 31 do
Writeln($'{i,-7} {Bin(i),-7} {Bin(grayEncode(i)),-7} {grayDecode(grayEncode(i)),-7}');
end.
- Output:
0 0 0 0 1 1 1 1 2 10 11 2 3 11 10 3 4 100 110 4 5 101 111 5 6 110 101 6 7 111 100 7 8 1000 1100 8 9 1001 1101 9 10 1010 1111 10 11 1011 1110 11 12 1100 1010 12 13 1101 1011 13 14 1110 1001 14 15 1111 1000 15 16 10000 11000 16 17 10001 11001 17 18 10010 11011 18 19 10011 11010 19 20 10100 11110 20 21 10101 11111 21 22 10110 11101 22 23 10111 11100 23 24 11000 10100 24 25 11001 10101 25 26 11010 10111 26 27 11011 10110 27 28 11100 10010 28 29 11101 10011 29 30 11110 10001 30 31 11111 10000 31
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);
}
Phix
(turned out to be almost the same as Euphoria)
with javascript_semantics 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
- Output:
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
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));
}
- Output:
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
Picat
go =>
foreach(I in 0..2**5-1)
G = gray_encode1(I),
E = gray_decode1(G),
printf("%2d %6w %2d %6w %6w %2d\n",I,I.to_binary_string,
G, G.to_binary_string,
E.to_binary_string, E)
end,
nl,
println("Checking 2**1300:"),
N2=2**1300,
G2=gray_encode1(N2),
E2=gray_decode1(G2),
% println(g2=G2),
% println(e2=E2),
println(check=cond(N2==E2,same,not_same)),
nl.
gray_encode1(N) = N ^ (N >> 1).
gray_decode1(N) = P =>
P = N,
N := N >> 1,
while (N != 0)
P := P ^ N,
N := N >> 1
end.- Output:
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 Checking 2**1300 check = same
PicoLisp
(de grayEncode (N)
(bin (x| N (>> 1 N))) )
(de grayDecode (G)
(bin
(pack
(let X 0
(mapcar
'((C) (setq X (x| X (format C))))
(chop G) ) ) ) ) )Test:
(prinl " Binary Gray Decoded")
(for I (range 0 31)
(let G (grayEncode I)
(tab (4 9 9 9) I (bin I) G (grayDecode G)) ) )- Output:
Binary Gray Decoded 0 0 0 0 1 1 1 1 2 10 11 2 3 11 10 3 4 100 110 4 5 101 111 5 6 110 101 6 7 111 100 7 8 1000 1100 8 9 1001 1101 9 10 1010 1111 10 11 1011 1110 11 12 1100 1010 12 13 1101 1011 13 14 1110 1001 14 15 1111 1000 15 16 10000 11000 16 17 10001 11001 17 18 10010 11011 18 19 10011 11010 19 20 10100 11110 20 21 10101 11111 21 22 10110 11101 22 23 10111 11100 23 24 11000 10100 24 25 11001 10101 25 26 11010 10111 26 27 11011 10110 27 28 11100 10010 28 29 11101 10011 29 30 11110 10001 30 31 11111 10000 31
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;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
PL/M
100H:
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; GO TO 0; END EXIT;
PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT;
PRINT$NUM: PROCEDURE (N, BASE);
DECLARE S (17) BYTE INITIAL ('................$');
DECLARE (N, P) ADDRESS, (DGT BASED P, BASE) BYTE;
P = .S(16);
DIGIT:
P = P - 1;
DGT = N MOD BASE + '0';
N = N / BASE;
IF N > 0 THEN GO TO DIGIT;
CALL PRINT(P);
END PRINT$NUM;
GRAY$ENCODE: PROCEDURE (N) BYTE;
DECLARE N BYTE;
RETURN N XOR SHR(N, 1);
END GRAY$ENCODE;
GRAY$DECODE: PROCEDURE (N) BYTE;
DECLARE (N, R, I) BYTE;
R = N;
DO WHILE (N := SHR(N,1)) > 0;
R = R XOR N;
END;
RETURN R;
END GRAY$DECODE;
DECLARE (I, G) BYTE;
DO I = 0 TO 31;
CALL PRINT$NUM(I, 10);
CALL PRINT(.(':',9,'$'));
CALL PRINT$NUM(I, 2);
CALL PRINT(.(9,'=>',9,'$'));
CALL PRINT$NUM(G := GRAY$ENCODE(I), 2);
CALL PRINT(.(9,'=>',9,'$'));
CALL PRINT$NUM(GRAY$DECODE(G), 10);
CALL PRINT(.(10,13,'$'));
END;
CALL EXIT;
EOF- Output:
0: 0 => 0 => 0 1: 1 => 1 => 1 2: 10 => 11 => 2 3: 11 => 10 => 3 4: 100 => 110 => 4 5: 101 => 111 => 5 6: 110 => 101 => 6 7: 111 => 100 => 7 8: 1000 => 1100 => 8 9: 1001 => 1101 => 9 10: 1010 => 1111 => 10 11: 1011 => 1110 => 11 12: 1100 => 1010 => 12 13: 1101 => 1011 => 13 14: 1110 => 1001 => 14 15: 1111 => 1000 => 15 16: 10000 => 11000 => 16 17: 10001 => 11001 => 17 18: 10010 => 11011 => 18 19: 10011 => 11010 => 19 20: 10100 => 11110 => 20 21: 10101 => 11111 => 21 22: 10110 => 11101 => 22 23: 10111 => 11100 => 23 24: 11000 => 10100 => 24 25: 11001 => 10101 => 25 26: 11010 => 10111 => 26 27: 11011 => 10110 => 27 28: 11100 => 10010 => 28 29: 11101 => 10011 => 29 30: 11110 => 10001 => 30 31: 11111 => 10000 => 31
Prolog
Codecs
The encoding and decoding predicates are simple and will work with any Prolog that supports bitwise integer operations.
to_gray(N, G) :-
N0 is N >> 1,
G is N xor N0.
from_gray(G, N) :-
( G > 0
-> S is G >> 1,
from_gray(S, N0),
N is G xor N0
; N is G ).
Test Code
A quick driver around this to test it will prove the point. (This test script uses features not available in every Prolog implementation.)
:- 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).
- Output:
Putting all of this in a file, we execute it, getting the following results:
% swipl -q -t go -f gray.pl # OR: yap -q -z go,halt -f gray.pl Number Binary Gray Decoded Number ------ ------ ---- ------- ------ 0 0 0 0 0 1 1 1 1 1 2 10 11 10 2 3 11 10 11 3 4 100 110 100 4 5 101 111 101 5 6 110 101 110 6 7 111 100 111 7 8 1000 1100 1000 8 9 1001 1101 1001 9 10 1010 1111 1010 10 11 1011 1110 1011 11 12 1100 1010 1100 12 13 1101 1011 1101 13 14 1110 1001 1110 14 15 1111 1000 1111 15 16 10000 11000 10000 16 17 10001 11001 10001 17 18 10010 11011 10010 18 19 10011 11010 10011 19 20 10100 11110 10100 20 21 10101 11111 10101 21 22 10110 11101 10110 22 23 10111 11100 10111 23 24 11000 10100 11000 24 25 11001 10101 11001 25 26 11010 10111 11010 26 27 11011 10110 11011 27 28 11100 10010 11100 28 29 11101 10011 11101 29 30 11110 10001 11110 30 31 11111 10000 11111 31
Python
Python: on integers
Works with python integers
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}")
- Output:
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
Python: on lists of bits
This example works with lists of discrete binary digits.
- First some int<>bin conversion routines
>>> def int2bin(n):
'From positive integer to list of binary bits, msb at index 0'
if n:
bits = []
while n:
n,remainder = divmod(n, 2)
bits.insert(0, remainder)
return bits
else: return [0]
>>> def bin2int(bits):
'From binary bits, msb at index 0 to integer'
i = 0
for bit in bits:
i = i * 2 + bit
return i
- Now the bin<>gray converters.
These follow closely the methods in the animation seen here: Converting Between Gray and Binary Codes.
>>> def bin2gray(bits):
return bits[:1] + [i ^ ishift for i, ishift in zip(bits[:-1], bits[1:])]
>>> def gray2bin(bits):
b = [bits[0]]
for nextb in bits[1:]: b.append(b[-1] ^ nextb)
return b
- Sample output
>>> for i in range(16):
print('int:%2i -> bin:%12r -> gray:%12r -> bin:%12r -> int:%2i' %
( i,
int2bin(i),
bin2gray(int2bin(i)),
gray2bin(bin2gray(int2bin(i))),
bin2int(gray2bin(bin2gray(int2bin(i))))
))
int: 0 -> bin: [0] -> gray: [0] -> bin: [0] -> int: 0
int: 1 -> bin: [1] -> gray: [1] -> bin: [1] -> int: 1
int: 2 -> bin: [1, 0] -> gray: [1, 1] -> bin: [1, 0] -> int: 2
int: 3 -> bin: [1, 1] -> gray: [1, 0] -> bin: [1, 1] -> int: 3
int: 4 -> bin: [1, 0, 0] -> gray: [1, 1, 0] -> bin: [1, 0, 0] -> int: 4
int: 5 -> bin: [1, 0, 1] -> gray: [1, 1, 1] -> bin: [1, 0, 1] -> int: 5
int: 6 -> bin: [1, 1, 0] -> gray: [1, 0, 1] -> bin: [1, 1, 0] -> int: 6
int: 7 -> bin: [1, 1, 1] -> gray: [1, 0, 0] -> bin: [1, 1, 1] -> int: 7
int: 8 -> bin:[1, 0, 0, 0] -> gray:[1, 1, 0, 0] -> bin:[1, 0, 0, 0] -> int: 8
int: 9 -> bin:[1, 0, 0, 1] -> gray:[1, 1, 0, 1] -> bin:[1, 0, 0, 1] -> int: 9
int:10 -> bin:[1, 0, 1, 0] -> gray:[1, 1, 1, 1] -> bin:[1, 0, 1, 0] -> int:10
int:11 -> bin:[1, 0, 1, 1] -> gray:[1, 1, 1, 0] -> bin:[1, 0, 1, 1] -> int:11
int:12 -> bin:[1, 1, 0, 0] -> gray:[1, 0, 1, 0] -> bin:[1, 1, 0, 0] -> int:12
int:13 -> bin:[1, 1, 0, 1] -> gray:[1, 0, 1, 1] -> bin:[1, 1, 0, 1] -> int:13
int:14 -> bin:[1, 1, 1, 0] -> gray:[1, 0, 0, 1] -> bin:[1, 1, 1, 0] -> int:14
int:15 -> bin:[1, 1, 1, 1] -> gray:[1, 0, 0, 0] -> bin:[1, 1, 1, 1] -> int:15
>>>
Quackery
[ dup 1 >> ^ ] is encodegray ( n --> n )
[ dup
[ dip [ 1 >> ]
over ^
over 0 = until ]
nip ] is decodegray ( n --> n )
[ [] unrot times
[ 2 /mod char 0 +
rot join swap ]
drop echo$ ] is echobin ( n n --> )
say "number encoded decoded" cr
say "------ ------- -------" cr
32 times
[ sp i^ 5 echobin
say " -> "
i^ encodegray dup 5 echobin
say " -> "
decodegray 5 echobin cr ]- Output:
number encoded 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
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)
}
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"))))
- Output:
> (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
Raku
(formerly Perl 6)
sub gray_encode ( Int $n --> Int ) {
return $n +^ ( $n +> 1 );
}
sub gray_decode ( Int $n is copy --> Int ) {
my $mask = 1 +< (32-2);
$n +^= $mask +> 1 if $n +& $mask while $mask +>= 1;
return $n;
}
for ^32 -> $n {
my $g = gray_encode($n);
my $d = gray_decode($g);
printf "%2d: %5b => %5b => %5b: %2d\n", $n, $n, $g, $d, $d;
die if $d != $n;
}
- Output:
0: 0 => 0 => 0: 0 1: 1 => 1 => 1: 1 2: 10 => 11 => 10: 2 3: 11 => 10 => 11: 3 4: 100 => 110 => 100: 4 5: 101 => 111 => 101: 5 6: 110 => 101 => 110: 6 7: 111 => 100 => 111: 7 8: 1000 => 1100 => 1000: 8 9: 1001 => 1101 => 1001: 9 10: 1010 => 1111 => 1010: 10 11: 1011 => 1110 => 1011: 11 12: 1100 => 1010 => 1100: 12 13: 1101 => 1011 => 1101: 13 14: 1110 => 1001 => 1110: 14 15: 1111 => 1000 => 1111: 15 16: 10000 => 11000 => 10000: 16 17: 10001 => 11001 => 10001: 17 18: 10010 => 11011 => 10010: 18 19: 10011 => 11010 => 10011: 19 20: 10100 => 11110 => 10100: 20 21: 10101 => 11111 => 10101: 21 22: 10110 => 11101 => 10110: 22 23: 10111 => 11100 => 10111: 23 24: 11000 => 10100 => 11000: 24 25: 11001 => 10101 => 11001: 25 26: 11010 => 10111 => 11010: 26 27: 11011 => 10110 => 11011: 27 28: 11100 => 10010 => 11100: 28 29: 11101 => 10011 => 11101: 29 30: 11110 => 10001 => 11110: 30 31: 11111 => 10000 => 11111: 31
Raku distinguishes numeric bitwise operators with a leading + sign, so +< and +> are left and right shift, while +& is a bitwise AND, while +^ is bitwise XOR (here used as part of an assignment metaoperator).
REXX
The leading zeroes for the binary numbers and the gray code could've easily been elided.
/*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 ►─────────┘ */
output when using the default input:
───decimal────► ────binary────► ──gray code───► ────binary────
0 00000 00000 00000
1 00001 00001 00001
2 00010 00011 00010
3 00011 00010 00011
4 00100 00110 00100
5 00101 00111 00101
6 00110 00101 00110
7 00111 00100 00111
8 01000 01100 01000
9 01001 01101 01001
10 01010 01111 01010
11 01011 01110 01011
12 01100 01010 01100
13 01101 01011 01101
14 01110 01001 01110
15 01111 01000 01111
16 10000 11000 10000
17 10001 11001 10001
18 10010 11011 10010
19 10011 11010 10011
20 10100 11110 10100
21 10101 11111 10101
22 10110 11101 10110
23 10111 11100 10111
24 11000 10100 11000
25 11001 10101 11001
26 11010 10111 11010
27 11011 10110 11011
28 11100 10010 11100
29 11101 10011 11101
30 11110 10001 11110
31 11111 10000 11111
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 resultOutput:
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
RPL
| RPL code | Comment |
|---|---|
≪ #1 RR 0 ROT START RL NEXT AND #0 ≠
≫ ´BIT?´ STO
≪ # 1b 0 ROT START RR NEXT OR
≫ ‘STBIT’ STO
≪ DUP SR XOR
≫ ‘→GRAY’ STO
≪ → gray
≪ #0 IF gray 0 BIT? THEN 0 STBIT END
1 RCWS 1 - FOR b
IF gray b BIT? OVER b 1 - BIT? XOR THEN b STBIT END
NEXT
≫ ≫ ‘GRAY→’ STO
≪ { } 0 31 FOR n n R→B →GRAY + NEXT
{ } 1 3 PICK SIZE FOR g OVER g GET GRAY→ + NEXT
≫ 'SHOWG’ STO
|
( #b n -- boolean ) ( #b n -- #b ) ( #b -- #g ) ( #g -- #b ) b(0) = g(0) Loop on all other bits b[i] = g[i] xor b[i-1] |
- Input:
SHOWG
- Output:
2: { # 0b # 1b # 11b # 10b # 110b # 111b # 101b # 100b # 1100b # 1101b # 1111b # 1110b # 1010b # 1011b # 1001b # 1000b # 11000b # 11001b # 11011b # 11010b # 11110b # 11111b # 11101b # 11100b # 10100b # 10101b # 10111b # 10110b # 10010b # 10011b # 10001b # 10000b }
1: { # 0b # 1b # 10b # 11b # 100b # 101b # 110b # 111b # 1000b # 1001b # 1010b # 1011b # 1100b # 1101b # 1110b # 1111b # 10000b # 10001b # 10010b # 10011b # 10100b # 10101b # 10110b # 10111b # 11000b # 11001b # 11010b # 11011b # 11100b # 11101b # 11110b # 11111b }
Ruby
Integer#from_gray has recursion so it can use each bit of the answer to compute the next bit.
class Integer
# Converts a normal integer to a Gray code.
def to_gray
raise Math::DomainError, "integer is negative" if self < 0
self ^ (self >> 1)
end
# Converts a Gray code to a normal integer.
def from_gray
raise Math::DomainError, "integer is negative" if self < 0
recurse = proc do |i|
next 0 if i == 0
o = recurse[i >> 1] << 1
o | (i[0] ^ o[1])
end
recurse[self]
end
end
(0..31).each do |number|
encoded = number.to_gray
decoded = encoded.from_gray
printf "%2d : %5b => %5b => %5b : %2d\n",
number, number, encoded, decoded, decoded
end
- Output:
0 : 0 => 0 => 0 : 0 1 : 1 => 1 => 1 : 1 2 : 10 => 11 => 10 : 2 3 : 11 => 10 => 11 : 3 4 : 100 => 110 => 100 : 4 5 : 101 => 111 => 101 : 5 6 : 110 => 101 => 110 : 6 7 : 111 => 100 => 111 : 7 8 : 1000 => 1100 => 1000 : 8 9 : 1001 => 1101 => 1001 : 9 10 : 1010 => 1111 => 1010 : 10 11 : 1011 => 1110 => 1011 : 11 12 : 1100 => 1010 => 1100 : 12 13 : 1101 => 1011 => 1101 : 13 14 : 1110 => 1001 => 1110 : 14 15 : 1111 => 1000 => 1111 : 15 16 : 10000 => 11000 => 10000 : 16 17 : 10001 => 11001 => 10001 : 17 18 : 10010 => 11011 => 10010 : 18 19 : 10011 => 11010 => 10011 : 19 20 : 10100 => 11110 => 10100 : 20 21 : 10101 => 11111 => 10101 : 21 22 : 10110 => 11101 => 10110 : 22 23 : 10111 => 11100 => 10111 : 23 24 : 11000 => 10100 => 11000 : 24 25 : 11001 => 10101 => 11001 : 25 26 : 11010 => 10111 => 11010 : 26 27 : 11011 => 10110 => 11011 : 27 28 : 11100 => 10010 => 11100 : 28 29 : 11101 => 10011 => 11101 : 29 30 : 11110 => 10001 => 11110 : 30 31 : 11111 => 10000 => 11111 : 31
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));
}
}
Scala
Functional style: the Gray code is encoded to, and decoded from a String.
The scanLeft function takes a sequence (here, of characters) and produces a collection containing cumulative results of applying an operator going left to right.
Here the operator is exclusive-or, "^", and we can use "_" placeholders to represent the arguments to the left and right. tail removes the "0" we added as the initial accumulator value, and mkString turns the collection back into a String, that we can parse into an integer (Integer.parseInt is directly from the java.lang package).
def encode(n: Int) = (n ^ (n >>> 1)).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)))
- Output:
decimal binary gray decoded
0 0 0 0
1 1 1 1
2 10 11 2
3 11 10 3
4 100 110 4
5 101 111 5
6 110 101 6
7 111 100 7
8 1000 1100 8
9 1001 1101 9
10 1010 1111 10
11 1011 1110 11
12 1100 1010 12
13 1101 1011 13
14 1110 1001 14
15 1111 1000 15
16 10000 11000 16
17 10001 11001 17
18 10010 11011 18
19 10011 11010 19
20 10100 11110 20
21 10101 11111 21
22 10110 11101 22
23 10111 11100 23
24 11000 10100 24
25 11001 10101 25
26 11010 10111 26
27 11011 10110 27
28 11100 10010 28
29 11101 10011 29
30 11110 10001 30
31 11111 10000 31
Alternatively, more imperative style:
def encode(n: Long) = n ^ (n >>> 1)
def decode(n: Long) = {
var g = 0L
var bits = n
while (bits > 0) {
g ^= bits
bits >>= 1
}
g
}
def toBin(n: Long) = ("0000" + n.toBinaryString) takeRight 5
println("decimal binary gray decoded")
for (i <- 0 until 32) {
val g = encode(i)
println("%7d %6s %5s %7s".format(i, toBin(i), toBin(g), decode(g)))
}
Improved version of decode using functional style (recursion+local method). No vars and mutations.
def decode(n:Long)={
def calc(g:Long,bits:Long):Long=if (bits>0) calc(g^bits, bits>>1) else g
calc(0, n)
}
- Output:
decimal binary gray decoded
0 00000 00000 0
1 00001 00001 1
2 00010 00011 2
3 00011 00010 3
4 00100 00110 4
5 00101 00111 5
6 00110 00101 6
7 00111 00100 7
8 01000 01100 8
9 01001 01101 9
10 01010 01111 10
11 01011 01110 11
12 01100 01010 12
13 01101 01011 13
14 01110 01001 14
15 01111 01000 15
16 10000 11000 16
17 10001 11001 17
18 10010 11011 18
19 10011 11010 19
20 10100 11110 20
21 10101 11111 21
22 10110 11101 22
23 10111 11100 23
24 11000 10100 24
25 11001 10101 25
26 11010 10111 26
27 11011 10110 27
28 11100 10010 28
29 11101 10011 29
30 11110 10001 30
31 11111 10000 31
Scratch
![[1]](http://i.imgur.com/0sw5D4T.png){kind=link}
Seed7
The type bin32 is intended for bit operations that are not defined for integer values. Bin32 is used for the exclusive or (><) operation.
$ include "seed7_05.s7i";
include "bin32.s7i";
const func integer: grayEncode (in integer: n) is
return ord(bin32(n) >< bin32(n >> 1));
const func integer: grayDecode (in var integer: n) is func
result
var integer: decoded is 0;
begin
decoded := n;
while n > 1 do
n >>:= 1;
decoded := ord(bin32(decoded) >< bin32(n));
end while;
end func;
const proc: main is func
local
var integer: i is 0;
begin
for i range 0 to 32 do
writeln(i <& " => " <& grayEncode(i) radix 2 lpad0 6 <& " => " <& grayDecode(grayEncode(i)));
end for;
end func;- Output:
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
SenseTalk
Note: Inputs and outputs as strings
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- Output:
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
Sidef
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
- Output:
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
SparForte
As a structured script.
#!/usr/local/bin/spar
pragma annotate( summary, "gray" );
pragma annotate( description, "Gray code is a form of binary encoding where " );
pragma annotate( description, "transitions between consecutive numbers differ by" );
pragma annotate( description, "only one bit. Create functions to encode a number" );
pragma annotate( description, "to and decode a number from Gray code. Display the" );
pragma annotate( description, "normal binary representations, Gray code" );
pragma annotate( description, "representations, and decoded Gray code values for all" );
pragma annotate( description, "5-bit binary numbers (0-31 inclusive, leading 0's not" );
pragma annotate( description, "necessary). There are many possible Gray codes. The" );
pragma annotate( description, "following encodes what is called 'binary reflected" );
pragma annotate( description, "Gray code.'" );
pragma annotate( see_also, "http://rosettacode.org/wiki/Gray_code" );
pragma annotate( author, "Ken O. Burtch" );
pragma license( unrestricted );
pragma restriction( no_external_commands );
procedure gray is
bits : constant natural := 5;
subtype nat_values is natural;
function encode (binary : nat_values) return nat_values is
begin
return binary xor numerics.shift_right (binary, 1);
end encode;
-- SparForte 1.3 cannot print to numbers to different bases but we
-- we can write a function
function intToBin( nat_value : nat_values ) return string is
result : string;
v : nat_values := nat_value;
begin
if v = 0 then
result := '0';
else
while v > 0 loop
if (v and 1) = 1 then
result := '1' & @;
else
result := '0' & @;
end if;
v := numerics.shift_right( @, 1 );
end loop;
end if;
return "2#" & result & "#";
end intToBin;
function decode (gray : nat_values) return nat_values is
binary : nat_values;
bit : nat_values;
mask : nat_values := 2 ** (bits - 1);
begin
bit := gray and mask;
binary := bit;
for i in 2 .. bits loop
bit := numerics.shift_right (@, 1);
mask := numerics.shift_right (mask, 1);
bit := (gray and mask) xor @;
binary := @ + bit;
end loop;
return binary;
end decode;
j : nat_values;
ibinstr : string;
jbinstr : string;
begin
put_line ("Number Binary Gray Decoded");
for i in 0..31 loop
j := encode (i);
-- convert i and j to base 2 representation
ibinstr := intToBin(i);
jbinstr := intToBin(j);
-- for binary strings, right-justify
put (i, "ZZZZZ9" ) @
(' ' & strings.insert( ibinstr, 1, (8-strings.length(ibinstr)) * ' ' ) ) @
(' ' & strings.insert( jbinstr, 1, (8-strings.length(jbinstr)) * ' ' ) ) @
( " " ) @ (decode (j), "ZZZZZ9" );
new_line;
end loop;
end gray;
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
Standard ML
fun gray_encode b =
Word.xorb (b, Word.>> (b, 0w1))
fun gray_decode n =
let
fun aux (p, n) =
if n = 0w0 then p
else aux (Word.xorb (p, n), Word.>> (n, 0w1))
in
aux (n, Word.>> (n, 0w1))
end;
val s = Word.fmt StringCvt.BIN;
fun aux i =
if i = 0w32 then
()
else
let
val g = gray_encode i
val b = gray_decode g
in
print (Word.toString i ^ " :\t" ^ s i ^ " => " ^ s g ^ " => " ^ s b ^ "\t: " ^ Word.toString b ^ "\n");
aux (i + 0w1)
end;
aux 0w0
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))")
}
- Output:
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)
Tcl
namespace eval gray {
proc encode n {
expr {$n ^ $n >> 1}
}
proc decode n {
# Compute some bit at least as large as MSB
set i [expr {2**int(ceil(log($n+1)/log(2)))}]
set b [set bprev [expr {$n & $i}]]
while {[set i [expr {$i >> 1}]]} {
set b [expr {$b | [set bprev [expr {$n & $i ^ $bprev >> 1}]]}]
}
return $b
}
}
Demonstrating:
package require Tcl 8.6; # Just for %b format specifier
for {set i 0} {$i < 32} {incr i} {
set g [gray::encode $i]
set b [gray::decode $g]
puts [format "%2d: %05b => %05b => %05b : %2d" $i $i $g $b $b]
}
- Output:
0: 00000 => 00000 => 00000 : 0 1: 00001 => 00001 => 00001 : 1 2: 00010 => 00011 => 00010 : 2 3: 00011 => 00010 => 00011 : 3 4: 00100 => 00110 => 00100 : 4 5: 00101 => 00111 => 00101 : 5 6: 00110 => 00101 => 00110 : 6 7: 00111 => 00100 => 00111 : 7 8: 01000 => 01100 => 01000 : 8 9: 01001 => 01101 => 01001 : 9 10: 01010 => 01111 => 01010 : 10 11: 01011 => 01110 => 01011 : 11 12: 01100 => 01010 => 01100 : 12 13: 01101 => 01011 => 01101 : 13 14: 01110 => 01001 => 01110 : 14 15: 01111 => 01000 => 01111 : 15 16: 10000 => 11000 => 10000 : 16 17: 10001 => 11001 => 10001 : 17 18: 10010 => 11011 => 10010 : 18 19: 10011 => 11010 => 10011 : 19 20: 10100 => 11110 => 10100 : 20 21: 10101 => 11111 => 10101 : 21 22: 10110 => 11101 => 10110 : 22 23: 10111 => 11100 => 10111 : 23 24: 11000 => 10100 => 11000 : 24 25: 11001 => 10101 => 11001 : 25 26: 11010 => 10111 => 11010 : 26 27: 11011 => 10110 => 11011 : 27 28: 11100 => 10010 => 11100 : 28 29: 11101 => 10011 => 11101 : 29 30: 11110 => 10001 => 11110 : 30 31: 11111 => 10000 => 11111 : 31
TypeScript
// Gray code
function encode(v: number): number {
return v ^ (v >> 1);
}
function decode(v: number): number {
var result = 0;
while (v > 0) {
result ^= v;
v >>= 1;
}
return result;
}
console.log("decimal binary gray decoded");
for (var i = 0; i <= 31; i++) {
var g = encode(i);
var d = decode(g);
process.stdout.write(
" " + i.toString().padStart(2, " ") +
" " + i.toString(2).padStart(5, "0") +
" " + g.toString(2).padStart(5, "0") +
" " + d.toString(2).padStart(5, "0") +
" " + d.toString().padStart(2, " "));
console.log();
}
- Output:
decimal binary gray decoded 0 00000 00000 00000 0 1 00001 00001 00001 1 2 00010 00011 00010 2 3 00011 00010 00011 3 4 00100 00110 00100 4 5 00101 00111 00101 5 6 00110 00101 00110 6 7 00111 00100 00111 7 8 01000 01100 01000 8 9 01001 01101 01001 9 10 01010 01111 01010 10 11 01011 01110 01011 11 12 01100 01010 01100 12 13 01101 01011 01101 13 14 01110 01001 01110 14 15 01111 01000 01111 15 16 10000 11000 10000 16 17 10001 11001 10001 17 18 10010 11011 10010 18 19 10011 11010 10011 19 20 10100 11110 10100 20 21 10101 11111 10101 21 22 10110 11101 10110 22 23 10111 11100 10111 23 24 11000 10100 11000 24 25 11001 10101 11001 25 26 11010 10111 11010 26 27 11011 10110 11011 27 28 11100 10010 11100 28 29 11101 10011 11101 29 30 11110 10001 11110 30 31 11111 10000 11111 31
Ursala
#import std
#import nat
xor = ~&Y&& not ~&B # either and not both
btog = xor*+ zipp0@iitBX # map xor over the argument zipped with its shift
gtob = ~&y+ =><0> ^C/xor@lrhPX ~&r # fold xor over the next input with previous output
#show+
test = mat` * 2-$'01'***K7xSS pad0*K7 <.~&,btog,gtob+ btog>* iota32- Output:
00000 00000 00000 00001 00001 00001 00010 00011 00010 00011 00010 00011 00100 00110 00100 00101 00111 00101 00110 00101 00110 00111 00100 00111 01000 01100 01000 01001 01101 01001 01010 01111 01010 01011 01110 01011 01100 01010 01100 01101 01011 01101 01110 01001 01110 01111 01000 01111 10000 11000 10000 10001 11001 10001 10010 11011 10010 10011 11010 10011 10100 11110 10100 10101 11111 10101 10110 11101 10110 10111 11100 10111 11000 10100 11000 11001 10101 11001 11010 10111 11010 11011 10110 11011 11100 10010 11100 11101 10011 11101 11110 10001 11110 11111 10000 11111
Verilog
Function Based Approach:
`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
Module Based Approach:
`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
VHDL
Combinatorial encoder:
LIBRARY ieee;
USE ieee.std_logic_1164.all;
entity b2g is
port( bin : in std_logic_vector (4 downto 0);
gray : out std_logic_vector (4 downto 0)
);
end b2g ;
architecture rtl of b2g is
constant N : integer := bin'high;
begin
gray <= bin(n) & ( bin(N-1 downto 0) xor bin(N downto 1));
end architecture rtl;
Combinatorial decoder:
LIBRARY ieee;
USE ieee.std_logic_1164.all;
entity g2b is
port( gray : in std_logic_vector (4 downto 0);
bin : buffer std_logic_vector (4 downto 0)
);
end g2b ;
architecture rtl of g2b is
constant N : integer := bin'high;
begin
bin(N) <= gray(N);
gen_xor: for i in N-1 downto 0 generate
bin(i) <= gray(i) xor bin(i+1);
end generate;
end architecture rtl;
V (Vlang)
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.
fn enc(b int) int {
return b ^ b>>1
}
fn dec(gg int) int {
mut b := 0
mut g := gg
for ; g != 0; g >>= 1 {
b ^= g
}
return b
}
fn main() {
println("decimal binary gray decoded")
for b := 0; b < 32; b++ {
g := enc(b)
d := dec(g)
println(" ${b:2} ${b:05b} ${g:05b} ${d:05b} ${d:2}")
}
}
- Output:
Same as Go.
Wren
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)))")
}
- Output:
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
XPL0
include c:\cxpl\codes; \intrinsic 'code' declarations
func Gray2Bin(N); \Convert N from Gray code to binary
int N;
int S;
[S:= 1;
repeat N:= N>>S | N;
S:= S<<1;
until S=32;
return N;
]; \Gray2Bin
func Bin2Gray(N); \Convert N from binary to Gray code
int N;
return N>>1 | N;
proc BinOut(N); \Output N in binary
int N;
int R;
[R:= N&1;
N:= N>>1;
if N then BinOut(N);
ChOut(0, R+^0);
]; \BinOut
int N, G;
[for N:= 0 to 31 do
[BinOut(N); ChOut(0, 9\tab\);
G:= Bin2Gray(N);
BinOut(G); ChOut(0, 9\tab\);
BinOut(Gray2Bin(G)); CrLf(0);
];
]- Output:
0 0 0 1 1 1 10 11 10 11 10 11 100 110 100 101 111 101 110 101 110 111 100 111 1000 1100 1000 1001 1101 1001 1010 1111 1010 1011 1110 1011 1100 1010 1100 1101 1011 1101 1110 1001 1110 1111 1000 1111 10000 11000 10000 10001 11001 10001 10010 11011 10010 10011 11010 10011 10100 11110 10100 10101 11111 10101 10110 11101 10110 10111 11100 10111 11000 10100 11000 11001 10101 11001 11010 10111 11010 11011 10110 11011 11100 10010 11100 11101 10011 11101 11110 10001 11110 11111 10000 11111
zkl
fcn grayEncode(n){ n.bitXor(n.shiftRight(1)) }
fcn grayDecode(g){ b:=g; while(g/=2){ b=b.bitXor(g) } b }foreach n in ([0..31]){
g:=grayEncode(n); b:=grayDecode(g);
println("%2d(%05.2B) --> %2d(%05.2B) --> %2d(%05.2B)".fmt(n,n,g,g,b,b));
}- Output:
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)
Categories:
- Programming Tasks
- Solutions by Programming Task
- 11l
- 8080 Assembly
- 8051 Assembly
- Action!
- Ada
- Aime
- ALGOL 68
- Amazing Hopper
- APL
- Arturo
- AutoHotkey
- AWK
- BASIC
- BBC BASIC
- FreeBASIC
- GW-BASIC
- Liberty BASIC
- PowerBASIC
- PureBasic
- VBScript
- XBasic
- Batch File
- Bc
- BCPL
- C
- C sharp
- C++
- CoffeeScript
- Common Lisp
- Component Pascal
- Cowgol
- Crystal
- D
- Delphi
- Draco
- DWScript
- EasyLang
- EDSAC order code
- Elixir
- Erlang
- Euphoria
- F Sharp
- Factor
- Forth
- Fortran
- Frink
- Go
- Groovy
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Jq
- Julia
- K
- Kotlin
- Limbo
- Lobster
- Logo
- Lua
- M2000 Interpreter
- Mathematica
- Wolfram Language
- MATLAB
- Mercury
- Modula-2
- Nim
- NOWUT
- OCaml
- PARI/GP
- Pascal
- PascalABC.NET
- Perl
- Phix
- PHP
- Picat
- PicoLisp
- PL/I
- PL/M
- Prolog
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- Scratch
- Seed7
- SenseTalk
- Sidef
- SparForte
- SQL
- Standard ML
- Swift
- Tcl
- TypeScript
- Ursala
- Verilog
- VHDL
- V (Vlang)
- Wren
- Wren-fmt
- XPL0
- Zkl