# Introduction

A Gray Code is an alternative to binary representation in which a number is incremented by toggling only one bit, rather than a variable amount of bits. Here are some gray codes along with their decimal and binary equivalents:

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


### Cyclic Bit Pattern of a Gray Code

Sometimes called "reflected binary", the property of changing only one bit at a time is easily achieved with cyclic bit patterns for each column starting from the least significant bit:

bit 0: 0110011001100110011001100110011001100110011001100110011001100110
bit 1: 0011110000111100001111000011110000111100001111000011110000111100
bit 2: 0000111111110000000011111111000000001111111100000000111111110000
bit 3: 0000000011111111111111110000000000000000111111111111111100000000
bit 4: 0000000000000000111111111111111111111111111111110000000000000000
bit 5: 0000000000000000000000000000000011111111111111111111111111111111


...and so on.

# Objective

Given a non-padded input string of a gray code, increment the gray code by alternating a single character in the sequence or prepending a 1 (when incrementing to the next power of 2), then output the result as a non-padded gray code.

### Caveats

• Do not worry about taking 0 or an empty string as input.
• The lowest input will be 1, and there is no upper-bound to the string length other than memory limitations imposed by the environment.
• By non-padded string, I mean there will be no leading or trailing whitespace (other than an optional trailing newline), and no leading 0s in the input or output.

### I/O formats

The following formats are accepted form for input and output, but strings are encouraged over other formats:

• most significant "bit" first
• non-padded character array or string of ASCII '1's and '0's
• non-padded integer array of 1s and 0s

What's not allowed:

• least significant "bit" first
• decimal, binary or unary integer
• fixed-length data-structure
• character array or string of non-printable ASCII indices 1 and 0

### Tests

input -> output
1 -> 11
11 -> 10
111 -> 101
1011 -> 1001
1111 -> 1110
10111 -> 10110
101100 -> 100100
100000 -> 1100000


More tests can be added by request.

# Criteria

This is , so shortest program in bytes wins! All ties will be broken by favoring earlier submissions; standard loopholes apply. The best submitted answer will be accepted October 9th, 2016, and updated whenever better answers are given.

• Oct 2, 2016 at 21:08
• Can we take input as a number?
– xnor
Oct 2, 2016 at 21:12
• Less obviously, also related. Oct 2, 2016 at 21:12
• Can I take both input and output reversed, e.g. 0011 for 8 Oct 3, 2016 at 6:32
• @TonHospel sorry I didn't see your question about reversed I/O. As I told 1000000000 my answer is no. Oct 3, 2016 at 18:45

## Jelly, 10 8 bytes

Thanks to Dennis for saving 2 bytes.

^\Ḅ‘^H$B  Input and output are lists of 0s and 1s. Try it online! ### Explanation The inverse of the Gray code is given by A006068. Using this we don't need to generate a large number of Gray codes to look up the input. One classification of this sequence given on OEIS is this: a(n) = n XOR [n/2] XOR [n/4] XOR [n/8] ...  Where the [] are floor brackets. Consider the example of 44 whose binary representation is 101100. Dividing by 2 and flooring is just a right-shift, chopping off the least-significant bit. So we're trying to XOR the following numbers 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1  Notice that the nth column contains the first n bits. Hence, this formula can be computed trivially on the binary input as the cumulative reduction of XOR over the list (which basically applies XOR to each prefix of the list and gives us a list of the results). This gives us a simple way to invert the Gray code. Afterwards, we just increment the result and convert it back to the Gray code. For the latter step we use the following definition: a(n) = n XOR floor(n/2)  Thankfully, Jelly seems to floor the inputs automatically when trying to XOR them. Anyway, here is the code: ^\ Cumulative reduce of XOR over the input. Ḅ Convert binary list to integer. ‘ Increment. ^H$     XOR with half of itself.
B    Convert integer to binary list.

• You don't need the Ḟ$; bitwise operators cast to int. Oct 3, 2016 at 0:25 • @Dennis Thanks, I discovered that while writing up. :) Oct 3, 2016 at 0:25 • @MartinEnder Is the integer it converts to internally a big integer? Oct 3, 2016 at 1:54 • @PatrickRoberts yes, if necessary - it's Python under the hood. Oct 3, 2016 at 2:20 • Nice analysis and explanation. Oct 4, 2016 at 13:55 # Perl, 27 25 bytes Includes +1 for -p Give input string on STDIN, e.g. gray.pl <<< 1010  gray.pl: #!/usr/bin/perl -p s%(10*\K1(\K0)*)*%1-$&%e


