Bit-Reversal Permutations

Question

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 2ⁿ 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, 2ⁿ-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 code-golf 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.

"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...) — Martin Ender♦, Jun 20 '16 at 20:47
@MartinEnder Nice find. Someday, it might be that there will be a builtin for everything in Mathematica, including generating random code-golf challenges. — miles, Jun 20 '16 at 20:57
Can we print 0 instead of [0] or does it have to be a list? — Dennis♦, Jun 20 '16 at 21:03
@Dennis Good point. I'll allow it, since it's only important that the output represents a valid permutation regardless of format. — miles, Jun 20 '16 at 21:10

Dennis · Accepted Answer · 2018-05-11 15:21:54Z

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.

Suever · Answer 2 · 2016-06-21 00:31:43Z

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

miles · Answer 3 · 2016-10-21 21:46:52Z

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

Adnan · Answer 4 · 2016-06-20 19:52:15Z

up vote 3 down vote

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

edited Jun 20 '16 at 19:52

answered Jun 20 '16 at 19:42

Adnan

34.1k460217

Nice one! Beats the one I had :) – Emigna Jun 20 '16 at 19:44
@Emigna Thanks! What was your version then? – Adnan Jun 20 '16 at 19:45
0)ïsF·D>« was close though. Had some issues with the '0'. – Emigna Jun 20 '16 at 19:48
@Emigna Oh, I actually have that same issue now. Lemme fix that :p – Adnan Jun 20 '16 at 19:51
1

Nice usage of ¾. Gonna have to remember that trick. – Emigna Jun 20 '16 at 19:53

add a comment |

Suever · Answer 5 · 2016-06-20 20:21:15Z

up vote 3 down vote

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

answered Jun 20 '16 at 20:21

Suever

9,3821244

add a comment |

R. Kap · Answer 6 · 2016-06-21 04:26:15Z

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)

You can save a few bytes parsing an int from args rather than reading from StdIn — Pavel, Jan 5 '17 at 0:06

Martin Ender · Answer 7 · 2016-06-21 07:50:43Z

up vote 3 down vote

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

edited Jun 21 '16 at 7:50

answered Jun 20 '16 at 20:55

Martin Ender♦

164k54373851

add a comment |

Ton Hospel · Answer 8 · 2016-10-21 22:23:30Z

up vote 3 down vote

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"

edited Oct 21 '16 at 22:23

answered Oct 21 '16 at 22:15

Ton Hospel

13.7k11243

add a comment |

Maltysen · Answer 9 · 2016-06-20 19:45:48Z

up vote 2 down vote

Pyth - 11 bytes

ushMByMGQ]0

Test Suite.

answered Jun 20 '16 at 19:45

Maltysen

21k443113

add a comment |

Dendrobium · Answer 10 · 2016-06-20 23:54:57Z

up vote 2 down vote

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]

edited Jun 20 '16 at 23:54

answered Jun 20 '16 at 20:26

Dendrobium

1,912524

How about f=n=>n>0?(r=f(n-1).map(i=>i*2)).concat(r.map(i=>i+1)):[0]? – miles Jun 20 '16 at 20:37
@miles Whoops, didn't realize I don't need a base case for n==1, thanks. – Dendrobium Jun 20 '16 at 20:43
2

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] – Neil Jun 20 '16 at 23:30

add a comment |

TheBikingViking · Answer 11 · 2016-06-21 00:07:53Z

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

This ties with my approach, but it golfiness won't survive a port to Python 3. — Dennis♦, Jun 21 '16 at 0:07

Dennis · Answer 12 · 2016-06-21 01:51:34Z

up vote 2 down vote

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!

edited Jun 21 '16 at 1:51

answered Jun 20 '16 at 21:43

Dennis♦

177k32287710

You can do [0][n:]or. – xnor Jun 21 '16 at 1:47
That's clever. Thanks! – Dennis♦ Jun 21 '16 at 1:51

add a comment |

Adám · Answer 13 · 2017-01-04 20:02:55Z

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

Erik the Outgolfer · Answer 14 · 2018-05-11 14:27:14Z

up vote 2 down vote

Jelly, 5 bytes

2ṗ’UḄ

Try it online!

-1 thanks to Dennis.

edited yesterday

answered 2 days ago

Erik the Outgolfer

26.7k42490

add a comment |

Angs · Answer 15 · 2018-05-12 09:33:03Z

up vote 2 down vote

Haskell, 40 37 bytes

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

