[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](https://en.wikipedia.org/wiki/Bit-reversal_permutation) of a range of \$2^n\$ items, zero-indexed. This is also the OEIS sequence [A030109](https://oeis.org/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](https://codegolf.stackexchange.com/questions/12420/too-fast-too-fourier-fft-code-golf) 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^n-1]\$, 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](/questions/tagged/code-golf "show questions tagged '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.
  
[Answer]
# [Haskell](https://www.haskell.org/), ~~40~~ 37 bytes
```
f 0=[0]
f a=[(*2),(+1).(*2)]<*>f(a-1)
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/P03BwDbaIJYrTSHRNlpDy0hTR0PbUFMPxIq10bJL00jUNdT8n5uYmadgq5CbWOAbr6BRUJSZV6KXpqkQbahjpGOsYxL7HwA "Haskell – Try It Online")
Thanks to @Laikoni for three bytes!
[Answer]
# [05AB1E](http://github.com/Adriandmen/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!](http://05ab1e.tryitonline.net/#code=wr4pSUbCt0Q-wqs&input=Mw).
[Answer]
# MATL, ~~13~~ ~~12~~ ~~10~~ ~~9~~ 8 bytes
```
0i:"EtQh
```
[**Try it Online**](http://matl.tryitonline.net/#code=MGk6IkV0UWg&input=Mw)
**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**](http://matl.tryitonline.net/#code=VzpxQjImUFhC&input=Mw)
**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
```
[Answer]
# 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
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 5 bytes
```
2ṗ’UḄ
```
[Try it online!](https://tio.run/##y0rNyan8/9/o4c7pjxpmhj7c0fL//39jAA "Jelly – Try It Online")
-1 thanks to [Dennis](https://codegolf.stackexchange.com/users/12012/dennis).
[Answer]
# 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**](http://ideone.com/1jopEJ)
[Answer]
# 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](http://ideone.com/Smw0nC).
*Thanks to @xnor for golfing off 1 byte!*
[Answer]
# 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)](http://ideone.com/fy1xGj)
[Answer]
## 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 `±`.
[Answer]
# 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"
```
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), ~~7~~ 6 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
Ḥ;‘$$¡
```
*Thanks to @EriktheOutgolfer for golfing off 1 byte!*
[Try it online!](https://tio.run/##y0rNyan8///hjiXWjxpmqKgcWvj/vzEA "Jelly – 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.
```
[Answer]
# Pyth - 11 bytes
```
ushMByMGQ]0
```
[Test Suite](http://pyth.herokuapp.com/?code=ushMByMGQ%5D0&test_suite=1&test_suite_input=0%0A1%0A2%0A3&debug=0).
[Answer]
# 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]
```
[Answer]
# 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](https://ideone.com/Atgesv)
[Answer]
# [Dyalog APL](http://goo.gl/9KrKoM), 12 [bytes](http://meta.codegolf.stackexchange.com/a/9429/43319)
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!](http://tryapl.org/?a=%u2395IO%u21900%20%u22C4%20%u2206%u21900%20%u22C4%202%u22A5%u22962%u22A5%u2363%AF1%u23732*%u2206%20%u22C4%20%u2206%u21901%20%u22C4%202%u22A5%u22962%u22A5%u2363%AF1%u23732*%u2206%20%u22C4%20%u2206%u21902%20%u22C4%202%u22A5%u22962%u22A5%u2363%AF1%u23732*%u2206%20%u22C4%20%u2206%u21903%20%u22C4%202%u22A5%u22962%u22A5%u2363%AF1%u23732*%u2206&run)
---
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
[Answer]
# [Ruby](https://www.ruby-lang.org/), 51 bytes
```
f=->n{n<1?[0]:(a=f[n-1].map{|i|i*2})+a.map(&:next)}
```
[Try it online!](https://tio.run/##KypNqvz/P81W1y6vOs/G0D7aINZKI9E2LTpP1zBWLzexoLomsyZTy6hWUzsRxNVQs8pLrSjRrP1voleSmZtarJCSrwBUwsVZUFpSrKCkXJ1Zq6Brp6BcnRadGVurxJWal/IfAA "Ruby – Try It Online")
[Answer]
# [K (ngn/k)](https://gitlab.com/n9n/k), ~~11~~ 8 bytes
```
2/|!2|&:
```
[Try it online!](https://tio.run/##y9bNS8/7/z/Nyki/RtGoRs3qf5q6obai6X8A "K (ngn/k) – 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
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~57 47~~ 39 bytes
```
->n{[*0...2**n].sort_by{|a|a.digits 2}}
```
[Try it online!](https://tio.run/##KypNqvyfZvtf1y6vOlrLQE9Pz0hLKy9Wrzi/qCQ@qbK6JrEmUS8lMz2zpFjBqLb2f4FCWrRRLBeIMoZQJrH/AQ "Ruby – Try It Online")
3 years later, 18 bytes golfed.
[Answer]
# 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!](http://julia.tryitonline.net/#code=IW49bj4wJiZbdD0yKiF-LW47dCsxXQoKZm9yIG4gaW4gMDozCiAgICBAcHJpbnRmKCIlZCAtPiAlc1xuIiwgbiwgIW4pCmVuZA&input=)
[Answer]
# Pyth, 8 bytes
```
iR2_M^U2
```
Try it online: [Demonstration](http://pyth.herokuapp.com/?code=iR2_M%5EU2&input=3&test_suite_input=0%0A1%0A2%0A3&debug=0) or [Test Suite](http://pyth.herokuapp.com/?code=iR2_M%5EU2&input=3&test_suite=1&test_suite_input=0%0A1%0A2%0A3&debug=0)
### 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
```
[Answer]
## 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)))))
```
[Answer]
# 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
[Answer]
## 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.
[Answer]
# [Japt](https://github.com/ETHproductions/japt), ~~14~~ 13 bytes
```
2pU Ç¤w ú0U Í
```
[Try it online!](https://ethproductions.github.io/japt/?v=2.0a0&code=MnBVIMekdyD6MFUgzQ==&input=LW1SClsxLCAyLCAzLCA0LCA1XQ==)
### 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.
[Answer]
# [APL (Dyalog Classic)](https://www.dyalog.com/), 9 bytes
```
(⍋,⍨)⍣⎕⊢0
```
[Try it online!](https://tio.run/##HYw9CsJAEIX7PcV2o5DAbuIPWHiXJWEluBjZpBFJJxoTN9hYWqiNFxAh4GXmInGSYt68x/dm1Nb48U6ZdOVHRmVZEnXY3JIUj1fBsDzpboSu9tC9x@hehLB6io4AQ9dIvPyg0NTdgwcE@7GA7gNYVkS/lCMLGji6e25VrDf@koTl/Q318PywZDW6dgHpGrA@gFaJoR8tYVt0gudcMNkrlywYdsAlD1k4@AmlGeUpD/mc@X8 "APL (Dyalog Classic) – 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
[Answer]
# [Perl 6](https://github.com/nxadm/rakudo-pkg), 25 bytes
```
{[X+] 0,|(0 X(2 X**^$_))}
```
[Try it online!](https://tio.run/##K0gtyjH7n1upoJamYPu/OjpCO1bBQKdGw0AhQsNIIUJLK04lXlOz9n9BaYlCmgaQbWenl5ZboqGuamBUoa6pkJZfpBBnYf0fAA "Perl 6 – Try It Online")
# [Perl 6](https://github.com/nxadm/rakudo-pkg), 42 bytes
```
{0,{$^p+^($_-$_/2+>lsb ++$)}...$_}o 1+<*-1
```
[Try it online!](https://tio.run/##K0gtyjH7n1upoJamYPu/2kCnWiWuQDtOQyVeVyVe30jbLqc4SUFbW0WzVk9PTyW@Nl/BUNtGS9fwvzVXQWmJQhpQoaadnV5abomGuqqBUYW6pkJafpFCnIX1fwA "Perl 6 – 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`.
[Answer]
# TI-BASIC, 26 bytes
```
Input A:{0:For(I,1,A:2Ans:augment(Ans,1+Ans:End:Ans
```
Prompts the user to input *n*.
Outputs the bit-reversal permutation as is specified in the challenge.
**Explanation:**
```
Input A                  ;prompt the user for "n".  store the input into A
{0                       ;leave {0} in Ans
For(I,1,A                ;loop A times
2Ans                     ;double Ans and leave the result in Ans
augment(Ans,1+Ans        ;add 1 to Ans and append it to the previous result
                         ;  leave the new result in Ans 
End                      ;loop end
Ans                      ;leave Ans in Ans
                         ;implicit print of Ans
```
**Examples:**
```
prgmCDGF25
?1
           {0 1}
prgmCDGF25
?3
{0 4 2 6 1 5 3 7}
```
**Note:** TI-BASIC is a tokenized language. Character count does *not* equal byte count.
[Answer]
# [Desmos](https://desmos.com/calculator), 71 bytes
```
f(n)=[total(mod(floor(2i/2^{[1...n]}),2)2^{[n-1...0]})fori=[0...2^n-1]]
```
Straightforward implementation of the challenge (convert to binary, then reverse), but probably optimizable with actions...
[Try It On Desmos!](https://www.desmos.com/calculator/icphgaiuxq)
[Try It On Desmos! - Prettified](https://www.desmos.com/calculator/thym4i9rks)
[Answer]
# [Factor](https://factorcode.org/), 43 bytes
```
[ { 0 } [ 2 v*n dup 1 v+n append ] repeat ]
```
[Try it online!](https://tio.run/##JcsxDoJAEEbhnlP8tRqCxkoPYGxsjNWGYoQRiTCMswOJGs@@amxfvnehygdLp@P@sNugJ7/mE/9SxI1NuEPk@8hScUTDwkZd@yRvB4lQY/eHWiv@P42k@bptlhVYI9DiXKaAFwq8EbDCNBPUo2KJaS4gVZYaJYyVyVGmnhR5@gA "Factor – Try It Online")
[Answer]
# 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......|
```
]