Perl has no cheap infinite-precision integers. So directly toggle the right bit which is the one just before where the last odd-numbered 1 would be.

• Wow, \G really makes things easy for you!
– Neil
Oct 3, 2016 at 7:41
• On the other hand, \K makes things even easier for you.
– Neil
Oct 3, 2016 at 9:06
• Haaaaa... Now I want to see the \G implementation as well. Oct 4, 2016 at 1:02
• @carusocomputing You can see older versions of a submission by clicking on the edited link Oct 4, 2016 at 6:58

## JavaScript (ES6), 58 bytes

s=>s.replace(s.split1.length%2?/.$/:/.?(?=10*$)/,c=>1-c)


Directly toggles the appropriate bit. Explanation: As shown in MartinEnder♦'s answer, each bit in a decoded Gray code is the cumulative XOR, or parity, of itself and the bits to its left. We then need to increment the number which causes a carry ripple that toggles all the rightmost 1 bits to 0 and then the next 0 bit to 1. Re-encoding results in a code with just that one 0 bit position toggled. If the parity of all the 1 bits is even, then the rightmost bit is 0 and we therefore just toggle the last bit. If the parity of all the 1 bits is odd, then the rightmost bits are 1, and we need to find the last 1 bit. This is now the last of the carried bits, so the bit we need to toggle is the next bit from the right.

