Incrementing Gray Codes

Question

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
• non-padded boolean array

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 code-golf, 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.

Answer 1

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.

Answer 2

JavaScript (ES6), 58 bytes

s=>s.replace(s.split`1`.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.

Answer 3

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.

Answer 4

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

Answer 5

MATL, 18 bytes

ZBtE:t2/kZ~tb=fQ)B

Try it online! Or verify all test cases.

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 a₀, 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·a₀ 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

Answer 6

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

Answer 7

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%}

---

Alternative approach (19 bytes)

{[{1$^}*]2b)_2/^2b}

This converts from Gray code to index, increments, and converts back to Gray code.

Answer 8

Retina, 25 bytes

^(10*10*)*
$1:
1:
0
.?:
1

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

Answer 9

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

Answer 10

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.

Answer 11

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.

Answer 12

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.

Click here to try it for the test cases.

Answer 13

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
                                                padding on the left.

                          [: 22 b./             Reduce the rows of the resulting 
                                                matrix with XOR, giving us the 
                                                normal binary
                      @#.                       Convert to int and...
                   @>:                          Increment and...
      (22 b. <.@-:)                             XOR that with its own floored half
[: #:@                                          And turn the result back to binary

Answer 14

Actually, 20 19 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".