# Give me the Gray Code list of bit width n

The Gray Code is a sequence of binary numbers of bitwidth n where successive numbers differ only in one bit (see example output).

Reference

Example input:

3


Example output:

000
001
011
010
110
111
101
100


Notes:

• This question seems to have a dupe but it's not, for that question is not a code-golf, and it demands different output. It will help to check out it's answers, though.
• You may assume a variable n which contains the input.
• Considering that the other question is a fastest-code code-challenge without an objective winning criterion (fastest measured how?), I propose closing the other and reopening this one. Jul 3, 2014 at 12:59
• I agree with @dennis and therefore I have upvoted the following unpopular answer on the original question. "If the answer you are looking for is strictly a fast result, then if you declare an array (of the gray codes)..." However the original question aready has a 7-character and a 4-character answer so I don´t see much room for improvement. Therefore I am not casting a reopen vote at present. Jul 3, 2014 at 13:10
• It's awfully similar to Traverse all numbers with only one bit flip per step though... Jul 3, 2014 at 13:58
• The earliest Gray code question isn't great, but it already has answers which are fundamentally the same as the answers which this question wants, and which are not likely to be improved. I think it would have made more sense to leave this one closed and change the other one to a code golf. Jul 3, 2014 at 15:57

# J, 24 bytes