• Very nice method. Is the first ? in /.?(?=10*$)/ really required? Oh, nevermind. Yes it is. :-) Oct 3, 2016 at 5:57 ## JavaScript (ES6), 53 bytes (non-competing) A recursive function which builds all gray codes until the input is found, then stops at the next iteration. The highest possible input depends on the browser recursion limit (about 13 bits in Firefox and 15 bits in Chrome). f=(s,n=1)=>(b=(n^n/2).toString(2),s)?f(b!=s&&s,n+1):b console.log(f("1")); // -> 11 console.log(f("11")); // -> 10 console.log(f("111")); // -> 101 console.log(f("1011")); // -> 1001 console.log(f("1111")); // -> 1110 console.log(f("10111")); // -> 10110 console.log(f("101100")); // -> 100100 console.log(f("100000")); // -> 1100000 • I'm afraid this submission doesn't qualify, since the method does not work for unbounded string lengths. Please change to non-competitive if you want to keep this answer on here. Oct 3, 2016 at 12:37 • @PatrickRoberts - Sure. That makes sense. Oct 3, 2016 at 12:53 • @PatrickRoberts Really? How does a recursion limit not fall under "memory limitations imposed by the environment."? Oct 9, 2016 at 14:53 • @sanchises I was referring to heap memory, but more to the point, this program recurses for every possible gray code up to the one being tested, which is extremely inefficient. Technically this could be submitted as "Node.js 6.5" and have --harmony added for penalty bytes in order to have access to tail-call recursion optimization, which appears to be possible here. Oct 9, 2016 at 15:58 • @PatrickRoberts I disagree. The algorithm itself does not impose a fundamental limit. It's inefficient, yes, but I feel that efficiency is not a requirement for code-golf. I don't think some thing that is less or "more acceptable" is a good criterion for disqualifying an entire answer. Personally, I would let this one go. Judging by your challenge description, it seems you fell for this trap - it seems that you wanted people to work on 'string level' rather than 'number' level. Oct 9, 2016 at 20:35 # Haskell, 118 115 108 bytes g 0=[""] g n|a<-g$n-1=map('0':)a++map('1':)(reverse a)
d=dropWhile
f s=d(=='0')$(d(/='0':s)$g$1+length s)!!1  Try it on Ideone. Naive approach: g generates the set of all gray codes with length n (with 0-padding), f calls g with length(input)+1, removes all elements until 0<inputstring> is found and returns the next element (truncating a possibly leading 0). • Good first answer! I hope we can get some more efficient ones soon. Oct 2, 2016 at 23:01 # MATL, 18 bytes ZBtE:t2/kZ~tb=fQ)B  ### Explanation Let a(n) denote the sequence of integers corresponding to Gray codes (OEIS A003188). The program uses the characterization a(n) = n XOR floor(n/2), where XOR is bit-wise. Essentially, the code converts the input to an integer a0, finds that integer in the sequence, and then selects the next term. This requires generating a sufficiently large number of terms of the sequence a(n). It turns out that 2·a0 is sufficiently large. This stems from the fact that the Gray code a(n) never has more binary digits than n. Let's take input '101' as an example. ZB % Input string implicitly. Convert from binary string to integer % STACK: 5 t % Duplicate % STACK: 5, 5 E % Multiply by 2. This is the number of terms we'll generate from the sequence % STACK: 5, 10 : % Range % STACK: 5, [1 2 3 4 5 6 7 8 9 10] t % Duplicate % STACK: 5, [1 2 3 4 5 6 7 8 9 10], [1 2 3 4 5 6 7 8 9 10] 2/k % Divide by 2 and round down, element-wise % STACK: 5, [1 2 3 4 5 6 7 8 9 10], [0 1 1 2 2 3 3 4 4 5] Z~ % Bit-wise XOR, element-wise % STACK: 5, [1 3 2 6 7 5 4 12 13 15] t % Duplicate % STACK: 5, [1 3 2 6 7 5 4 12 13 15], [1 3 2 6 7 5 4 12 13 15] b % Bubble up % STACK: [1 3 2 6 7 5 4 12 13 15], [1 3 2 6 7 5 4 12 13 15], 5 = % Equality test, element-wise % STACK: [1 3 2 6 7 5 4 12 13 15], [0 0 0 0 0 1 0 0 0 0] f % Find: yield (1-based) index of nonzero values (here there's only one) % STACK: [1 3 2 6 7 5 4 12 13 15], 6 Q % Increase by 1 % STACK: [1 3 2 6 7 5 4 12 13 15], 7 ) % Apply as index % STACK: 4 B % Convert to binary array % STACK: [1 0 0] % Implicitly display  • I notice the output is space-delimited characters... is it printing some sort of array? Oct 2, 2016 at 23:06 • @PatrickRoberts Yes, exactly. I assumed it's acceptable, is it? Oct 2, 2016 at 23:07 • I'll accept it as-is. I've already loosened my requirements on I/O format, so there's no point in making it more strict again. Nice job. Oct 2, 2016 at 23:09 ## CJam (19 bytes) {_2b__(^@1b1&*)^2b}  Online demo. This is an anonymous block (function) from bit array to bit array, which the demo executes in a loop. It works on the simple principle that if the number of set bits is even we should toggle the least significant bit, and otherwise we should toggle the bit to the left of the least significant set bit. Actually identifying that bit turns out to be much easier using bit hacks on an integer than using the list of bits. ### Dissection { e# Declare a block: _2b e# Convert the bit array to a binary number __(^ e# x ^ (x-1) gives 1s from the least significant set bit down @1b1& e# Get the parity of the number of set bits from the original array * e# Multiply: if we have an even number of set bits, we get 0; e# otherwise we have 2**(lssb + 1) - 1 )^ e# Increment and xor by 1 or 2**(lssb + 1) 2b e# Base convert back to a bit array }  Working solely with the bit array, I think it's necessary to reverse it: working with the left-most 1 is much easier than the right-most. The best I've found so far is (24 bytes): {W%_1b)1&1$+1#0a*1+.^W%}


{[{1$^}*]2b)_2/^2b}  This converts from Gray code to index, increments, and converts back to Gray code. ## Retina, 25 bytes ^(10*10*)*$1:
1:
0
.?:
1


I feel sure there should be a better way of doing this...

• Do you actually need the ^ ? Oct 3, 2016 at 9:07
• @TonHospel The regex tried to match everywhere without it. (Replace mode defaults to a global replacement.)
– Neil
Oct 3, 2016 at 9:13

# 05AB1E, 12 bytes

Uses CP-1252 encoding.

CÐ<^¹SOÉ*>^b


Try it online!

Explanation

Example for input 1011.

