28
\$\begingroup\$

Your goal is to create a function or a program to reverse the bits in a range of integers given an integer n. In other words, you want to find the bit-reversal permutation of a range of 2n items, zero-indexed. This is also the OEIS sequence A030109. This process is often used in computing Fast Fourier Transforms, such as the in-place Cooley-Tukey algorithm for FFT. There is also a challenge for computing the FFT for sequences where the length is a power of 2.

This process requires you to iterate over the range [0, 2n-1] and to convert each value to binary and reverse the bits in that value. You will be treating each value as a n-digit number in base 2 which means reversal will only occur among the last n bits.

For example, if n = 3, the range of integers is [0, 1, 2, 3, 4, 5, 6, 7]. These are

i  Regular  Bit-Reversed  j
0    000        000       0
1    001        100       4
2    010        010       2
3    011        110       6
4    100        001       1
5    101        101       5
6    110        011       3
7    111        111       7

where each index i is converted to an index j using bit-reversal. This means that the output is [0, 4, 2, 6, 1, 5, 3, 7].

The output for n from 0 thru 4 are

n    Bit-Reversed Permutation
0    [0]
1    [0, 1]
2    [0, 2, 1, 3]
3    [0, 4, 2, 6, 1, 5, 3, 7]

You may have noticed a pattern forming. Given n, you can take the previous sequence for n-1 and double it. Then concatenate that doubled list to the same double list but incremented by one. To show,

[0, 2, 1, 3] * 2 = [0, 4, 2, 6]
[0, 4, 2, 6] + 1 = [1, 5, 3, 7]
[0, 4, 2, 6] ⊕ [1, 5, 3, 7] = [0, 4, 2, 6, 1, 5, 3, 7]

where represents concatenation.

You can use either of the two methods above in order to form your solution. If you know a better way, you are free to use that too. Any method is fine as long as it outputs the correct results.

Rules

  • This is so the shortest solution wins.
  • Builtins that solve this challenge as a whole and builtins that compute the bit-reversal of a value are not allowed. This does not include builtins which perform binary conversion or other bitwise operations.
  • Your solution must be, at the least, valid for n from 0 to 31.
\$\endgroup\$
  • 3
    \$\begingroup\$ "Builtins that solve this challenge as a whole and builtins that compute the bit-reversal of a value are not allowed." Awww, IntegerReverse[Range[2^#]-1,2,#]&. (I don't know why Mathematica needs that built-in but I guess it's not a lot weirder than Sunset...) \$\endgroup\$ – Martin Ender Jun 20 '16 at 20:47
  • \$\begingroup\$ @MartinEnder Nice find. Someday, it might be that there will be a builtin for everything in Mathematica, including generating random code-golf challenges. \$\endgroup\$ – miles Jun 20 '16 at 20:57
  • \$\begingroup\$ Can we print 0 instead of [0] or does it have to be a list? \$\endgroup\$ – Dennis Jun 20 '16 at 21:03
  • \$\begingroup\$ @Dennis Good point. I'll allow it, since it's only important that the output represents a valid permutation regardless of format. \$\endgroup\$ – miles Jun 20 '16 at 21:10
  • \$\begingroup\$ Would returning false instead of 0 be acceptable? \$\endgroup\$ – Dennis Jun 20 '16 at 21:21

27 Answers 27

2
\$\begingroup\$

Jelly, 7 6 bytes

Ḥ;‘$$¡

Thanks to @EriktheOutgolfer for golfing off 1 byte!

Try it online!

How it works

Ḥ;‘$$¡  Main link. No arguments.
        Implicit argument / initial return value: 0

     ¡  Read an integer n from STDIN and call the link to the left n times.
    $   Combine the two links to the left into a monadic chain, to be called
        with argument A (initially 0, later an array).
Ḥ         Unhalve; yield 2A.
   $      Combine the two links to the left into a monadic chain, to be called
          with argument 2A.
  ‘         Increment; yield 2A + 1
 ;          Concatenate 2A and 2A + 1.
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 8 bytes

Code:

¾)IF·D>«

Explanation:

¾         # Constant for 0.
 )        # Wrap it up into an array.
  IF      # Do the following input times.
    ·     # Double every element.
     D    # Duplicate it.
      >   # Increment by 1.
       «  # Concatenate the first array.

Uses the CP-1252 encoding. Try it online!.

