# 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.

• – Martin Ender Oct 2 '16 at 21:08
• Can we take input as a number? – xnor Oct 2 '16 at 21:12
• Less obviously, also related. – Martin Ender Oct 2 '16 at 21:12
• Can I take both input and output reversed, e.g. 0011 for 8 – Ton Hospel Oct 3 '16 at 6:32
• @TonHospel sorry I didn't see your question about reversed I/O. As I told 1000000000 my answer is no. – Patrick Roberts Oct 3 '16 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.

# 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 '16 at 7:41 • On the other hand, \K makes things even easier for you. – Neil Oct 3 '16 at 9:06 • Haaaaa... Now I want to see the \G implementation as well. – Magic Octopus Urn Oct 4 '16 at 1:02 • @carusocomputing You can see older versions of a submission by clicking on the edited link – Ton Hospel Oct 4 '16 at 6:58 # Haskell, 118 115 108 bytes g 0=[""] g n|a<-g$n-1=map('0':)a++map('1':)(reverse a)
d=dropWhile

{[{1$^}*]2b)_2/^2b} This converts from Gray code to index, increments, and converts back to Gray code. ## 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. – Patrick Roberts Oct 3 '16 at 12:37 • @PatrickRoberts - Sure. That makes sense. – Arnauld Oct 3 '16 at 12:53 • @PatrickRoberts Really? How does a recursion limit not fall under "memory limitations imposed by the environment."? – Sanchises Oct 9 '16 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. – Patrick Roberts Oct 9 '16 at 15:58 • @sanchises Looking over my reply, that was a poor argument. The main issue is that the limitation isn't imposed by the environment, it's imposed by the algorithm. There are other answers which recurse for every bit rather than for every incremental value, and I find those to be more acceptable since it works for a much wider range of values. – Patrick Roberts Oct 9 '16 at 16:47 ## 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 ^ ? – Ton Hospel Oct 3 '16 at 9:07
• @TonHospel The regex tried to match everywhere without it. (Replace mode defaults to a global replacement.) – Neil Oct 3 '16 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

## 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. – ElPedro Oct 4 '16 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 :) – Morwenn Oct 4 '16 at 10:25
• Just saw that. Nice answer :-) – ElPedro Oct 4 '16 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 – Patrick Roberts Oct 4 '16 at 14:45
• @PatrickRoberts I'll check later. long instead of int might solve the problem. – Morwenn Oct 4 '16 at 14:46

## 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. – Patrick Roberts Oct 9 '16 at 3:40
• @PatrickRoberts Added the link and the description as you requested. – AlexRacer Oct 10 '16 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.

# 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