Su objetivo es crear una función o un programa para invertir los bits en un rango de enteros dado un entero n . En otras palabras, desea encontrar la permutación de inversión de bits de un rango de 2 n elementos, indexados a cero. Esta es también la secuencia OEIS A030109 . Este proceso a menudo se usa en la computación de transformaciones rápidas de Fourier, como el algoritmo Cooley-Tukey en el lugar para FFT. También hay un desafío para calcular la FFT para secuencias donde la longitud es una potencia de 2.
Este proceso requiere que itere sobre el rango [0, 2 n -1] y que convierta cada valor en binario e invierta los bits en ese valor. Tratará cada valor como un número de n dígitos en la base 2, lo que significa que la inversión solo ocurrirá entre los últimos n bits.
Por ejemplo, si n = 3, el rango de enteros es [0, 1, 2, 3, 4, 5, 6, 7]
. Estos son
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
donde cada índice i se convierte en un índice j usando la inversión de bits. Esto significa que la salida es [0, 4, 2, 6, 1, 5, 3, 7]
.
La salida para n de 0 a 4 son
n Bit-Reversed Permutation
0 [0]
1 [0, 1]
2 [0, 2, 1, 3]
3 [0, 4, 2, 6, 1, 5, 3, 7]
Es posible que haya notado que se forma un patrón. Dado n , puede tomar la secuencia anterior para n -1 y duplicarla. Luego concatena esa lista duplicada a la misma lista doble pero incrementada en una. 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]
donde ⊕
representa la concatenación.
Puede utilizar cualquiera de los dos métodos anteriores para formar su solución. Si conoce una mejor manera, también puede usarla. Cualquier método está bien siempre que genere los resultados correctos.
Reglas
- Este es el código de golf, por lo que gana la solución más corta.
- No se permiten las construcciones que resuelven este desafío como un todo y las construcciones que calculan la inversión de bits de un valor. Esto no incluye las incorporaciones que realizan la conversión binaria u otras operaciones bit a bit.
- Su solución debe ser, como mínimo, válida para n de 0 a 31.
IntegerReverse[Range[2^#]-1,2,#]&
. (No sé por qué Mathematica necesita esa función, pero supongo que no es mucho más raro queSunset
...)0
lugar de[0]
o tiene que ser una lista?Respuestas:
Gelatina ,
76 bytes¡Gracias a @EriktheOutgolfer por jugar golf en 1 byte!
Pruébalo en línea!
Cómo funciona
fuente
05AB1E , 8 bytes
Código:
Explicación:
Utiliza la codificación CP-1252 . Pruébalo en línea! .
fuente
0)ïsF·D>«
aunque estaba cerca. Tuve algunos problemas con el '0'.¾
. Voy a tener que recordar ese truco.MATL,
13121098 bytesPruébalo en línea
Explicación
En aras de la exhaustividad, aquí estaba mi vieja respuesta usando el enfoque no recursivo (9 bytes).
Pruébalo en línea
Explicación
fuente
J,
1511 bytesHay una alternativa para 15 bytes que usa conversión y reversión binarias directas.
Uso
Explicación
fuente
Jalea , 5 bytes
Pruébalo en línea!
-1 gracias a Dennis .
fuente
Haskell ,
4037 bytesPruébalo en línea!
¡Gracias a @Laikoni por tres bytes!
fuente
Octava, 37 bytes
Crea una función anónima llamada
ans
que simplemente se puede llamar conans(n)
.Demo en línea
fuente
Python 2,
565554 bytesPruébalo en Ideone .
¡Gracias a @xnor por jugar golf en 1 byte!
fuente
[0][n:]or
.Java,
422419 bytes:Bueno, finalmente aprendí Java para mi segundo lenguaje de programación, por lo que quería usar mis nuevas habilidades para completar un desafío simple, y aunque resultó ser muy largo, no estoy decepcionado. Me alegra haber podido completar un desafío simple en Java.
¡Pruébelo en línea! (Ideone)
fuente
Mathematica,
5633 bytesEl recuento de bytes supone una fuente codificada ISO 8859-1.
Esto utiliza la definición recursiva para definir un operador unario
±
.fuente
Perl,
4645 bytesIncluye +1 para
-p
Dar el número de entrada en STDIN
fuente
Pyth - 11 bytes
Test Suite .
fuente
Javascript ES6,
655351 bytesUtiliza el algoritmo recursivo de doble incremento-concat.
Ejecuciones de ejemplo:
fuente
f=n=>n>0?(r=f(n-1).map(i=>i*2)).concat(r.map(i=>i+1)):[0]
?n==1
, gracias.f=(n,m=1)=>n?[...n=f(n-1,m+m),...n.map(i=>i+m)]:[0]
Python 3,
6759 bytesGracias a @Dennis por -8 bytes
También podríamos tener una implementación directa (modificada) en Python, incluso si esto es bastante largo.
Una función anónima que toma datos por argumento y devuelve la permutación de bits invertidos como una lista.
Cómo funciona
Pruébalo en Ideone
fuente
Dyalog APL , 12 bytes
Requiere
⎕IO←0
cuál es el predeterminado en muchos sistemas.2⊥
desde-base-2 de⊖
el volteado2⊥⍣¯1
inversa de desde-base-2 de⍳
los primeros n enteros, donde n es2*
2 al poder de⎕
entrada numéricaTryAPL en línea!
A modo de comparación, aquí está el otro método:
(
el tren funcional ...2∘×
dos veces (el argumento),
concatenado a1+
uno más2∘×
dos veces (el argumento))⍣
aplicado tantas veces como lo especifique⎕
entrada numérica⊢
en0
cerofuente
(⍋,⍨)⍣⎕⊢0
(⎕io←0
)K (ngn / k) ,
118 bytesPruébalo en línea!
&
es el último verbo en la composición por lo que necesitamos una:
para forzarlo a ser monádicofuente
Julia,
2322 bytesImplementación bastante sencilla del proceso descrito en la especificación de desafío.
Pruébalo en línea!
fuente
Pyth, 8 bytes
Pruébelo en línea: Demostración o conjunto de pruebas
Explicación:
fuente
Clojure, 78 bytes
Solo siguiendo las especificaciones ...
fuente
Ruby, 57 bytes:
fuente
PHP, 57 bytes
toma datos del parámetro de línea de comando, imprime valores delimitados por guiones bajos Corre con
-nr
.solución recursiva, 72 bytes
la función toma un entero, devuelve una matriz
fuente
Ruby , 51 bytes
Pruébalo en línea!
fuente
Perl 6 , 42 bytes
Pruébalo en línea!
Incrementar un número entero simplemente voltea una secuencia de bits menos significativos, por ejemplo, de
xxxx0111
axxxx1000
. Por lo tanto, el siguiente índice de bits invertidos se puede obtener del anterior volteando una secuencia de bits más significativos. La máscara XOR se puede calcular conm - (m >> (ctz(i) + 1))
form = 2**n
om = 2**n-1
.Perl 6 , 30 bytes
Pruébalo en línea!
Enfoque recursivo.
fuente
JavaScript (Firefox 30-57), 48 bytes
Puerto de la solución Python 2 de @ Dennis ♦.
fuente
Japt ,
1413 bytesPruébalo en línea!
Desempaquetado y cómo funciona
Implementación directa.
fuente
n2
:Í
APL (Dyalog Classic) , 9 bytes
Pruébalo en línea!
⎕
entrada evaluada(
)⍣⎕⊢0
aplicar la cosa(
)
muchas veces, comenzando con0
,⍨
concatenar el resultado actual consigo mismo⍋
índices de una permutación ascendentefuente
x86, 31 bytes
Toma una suficientemente grande
int[] buffer
eneax
y n enecx
, y devuelve el búfer eneax
.Implementa el algoritmo de concatenación dado en la declaración de desafío. Puede ser posible guardar bytes incrementando los punteros en 4 en lugar de usar los accesos de matriz directamente, pero
lea
/mov
ya es bastante corto (3 bytes para 3 registros y un multiplicador).Hexdump:
fuente