# 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
-
This is fundamentally the same question as codegolf.stackexchange.com/questions/4094 with a different winning criterion. – Peter Taylor Sep 15 '12 at 12:03

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)

-

C++ (188 bytes/chars):

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

-

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

-