# Traverse all numbers with only one bit flip per step

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

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)

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

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

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

# Jelly, 6 bytes (non-competing)

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.