C              # convert to int (bigint if necessary)
# STACK: 11
Ð             # triplicate
# STACK: 11, 11, 11
<            # decrease by 1
# STACK: 11, 11, 10
^           # XOR
# STACK: 11, 1
¹          # push first input
# STACK: 11, 1, 1011
S         # split to list
# STACK: 11, 1, [1,0,1,1]
O        # sum
# STACK: 11, 1, 3
É       # mod 2
# STACK: 11, 1, 1
*      # multiply
# STACK: 11, 1
>     # increase by 1
# STACK: 11, 2
^    # XOR
# STACK: 9
b   # convert to binary
# STACK: 1001
# implicitly print top of stack


## C++, 205 bytes

#include <string>
std::string g(std::string s){int i,z;if(s=="1")return"11";for(i=z=0;i<s.length();i++)if(s[i]=='1')z++;i--;if(z%2){char c=s[i];s.erase(i);s=g(s);s+=c;}else{s[i]=s[i]==49?48:49;}return s;}


Description: Even numbers have even number of ones. Variable z counts ones; if z is even (z mod 2 = z%2 = 0 - else branch), alter the last bit; if z is odd, call this function again without the last character and calculate new value, then append the last character afterwards.

• Thanks for your submission. If you could provide a short description of your approach and a link to an online compilation of this as a demo, I'd really appreciate that. Oct 9, 2016 at 3:40
• @PatrickRoberts Added the link and the description as you requested. Oct 10, 2016 at 23:16

## Batch, 199 197 bytes

@echo off
set/ps=
set r=
set t=%s:0=%
if 1%t:11=%==1 goto g
:l
set b=%s:~-1%
set s=%s:~,-1%
set r=%b%%r%
if %b%==0 goto l
if 0%s%==0 set s=0
:g
set/ab=1-%s:~-1%
echo %s:~,-1%%b%%r%


Reads input from STDIN into variable s. Removes the 0s and does a parity check on the 1s and if there are an odd number it strips the rightmost 0s in a loop, stopping when it strips a 1. s therefore contains the even parity prefix and r the rest of the string. s is set to zero if it was blank so that its last digit can be toggled, and then everything is concatenated.

## Python 2.7, 68 characters

def f(s):i=long(s,2);print bin(i^(1,(i&-i)<<1)[s.count('1')&1])[2:]


## Python 3, 68 characters

def f(s):i=int(s,2);print(bin(i^(1,(i&-i)<<1)[s.count('1')&1])[2:])


This function converts the given binary string to an integer then xor the last bit if the number of set bits in the original string is even, or its swaps the bit to the left of the rightmost set bit if the number of set bits in the original string is odd. Then it converts the result to a binary string and removes the 0b boolean prefix.

• You can save 1 byte by removing the space after def f(s): and (assuming Python 2) another by using print instead of return. Oct 4, 2016 at 10:21
• @ElPedro Thanks, I also applied a condition trick and factored out the left-hand size of a xor to save a few additional characters :) Oct 4, 2016 at 10:25
• Just saw that. Nice answer :-) Oct 4, 2016 at 10:27
• Um.. checking python documentation, it looks like int() generates a 32 bit integer, although my requirement is for you to increment any length string. I'm not sure that this qualifies as a valid submission Oct 4, 2016 at 14:45
• @PatrickRoberts I'll check later. long instead of int might solve the problem. Oct 4, 2016 at 14:46

# Actually, 2019 13 bytes

Based on Martin Ender's Jelly answer with my own version of "cumulative reduce of XOR over the input". Golfing suggestions welcome. Try it online!

σ1♀&2@¿u;½≈^├


Ungolfing

      Implicit input a as a list, such as [1,0,1,1,0,0].
σ     Get the cumulative sums of a.
1♀&   Map x&1 (equivalent to x%2) over every member of the cumulative sum.
2@¿   Convert from binary to decimal.
u     Increment x.
;½≈   Duplicate and integer divide by 2.
^     XOR x and x//2.
├     Convert to binary to obtain our incremented Gray code.
Implicit return as a string, such as "100100".


# J, 38 bytes

[:#:@(22 b.<.@-:)@>:@#.[:22 b./[:#:#.\


Try it online!

This is essentially Martin's algorithm in J.

Note that 22 b. is XOR.

                                    [: #: #.\   Creates the prefixes of the input
converts to a number, then converts
back to binary.  Needed to get the