Try it online!

Thanks to @Laikoni for three bytes!

edited yesterday

answered yesterday

Angs

3,0901430

add a comment |

Dennis · Answer 16 · 2016-06-20 23:07:49Z

up vote 1 down vote

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!

edited Jun 20 '16 at 23:07

answered Jun 20 '16 at 21:22

Dennis♦

177k32287710

add a comment |

Jakube · Answer 17 · 2016-06-21 08:31:52Z

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

NikoNyrh · Answer 18 · 2016-12-25 22:47:15Z

up vote 1 down vote

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)))))

answered Dec 25 '16 at 22:47

NikoNyrh

2,08136

add a comment |

G B · Answer 19 · 2016-12-25 23:10:54Z

up vote 1 down vote

Ruby, 57 bytes:

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

edited Dec 25 '16 at 23:10

answered Dec 25 '16 at 23:00

G B

5,3001121

add a comment |

Titus · Answer 20 · 2017-01-04 23:42:07Z

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

Neil · Answer 21 · 2017-12-27 11:07:25Z

up vote 1 down vote

JavaScript (Firefox 30-57), 46 bytes

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

Port of @Dennis♦'s Python 2 solution.

edited Dec 27 '17 at 11:07

answered Jun 21 '16 at 7:38

Neil

69.3k740160

add a comment |

ngn · Answer 22 · 2018-05-12 22:57:14Z

K (ngn/k), 11 bytes

{2/'+|!x#2}

Try it online!

{ } is a lambda with argument x

explaination using the repl:

 x:3 / just for testing
 x#2 / x times repeat 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)
 +|!x#2 / transpose
(0 0 0
 1 0 0
 0 1 0
 1 1 0
 0 0 1
 1 0 1
 0 1 1
 1 1 1)
 2/'+|!x#2 / base-2 decode (2/) each (')
0 4 2 6 1 5 3 7

Asone Tuhid · Answer 23 · 2018-05-12 10:15:51Z

up vote 0 down vote

Ruby, 51 bytes

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

Try it online!

answered yesterday

Asone Tuhid

1,10317

add a comment |

nwellnhof · Answer 24 · 2018-05-12 11:18:44Z

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.

asked	1 year, 10 months ago
viewed	1,870 times
active	today

Stack Exchange Network

current community

your communities

more stack exchange communities

Bit-Reversal Permutations

Rules

24 Answers 24

Jelly, 7 6 bytes

How it works

MATL, 13 12 10 9 8 bytes

J, 15 11 bytes

Usage

Explanation

05AB1E, 8 bytes

Octave, 37 bytes

Java, 422 419 bytes:

Mathematica, 56 33 bytes

Perl, 46 45 bytes

Pyth - 11 bytes

Javascript ES6, 65 53 51 bytes

Python 3, 67 59 bytes

Python 2, 56 55 54 bytes

Dyalog APL, 12 bytes

Jelly, 5 bytes

Haskell, 40 37 bytes

Julia, 23 22 bytes

Pyth, 8 bytes

Explanation:

Clojure, 78 bytes

Ruby, 57 bytes:

PHP, 57 bytes

JavaScript (Firefox 30-57), 46 bytes

K (ngn/k), 11 bytes

Ruby, 51 bytes

Perl 6, 42 bytes

Perl 6, 30 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf array-manipulation binary permutations bitwise or ask your own question.

Linked

Hot Network Questions

Bit-Reversal Permutations

Rules

24 Answers 24

Jelly, 7 6 bytes

How it works

MATL, 13 12 10 9 8 bytes

J, 15 11 bytes

Usage

Explanation

05AB1E, 8 bytes

Octave, 37 bytes

Java, 422 419 bytes:

Mathematica, 56 33 bytes

Perl, 46 45 bytes

Pyth - 11 bytes

Javascript ES6, 65 53 51 bytes

Python 3, 67 59 bytes

Python 2, 56 55 54 bytes

Dyalog APL, 12 bytes

Jelly, 5 bytes

Haskell, 40 37 bytes

Julia, 23 22 bytes

Pyth, 8 bytes

Explanation:

Clojure, 78 bytes

Ruby, 57 bytes:

PHP, 57 bytes

JavaScript (Firefox 30-57), 46 bytes

K (ngn/k), 11 bytes

Ruby, 51 bytes

Perl 6, 42 bytes

Perl 6, 30 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf array-manipulation binary permutations bitwise or ask your own question.

Linked

Related

Hot Network Questions