4
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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)

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.