[:#:@/:2|2+/\"1@#:@i.@^]


Try it online!

Different algorithm that converts $$\1..2^n\$$ to regular binary, scan sums each of the binary digits, mods by 2, takes the grade up, and converts back to binary.

This works because scan summing the digits returns the inverse grey code sequence - A006068, and grade up is self-inverse.

# J, 24 bytes

[:#:@(22 b.<.@-:)[:i.2^]


Try it online!

Straightforward implementation of the "XOR with it's own floored half" algorithm. Note that 22 b. is XOR.

# Python 3, 48 bytes

for i in range(1<<n):print(bin(2**n+i//2^i)[3:])


Explanation:

• The outer loop iterates over numbers from 0 to 2^n - 1
• For each number i, the expression bin(2**n + i//2 ^ i) calculates the Gray code:
• 2^n is added to i//2, effectively shifting i one position to the right
• The XOR operator ^ is used to perform the Gray code transformation
• Adding 2^n ensures the resulting binary representation has n bits
• bin() converts the integer to a binary string
• [3:] slices the binary string to remove the prefix '0b', leaving only the n-bit Gray code

Ungolfed:

n = int(input())  # Take input for the number of bits in the Gray code

for i in range(1 << n): # Iterate over numbers from 0 to 2^n - 1
gray_code = bin(2**n + i // 2 ^ i) # Calculate the Gray code for the current number
print(gray_code[3:]) # Print the Gray code excluding the prefix '0b'


Try it online!

## JavaScript (77)

for(i=0;i<1<<n;)alert((Array(n*n).join(0)+(i>>1^i++).toString(2)).substr(-n))


More browser-friendly version (console.log and prompt()):

n=prompt();for(i=0;i<1<<n;)console.log((Array(n*n).join(0)+(i>>1^i++).toString(2)).substr(-n))

• Maybe this array...join is overkill for(i=0;i<(l=1<<n);i++)console.log((i^(i>>1)|l).toString(2).slice(1)); Jul 3, 2014 at 16:00

# Python 2 (47)

for i in range(2**n):print bin(2**n+i/2^i)[3:]


The expression i/2^i for the i'th gray code number is from the this answer. To add leading zeroes that pad to length n, I add 2**n before converting to a binary string, creating a string of length n+1. Then, I truncate the leading 1 and number type prefix 0b with [3:].

### Ruby — 42 39

Same algorithm, different language:

(2**n).times{|b|puts"%0#{n}b"%(b>>1^b)}


Switching from #map to #times as @voidpigeon suggests saves 3 characters.

• Instead of [*0...2**n].map you can use (2**n).times. Jul 7, 2014 at 18:08

# K (ngn/k), 10 bytes

+~0=':!n#2


Try it online!

• the odometer overload of ! took me by surprise. very cool ! Aug 21, 2019 at 15:11

# APL (Dyalog Classic), 11 bytes

2≠/0,↑,⍳n⍴2


Try it online!

n⍴2 is 2 2...2 - a vector of n twos

⍳ is the indices of an n-dimensional array with shape 2 2...2 - that is, a 2×2×...×2 array of nested vectors. As we use 0-indexing (⎕IO←0), those are all binary vectors of length n.

, flatten the 2×2×...×2 shape, so we get a vector of 2n nested binary vectors

↑ "mix" - convert the vector of vectors to a solid 2n×n matrix. It looks like this:

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1


0, prepends zeroes to the left of the matrix

2≠/ computes the pairwise (2) xor (≠) along the last dimension (/ as opposed to ⌿); in other words, every element gets xor-ed with its right neighbour, and the last column disappears

0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0

• would you mind adding a quick explanation? Jul 9, 2018 at 5:14
• @Jonah sure, added
– ngn
Jul 9, 2018 at 9:37
• very clever, thx Jul 9, 2018 at 12:51

# Japt, 14 12 bytes

2pU Ç^z)¤ùTU


Shaved off two bytes thanks to ETHproductions.

Try it online!

• Perfect example of how ù is used. Since N.z(n) is integer division with default arg = 2, you can save two bytes with 2pU Ç^z)¤ùTU: Try it online! Jul 9, 2018 at 18:31
• @ETHproductions Thanks, I still miss the default args every now and then. Very handy, thanks a lot. Jul 9, 2018 at 18:43

# K (ngn/k), 25 bytes

{(x-1){,/0 1,''|:\x}/0 1}


Try it online!

• |:\xis "reverse scan x". applies reverse to x until the output equals the input, and shows each iteration. returns (0 1; 1 0) on first pass.
• 0 1,'' is "0 1 join each each". joins a 0 to each value of 1st elem, and 1 to each value of 2nd elem, giving ((0 0; 0 1);(1 1; 1 0)) on first pass
• ,/ is "join over", and flattens to list.
• (x-1){...}/0 1is "apply {func} over 0 1 x-1 times". takes the output of the last iteration as input

## Python - 54

Based off of an algorithm from the reference given in the challenge:

for i in range(2**n):print'{1:0{0}b}'.format(n,i>>1^i)


Ungolfed:

# For each of the possible 2**n numbers...
for num in range(2**n):
gray = num>>1 ^ num

# Print in binary and pad with n zeros.
print '{1:0{0}b}'.format(grey)


## PowerShell(168)

Amateur PowerShell'r back with another attempt at golF! Hope you don't mind! At the very least these questions are fun, and a learning experience to boot. Assuming n has been inputted, we have:

$x=@('0','1');for($a=1;$a-lt$n;$a++){$x+=$x[($x.length-1)..0];$i=[Math]::Floor(($x.length-1)/2);0..$i|%{$x[$_]='0'+$x[$_]};($i+1)..($x.length-1)|%{$x[$_]='1'+$x[$_]}}$x


Because the PowerShell I'm working with is only 2.0, I can't use any bit shifting cmdlets which might make for shorter code. So I took advantage of a different method described in the question source, flipping the array and adding it to itself, appending a 0 to the front of the top half, and a 1 to the bottom half.

# APL (22)

{(0,⍵)⍪1,⊖⍵}⍣(n-1)⍪0 1


This outputs a n-by-2^n matrix containing the bits as its rows:

      n←3
{(0,⍵)⍪1,⊖⍵}⍣(n-1)⍪0 1
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0


Explanation:

• {...}⍣(n-1)⍪0 1: run the function n-1 times with initial input the matrix (0 1)T (which is the 1-bit gray code)

• (0,⍵): each row of ⍵ with a 0 prefixed,
• ⍪: on top of,
• 1,⊖⍵: each row of ⍵ with an 1 prefixed, in reversed order

## F# (86)(84) (80)

for i in 0..(1<<<n)-1 do printfn"%s"(Convert.ToString(i^^^i/2,2).PadLeft(n,'0'))


This could probably be improved further.

Also note, if run in FSI, you'd need to open System;; first. If you'd like to avoid importing that, (and if you don't care about the order in which the values are printed) you can use this 82-character version:

for i in 0..(1<<<n)-1 do(for j in 0..n-1 do printf"%i"((i^^^i/2>>>j)%2));printfn""


# MATL, 10 bytes

W:qt2/kZ~B


Try it online!

The good old "XOR n with n>>2" method.

W - compute 2^(input) (gets input implicitly)
:q - create range of numbers from 0 to 2^n - 1
t - duplicate that range
2/k - MATL doesn't have bitshift, so divide (each number) by 2 and floor
Z~ - elementwise XOR that result with the original 0 to 2^n - 1 array
B - convert each number in the result to binary
(Implicitly display output.)

# J, 14 bytes

#:(,#+|.)^:n 0


Try it online!

A snippet assuming variable n as specified in the challenge.

A Gray code of order n can be constructed from order n-1 by the following steps:

• Take two copies of the previous one.
• Reverse the second.
• Prepend 0 bit to the first and 1 to the second.

As a list of integer values, prepending the 1 bit corresponds to adding 2^(n-1), which is precisely the length of the previous Gray code, and prepending 0 is a no-op. Therefore, one such iteration can be summarized to "append length plus reverse to self", which is what (,#+|.) does.

#:(,#+|.)^:n 0
(     )^:n 0    Starting from a single 0, repeat n times:
|.            Reverse
#+              Add length to each item
,                Append to self
(0 -> 0 1 -> 0 1 3 2 -> 0 1 3 2 6 7 5 4 -> ...)
#:                Convert each number to binary


# J, 17 bytes

[:#:(,#+|.)@[&0&0


Try it online!

Same solution as a function. @[&0&0 part is a bit tricky:

f@[&0&0
f          A monadic(1-arg) function
@[        Convert to a dyadic(2-arg) function that uses the left arg,
ignoring the right
&0      Attach a dummy argument on the right side to get a "bind" function
&0    Treat a "bind" function as dyadic, where left arg becomes
repetition count and right arg is the starting value,
and set 0 as the starting value


# Jq 1.5, 105 100 bytes

def g(n):if n<2then. else map([0]+.)+(reverse|map([1]+.))|g(n-1)end;[[0],[1]]|g(N)[]|map("\(.)")|add


Assumes N provides input. e.g.

def N: 3 ;


Expanded

def g(n):  # recursively compute gray code
if n < 2
then .
else map([0]+.) + (reverse|map([1]+.)) | g(n-1)
end;

[[0],[1]]                 # initial state
| g(N)[]                    # for each element in array of gray codes
| map("\(.)")|add           # covert to a string


Try it online!

# Japt, 10 bytes

³Ç¤ÅÃf_Ê¥U


Try it online!

# Scala 3, 102 bytes

Golfed version. Attempt This Online!

for(i<-0 to scala.math.pow(2,n).toInt-1)println((scala.math.pow(2,n).toInt+i/2^i).toBinaryString.tail)


Ungolfed version. Attempt This Online!

object Main {
def main(args: Array[String]): Unit = {
val n = 3
for (i <- 0 until scala.math.pow(2, n).toInt) {
val result = (scala.math.pow(2, n).toInt + i / 2 ^ i).toBinaryString
println(result.drop(1))
}
}
}


# Perl 5 + -a, 38 bytes

printf"%0@{F}b

# APL(NARS), 31 chars

{2∣↑+/(⍵⍴2)∘⊤¨¨(⌊m÷2)m←¯1+⍳2*⍵}


I hope this generate gray code. It is something as {toBinary¨{⍵ xor ⌊⍵÷2}¨0..¯1+2*⍵}. Test:

  f←{2∣↑+/(⍵⍴2)∘⊤¨¨(⌊m÷2)m←¯1+⍳2*⍵}
f 2
0 0  0 1  1 1  1 0
f 3
0 0 0  0 0 1  0 1 1  0 1 0  1 1 0  1 1 1  1 0 1  1 0 0
f 4
0 0 0 0  0 0 0 1  0 0 1 1  0 0 1 0  0 1 1 0  0 1 1 1  0 1 0 1  0 1 0 0  1 1 0 0  1 1 0 1  1 1 1 1  1 1 1 0  1 0 1 0  1 0 1 1  1 0 0 1  1 0 0 0


## T-SQL 134

This challenge is asking to return the Cartesian power of {(0),(1)}. This snippet builds the code which would execute the Cartesian product of {(0),(1)} n times.

DECLARE @ int=4,@s varchar(max)='SELECT*FROM's:set @s+='(VALUES(0),(1))t'+ltrim(@)+'(b)'if @>1set @s+=','set @-=1if @>0goto s exec(@s)

• It's asking for the cartesian power in a specific order. Does your code account for that? Feb 25, 2017 at 18:14