Seu objetivo é criar uma função ou um programa para reverter os bits em um intervalo de números inteiros, dado um número inteiro n . Em outras palavras, você deseja encontrar a permutação de reversão de bits de um intervalo de 2 ⁿ itens, indexados a zero. Essa também é a sequência OEIS A030109 . Esse processo geralmente é usado na computação de transformadas rápidas de Fourier, como o algoritmo Cooley-Tukey para FFT no local. Há também um desafio para calcular a FFT para sequências em que o comprimento é uma potência de 2.

Esse processo requer que você itere no intervalo [0, 2 ⁿ -1] e converta cada valor em binário e inverta os bits nesse valor. Você tratará cada valor como um número de n dígitos na base 2, o que significa que a reversão ocorrerá apenas entre os últimos n bits.

Por exemplo, se n = 3, o intervalo de números inteiros é [0, 1, 2, 3, 4, 5, 6, 7]. Esses são

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

onde cada índice i é convertido em um índice j usando inversão de bits. Isso significa que a saída é [0, 4, 2, 6, 1, 5, 3, 7].

A saída para n de 0 a 4 é

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

Você pode ter notado uma formação de padrão. Dado n , você pode pegar a sequência anterior para n -1 e dobrá-la. Em seguida, concatene essa lista dobrada para a mesma lista dupla, mas incrementada em uma. Mostrar,

[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]

onde ⊕representa concatenação.

Você pode usar um dos dois métodos acima para formar sua solução. Se você conhece uma maneira melhor, você também pode usá-la. Qualquer método é bom, desde que produza os resultados corretos.

Regras

• Isso é código-golfe, então a solução mais curta vence.
• Construções que resolvem esse desafio como um todo e construções que calculam a reversão de bits de um valor não são permitidas. Isso não inclui built-in que executam conversão binária ou outras operações bit a bit.
• Sua solução deve ser, no mínimo, válida para n de 0 a 31.

Geléia , 7 6 bytes

Ḥ;‘$$¡

Obrigado a @EriktheOutgolfer por jogar fora um byte!

Experimente online!

Como funciona

Ḥ;‘$$¡  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.

05AB1E , 8 bytes

Código:

¾)IF·D>«

Explicação:

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

Usa a codificação CP-1252 . Experimente online! .

MATL, 13 12 10 9 8 bytes

0i:"EtQh

Experimente Online

Explicação

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

Por uma questão de exaustividade, aqui estava minha resposta antiga, usando a abordagem não recursiva (9 bytes).

W:qB2&PXB

Experimente Online

Explicação

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

J, 15 11 bytes

2&(*,1+*)0:

Existe uma alternativa para 15 bytes que usa conversão e reversão binárias diretas.

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

Uso

   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

Explicação

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

Geléia , 5 bytes

2ṗ’UḄ

Experimente online!

-1 graças a Dennis .

Haskell , 40 37 bytes

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

Experimente online!

Obrigado a @Laikoni por três bytes!

Oitava, 37 bytes

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

Cria uma função anônima chamada ansque pode ser simplesmente chamada com ans(n).

Demo Online

Python 2, 56 55 54 bytes

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

Teste em Ideone .

Graças a @xnor por jogar fora um byte!

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())));}}

Bem, eu finalmente aprendi Java para minha segunda linguagem de programação, então eu queria usar minhas novas habilidades para concluir um desafio simples e, embora tenha sido muito longo, não estou desapontado. Estou feliz por ter conseguido concluir um desafio simples em Java.

Experimente Online! (Ideona)

Mathematica, 56 33 bytes

A contagem de bytes assume uma fonte codificada ISO 8859-1.

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

Isso usa a definição recursiva para definir um operador unário ±.

Perl, 46 45 bytes

Inclui +1 para -p

Forneça o número de entrada no STDIN

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

Pitão - 11 bytes

ushMByMGQ]0

Conjunto de Teste .

Javascript ES6, 65 53 51 bytes

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

Usa o algoritmo recursivo de incremento duplo-concat.

Exemplo é executado:

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]

Python 3, 67 59 bytes

Graças a @Dennis por -8 bytes

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

Também podemos ter uma implementação simples (modificada) em Python, mesmo que seja muito longa.

Uma função anônima que recebe entrada por argumento e retorna a permutação de bits reversos como uma lista.

Como funciona

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

Experimente no Ideone

Dyalog APL , 12 bytes

Requer ⎕IO←0qual é o padrão em muitos sistemas.

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

2⊥ da base 2 de

⊖ o capotou

2⊥⍣¯1 inverso da base 2 de

⍳os primeiros n números inteiros, onde n é

2* 2 ao poder de

⎕ entrada numérica

TryAPL online!

Para comparação, aqui está o outro método:

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

( o trem de função ...

 2∘× duas vezes (o argumento)

 , concatenado para

 1+ um mais

 2∘× duas vezes (o argumento)

)⍣ aplicado quantas vezes for especificado por

⎕ entrada numérica

⊢ em

0 zero

K (ngn / k) , 11 8 bytes

2/|!2|&:

Experimente 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

&é o último verbo na composição, por isso precisamos de um :para forçá-lo a ser monádico

Julia, 23 22 bytes

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

Implementação bastante direta do processo descrito na especificação do desafio.

Experimente online!

Pitão, 8 bytes

iR2_M^U2

Experimente on-line: demonstração ou Test Suite

Explicação:

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

Clojure, 78 bytes

Apenas seguindo as especificações ...

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

Ruby, 57 bytes:

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

PHP, 57 bytes

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

recebe entrada do parâmetro da linha de comando, imprime valores delimitados por sublinhado. Corra com -nr.

solução recursiva, 72 bytes

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

função leva inteiro, retorna matriz

Ruby , 51 bytes

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

Experimente online!

Perl 6 , 42 bytes

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

Experimente online!

Incrementar um número inteiro simplesmente inverte uma sequência de bits menos significativos, por exemplo, de xxxx0111para xxxx1000. Portanto, o próximo índice reverso de bits pode ser obtido a partir do anterior, invertendo uma sequência dos bits mais significativos. A máscara XOR pode ser calculado com m - (m >> (ctz(i) + 1))para m = 2**noum = 2**n-1 .

Perl 6 , 30 bytes

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

Experimente online!

Abordagem recursiva.

JavaScript (Firefox 30-57), 48 bytes

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

Porto da solução Python 2 de @ Dennis ♦.

Japonês , 14 13 bytes

2pU Ǥw ú0U Í

Experimente online!

Descompactado e como funciona

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

Implementação direta.

APL (Dyalog Classic) , 9 bytes

(⍋,⍨)⍣⎕⊢0

Experimente online!

⎕ entrada avaliada

( )⍣⎕⊢0aplique a coisa ( )várias vezes, começando com0

,⍨ concatenar o resultado atual consigo mesmo

⍋ índices de uma permutação crescente

x86, 31 bytes

Toma um suficientemente grande int[] bufferem eaxe n em ecx, e retorna o tampão emeax .

Implementa o algoritmo de concatenação fornecido na declaração de desafio. Pode ser possível salvar bytes incrementando os ponteiros em 4, em vez de usar os acessos à matriz diretamente, mas lea/ movjá é bastante curto (3 bytes para 3 regs e um multiplicador).

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