Traverse all numbers with only one bit flip per step

Question

You can count 0, 1, 2, 3, 4. But to get from 3 to 4 you have to change 3 bits at once. Given a number of bits, how can you go through all numbers once, but change at each step only 1! bit.

Here is an example for 3 bits:

000 100 110 010 011 111 101 001

so the output is:

0 1 3 2 6 7 5 4

Rules:

• given a number of bits n, return a list of 2^n unique numbers
• between to consecutive numbers only one bit is different
• the shorter the code the better

Answer 1

Python 3:

for i in range(2**n):i^i//2

(Doh. Overlooked that this solutions is already known. Would delete it if stackexchange allowed it)

Answer 2

GolfScript, 13 chars

~2\?,{.2/^}%`

For example, the input 3 produces the output [0 1 3 2 6 7 5 4].

Here's a de-golfed version with comments:

~              # evaluate the input, turning it from a string into a number
2 \ ?          # raise 2 to the power given by the input...
,              # ...and turn it into a list containing the numbers from 0 to 2^n-1
{ . 2 / ^ } %  # xor each number in the list with itself divided by 2
`              # un-eval the list into a string for output

It's perhaps interesting to note that there are no particular "golfing tricks" involved — this is basically the most obvious and straightforward way to solve this task in GolfScript.

Answer 3

C++, 188 bytes

#include <cstdlib>
#include <iostream>
#define y if(b)f(b-1)
int x=0;
void f(int b){y;std::cout<<(x^=1<<b)<<' ';y;}
int main(int,char**v){int b=std::atoi(v[1]);std::cout<<x<<' ';y;}

Specify the number of bits on the command line and it will print a list of space separated integers.

Answer 4

F# (32)

[for i in 0..(1<<<n)-1->i^^^i/2]

If explicit output is not required, this will do the job (45 chars):

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

^{Disclaimer: Very similar to the answer I provided here, just simplified to fit the output specified here.}

Answer 5

Jelly, 6 bytes

2*Ḷ^H$

Try it online!

How it works

2*Ḷ^H$  Main link. Argument: n

2*      Yield 2ⁿ.
  Ḷ     Unlength; yield [0, ..., 2ⁿ].
     $  Combine the two links to the left into a chain.
   ^H       XOR each k in the range with k/2.