Permutações de Reversão de Bit

28

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 n 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 n -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 é 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.
milhas
fonte
3
"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." Awww IntegerReverse[Range[2^#]-1,2,#]&,. (Eu não sei por que Mathematica precisa que built-in, mas eu acho que não é um estranho muito que Sunset...)
Martin Ender
@MartinEnder Nice find. Algum dia, pode ser que haja um componente interno para tudo no Mathematica, incluindo a geração de desafios aleatórios de código-golfe.
milhas
Podemos imprimir em 0vez de [0]ou precisa ser uma lista?
Dennis
@Dennis Bom ponto. Eu vou permitir isso, já que é importante que a saída represente uma permutação válida, independentemente do formato.
milhas
Retornar falso em vez de 0 seria aceitável?
Dennis

Respostas:

2

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.
Dennis
fonte
4

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

Adnan
fonte
Agradável! Bate o que eu tinha :)
Emigna
@Emigna Thanks! Qual era a sua versão então?
21416 Adnan
0)ïsF·D>«estava perto embora. Teve alguns problemas com o '0'.
Emigna
1
Bom uso de ¾. Vou ter que lembrar desse truque.
Emigna
1
@KevinCruijssen Para a entrada 0 , parece mais bonito ter a representação int de 0 e não a representação da string :). Fora isso, não há diferenças.
Adnan
4

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
Suever
fonte
4

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
milhas
fonte
4

Haskell , 40 37 bytes

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

Experimente online!

Obrigado a @Laikoni por três bytes!

Angs
fonte
3

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

Suever
fonte
3

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!

Dennis
fonte
Você pode fazer [0][n:]or.
Xnor
3

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)

R. Kap
fonte
Você pode salvar alguns bytes analisando um int a partir de args, em vez de ler em StdIn
Pavel
3

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

Martin Ender
fonte
3

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"
Ton Hospel
fonte
2

Pitão - 11 bytes

ushMByMGQ]0

Conjunto de Teste .

Maltysen
fonte
2

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]
Dendrobium
fonte
Que tal f=n=>n>0?(r=f(n-1).map(i=>i*2)).concat(r.map(i=>i+1)):[0]?
milhas
@miles Opa, não percebi que não preciso de um caso básico n==1, obrigado.
Dendrobium
2
Acho que consegui para raspar 2 bytes movendo a multiplicação por dois:f=(n,m=1)=>n?[...n=f(n-1,m+m),...n.map(i=>i+m)]:[0]
Neil
2

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

TheBikingViking
fonte
2
Este laços com a minha abordagem, mas golfiness não vai sobreviver a uma porta para Python 3.
Dennis
2

Dyalog APL , 12 bytes

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

2⊥⊖2⊥⍣¯12*⎕

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

Adão
fonte
(⍋,⍨)⍣⎕⊢0( ⎕io←0)
ngn 25/04
@ngn Isso não tem nada a ver com o meu algoritmo.
Adám 27/04
Eu pensei que era semelhante ao seu "outro método", mas ok, vou escrever uma resposta separada
ngn
2

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

ngn
fonte
1

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!

Dennis
fonte
1

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
Jakube
fonte
1

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)))))
NikoNyrh
fonte
1

Ruby, 57 bytes:

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

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

Titus
fonte
1

Ruby , 51 bytes

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

Experimente online!

Asone Tuhid
fonte
1

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.

Nwellnhof
fonte
1

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

Neil
fonte
ReferenceError: f não está definido
l4m2 25/05
1

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.

Bubbler
fonte
Na verdade, há um atalho em situação irregular para n2:Í
Oliver
1

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

ngn
fonte
0

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