\$\endgroup\$
  • \$\begingroup\$ Nice one! Beats the one I had :) \$\endgroup\$ – Emigna Jun 20 '16 at 19:44
  • \$\begingroup\$ @Emigna Thanks! What was your version then? \$\endgroup\$ – Adnan Jun 20 '16 at 19:45
  • \$\begingroup\$ 0)ïsF·D>« was close though. Had some issues with the '0'. \$\endgroup\$ – Emigna Jun 20 '16 at 19:48
  • 1
    \$\begingroup\$ Nice usage of ¾. Gonna have to remember that trick. \$\endgroup\$ – Emigna Jun 20 '16 at 19:53
  • 1
    \$\begingroup\$ @KevinCruijssen For input 0, it looks prettier to have the int representation of 0 and not the string representation :). Other than that, there are no differences. \$\endgroup\$ – Adnan May 25 '18 at 12:40
4
\$\begingroup\$

MATL, 13 12 10 9 8 bytes

0i:"EtQh

Try it Online

Explanation

0       % Push number literal 0 to the stack
i:"     % Loop n times
    E   % Multiply by two
    t   % Duplicate
    Q   % Add one
    h   % Horizontally concatenate the result
        % Implicit end of loop, and implicitly display the result

For the sake of completeness, here was my old answer using the non-recursive approach (9 bytes).

W:qB2&PXB

Try it Online

Explanation

W       % Compute 2 to the power% ofImplicitly thegrab input (n) and compute 2^n
:       % Create an array from [1...2^n]
q       % Subtract 1 to get [0...(2^n - 1)]
B       % Convert to binary where each row is the binary representation of a number
2&P     % Flip this 2D array of binary numbers along the second dimension
XB      % Convert binary back to decimal
        % Implicitly display the result
\$\endgroup\$
4
\$\begingroup\$

J, 15 11 bytes

2&(*,1+*)0:

There is an alternative for 15 bytes that uses straight-forward binary conversion and reversal.

2|."1&.#:@i.@^]

Usage

   f =: 2&(*,1+*)0:
   f 0
0
   f 1
0 1
   f 2
0 2 1 3
   f 3
0 4 2 6 1 5 3 7
   f 4
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

Explanation

2&(*,1+*)0:  Input: n
         0:  The constant 0
2&(     )    Repeat n times starting with x = [0]
2      *       Multiply each in x by 2
     1+        Add 1 to each
    ,          Append that to
2  *           The list formed by multiplying each in x by 2
               Return that as the next value of x
             Return the final value of x
\$\endgroup\$
4
\$\begingroup\$

Jelly, 5 bytes

2ṗ’UḄ

Try it online!

-1 thanks to Dennis.

\$\endgroup\$
4
\$\begingroup\$

Haskell, 40 37 bytes

f 0=[0]
f a=[(*2),(+1).(*2)]<*>f(a-1)

Try it online!

Thanks to @Laikoni for three bytes!

\$\endgroup\$
3
\$\begingroup\$

Octave, 37 bytes

@(n)bin2dec(fliplr(dec2bin(0:2^n-1)))

Creates an anonymous function named ans that can simply be called with ans(n).

Online Demo

\$\endgroup\$
3
\$\begingroup\$

Python 2, 56 55 54 bytes

f=lambda n:[0][n:]or[i+j*2for i in 0,1for j in f(n-1)]

Test it on Ideone.

Thanks to @xnor for golfing off 1 byte!

\$\endgroup\$
  • \$\begingroup\$ You can do [0][n:]or. \$\endgroup\$ – xnor Jun 21 '16 at 1:47
3
\$\begingroup\$

Java, 422 419 bytes:

import java.util.*;class A{static int[]P(int n){int[]U=new int[(int)Math.pow(2,n)];for(int i=0;i<U.length;i++){String Q=new String(Integer.toBinaryString(i));if(Q.length()<n){Q=new String(new char[n-Q.length()]).replace("\0","0")+Q;}U[i]=Integer.parseInt(new StringBuilder(Q).reverse().toString(),2);}return U;}public static void main(String[]a){System.out.print(Arrays.toString(P(new Scanner(System.in).nextInt())));}}

Well, I finally learned Java for my second programming language, so I wanted to use my new skills to complete a simple challenge, and although it turned out very long, I am not disappointed. I am just glad I was able to complete a simple challenge in Java.

Try It Online! (Ideone)

\$\endgroup\$
  • \$\begingroup\$ You can save a few bytes parsing an int from args rather than reading from StdIn \$\endgroup\$ – Pavel Jan 5 '17 at 0:06
3
\$\begingroup\$

Mathematica, 56 33 bytes

Byte count assumes an ISO 8859-1 encoded source.

±0={0};±x_:=Join[y=±(x-1)2,y+1]

This uses the recursive definition to define a unary operator ±.

\$\endgroup\$
3
\$\begingroup\$

Perl, 46 45 bytes

Includes +1 for -p

Give input number on STDIN

#!/usr/bin/perl -p
map$F[@F]=($_*=2)+1,@F for(@F=0)..$_;$_="@F"
\$\endgroup\$
2
\$\begingroup\$

Pyth - 11 bytes

ushMByMGQ]0

Test Suite.

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

Javascript ES6, 65 53 51 bytes

f=(n,m=1)=>n?[...n=f(n-1,m+m),...n.map(i=>i+m)]:[0]

Uses the recursive double-increment-concat algorithm.

Example runs:

f(0) => [0]
f(1) => [0, 1]
f(2) => [0, 2, 1, 3]
f(4) => [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
\$\endgroup\$
  • \$\begingroup\$ How about f=n=>n>0?(r=f(n-1).map(i=>i*2)).concat(r.map(i=>i+1)):[0]? \$\endgroup\$ – miles Jun 20 '16 at 20:37
  • \$\begingroup\$ @miles Whoops, didn't realize I don't need a base case for n==1, thanks. \$\endgroup\$ – Dendrobium Jun 20 '16 at 20:43
  • 2
    \$\begingroup\$ I think I managed to shave off 2 bytes by moving the multiplication by two: f=(n,m=1)=>n?[...n=f(n-1,m+m),...n.map(i=>i+m)]:[0] \$\endgroup\$ – Neil Jun 20 '16 at 23:30
2
\$\begingroup\$

Python 3, 67 59 bytes

Thanks to @Dennis for -8 bytes

lambda n:[int(bin(i+2**n)[:1:-1],2)//2for i in range(2**n)]

We may as well have a (modified) straightforward implementation in Python, even if this is quite long.

An anonymous function that takes input by argument and returns the bit-reversed permutation as a list.

How it works

lambda n                 Anonymous function with input n
...for i in range(2**n)  Range from 0 to 2**n-1
bin(i+2**n)[:1:-1]       Convert i+2**n to binary string, giving 1 more digit than needed,
                         remove '0b' from start, and reverse
int(...,2)               Convert back to decimal
...//2                   The binary representation of the decimal value has one trailing
                         bit that is not required. This is removed by integer division by 2
:[...]                   Return as list

Try it on Ideone

\$\endgroup\$
  • 2
    \$\begingroup\$ This ties with my approach, but it golfiness won't survive a port to Python 3. \$\endgroup\$ – Dennis Jun 21 '16 at 0:07
2
\$\begingroup\$

Dyalog APL, 12 bytes

Requires ⎕IO←0 which is default on many systems.

2⊥⊖2⊥⍣¯1⍳2*⎕

2⊥ from-base-2 of

the flipped

2⊥⍣¯1 inverse of from-base-2 of

the first n integers, where n is

2* 2 to the power of

numeric input

TryAPL online!


For comparison, here is the other method:

(2∘×,1+2∘×)⍣⎕⊢0

( the function train...

2∘× two times (the argument)

, concatenated to

1+ one plus

2∘× two times (the argument)

)⍣ applied as many times as specified by

numeric input

on

0 zero

\$\endgroup\$
  • \$\begingroup\$ (⍋,⍨)⍣⎕⊢0 (⎕io←0) \$\endgroup\$ – ngn Apr 25 at 16:49
  • \$\begingroup\$ @ngn That has nothing to do with my algorithm. \$\endgroup\$ – Adám Apr 27 at 21:25
  • \$\begingroup\$ i thought it was similar to your "other method" but ok, i'll write a separate answer \$\endgroup\$ – ngn Apr 27 at 21:56
2
\$\begingroup\$

K (ngn/k), 11 8 bytes

2/|!2|&:

Try it online!

 x:3  / just for testing
 &x   / that many zeroes
0 0 0
 2|&x / max with 2
2 2 2
 !x#2 / binary words of length x, as a transposed matrix
(0 0 0 0 1 1 1 1
 0 0 1 1 0 0 1 1
 0 1 0 1 0 1 0 1)
 |!x#2 / reverse
(0 1 0 1 0 1 0 1
 0 0 1 1 0 0 1 1
 0 0 0 0 1 1 1 1)
 2/|!x#2 / base-2 decode the columns
0 4 2 6 1 5 3 7

& is the last verb in the composition so we need a : to force it to be monadic

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

Julia, 23 22 bytes

!n=n>0&&[t=2*!~-n;t+1]

Rather straightforward implementation of the process described in the challenge spec.

Try it online!

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

Pyth, 8 bytes

iR2_M^U2

Try it online: Demonstration or Test Suite

Explanation:

iR2_M^U2Q   implicit Q (=input number) at the end
     ^U2Q   generate all lists of zeros and ones of length Q in order
   _M       reverse each list
iR2         convert each list to a number
\$\endgroup\$
1
\$\begingroup\$

Clojure, 78 bytes

Just following the spec...

(defn f[n](if(= n 0)[0](let[F(map #(* 2 %)(f(dec n)))](concat F(map inc F)))))
\$\endgroup\$
1
\$\begingroup\$

Ruby, 57 bytes:

->n{(0...a=2**n).map{|x|("%b"%x+=a).reverse[0,n].to_i 2}}
\$\endgroup\$
1
\$\begingroup\$

PHP, 57 bytes

while($i<1<<$argv[1])echo bindec(strrev(decbin($i++))),_;

takes input from command line parameter, prints underscore-delimited values. Run with -nr.

recursive solution, 72 bytes

function p($n){$r=[$n];if($n)foreach($r=p($n-1)as$q)$r[]=$q+1;return$r;}

function takes integer, returns array

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

Ruby, 51 bytes

f=->n{n<1?[0]:(a=f[n-1].map{|i|i*2})+a.map(&:next)}

Try it online!

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

Perl 6, 42 bytes

{0,{$^p+^($_-$_/2+>lsb ++$)}...$_}o 1+<*-1

Try it online!

Incrementing an integer simply flips a sequence of least-significant bits, for example from xxxx0111 to xxxx1000. So the next bit-reversed index can be obtained from the previous one by flipping a sequence of most-significant bits. The XOR mask can be computed with m - (m >> (ctz(i) + 1)) for m = 2**n or m = 2**n-1.

Perl 6, 30 bytes

my&f={$_&&(^2 X+(f($_-1)X*2))}

Try it online!

Recursive approach.

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

JavaScript (Firefox 30-57), 48 bytes

f=n=>n?[for(x of[0,1])for(y of f(n-1))x+y+y]:[0]

Port of @Dennis♦'s Python 2 solution.

\$\endgroup\$
  • \$\begingroup\$ ReferenceError: f is not defined \$\endgroup\$ – l4m2 May 25 '18 at 10:39
1
\$\begingroup\$

Japt, 14 13 bytes

2pU Ǥw ú0U Í

Try it online!

Unpacked & How it works

2pU o_s2 w ú0U n2

2pU    2**n
o_     range(2**n).map(...)
s2       convert to binary string
w        reverse
ú0U      right-pad to length n, filling with '0'
n2       convert binary string to number

Straightforward implementation.

\$\endgroup\$
  • \$\begingroup\$ There's actually an undocumented shortcut for n2: Í \$\endgroup\$ – Oliver May 25 '18 at 15:35
1
\$\begingroup\$

APL (Dyalog Classic), 9 bytes

(⍋,⍨)⍣⎕⊢0

Try it online!

evaluated input

( )⍣⎕⊢0 apply the thing in ( ) that many times, starting with 0

,⍨ concatenate the current result with itself

indices of a sort-ascending permutation

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

x86, 31 bytes

Takes a sufficiently large int[] buffer in eax and n in ecx, and returns the buffer in eax.

Implements the concatenating algorithm given in the challenge statement. It may be possible to save bytes by incrementing the pointers by 4 instead of using array accesses directly, but lea/mov is already pretty short (3 bytes for 3 regs and a multiplier).

.section .text
.globl main
main:
        mov     $buf, %eax          # buf addr
        mov     $3, %ecx            # n 

start:
        xor     %ebx, %ebx
        mov     %ebx, (%eax)        # init buf[0] = 0 
        inc     %ebx                # x = 1

l1:
        mov     %ebx, %edi          
        dec     %edi                # i = x-1
        lea     (%eax,%ebx,4), %edx # buf+x 

l2:
        mov     (%eax,%edi,4), %esi # z = buf[i]
        sal     %esi                # z *= 2
        mov     %esi, (%eax,%edi,4) # buf[i] = z
        inc     %esi                # z += 1
        mov     %esi, (%edx,%edi,4) # buf[x+i] = z

        dec     %edi                # --i 
        jns     l2                  # do while (i >= 0)

        sal     %ebx                # x *= 2
        loop    l1                  # do while (--n)

        ret

.data
buf:    .space 256, -1

Hexdump:

00000507  31 db 89 18 43 89 df 4f  8d 14 98 8b 34 b8 d1 e6  |1...C..O....4...|
00000517  89 34 b8 46 89 34 ba 4f  79 f1 d1 e3 e2 e7 c3     |.4.F.4.Oy......|
\$\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.