Normalmente, descomponemos un número en dígitos binarios asignándolo con potencias de 2, con un coeficiente de
0
o1
para cada término:
25 = 1*16 + 1*8 + 0*4 + 0*2 + 1*1
La elección de
0
y1
es ... no muy binaria. Realizaremos la verdadera expansión binaria expandiéndonos con potencias de 2, pero con un coeficiente de1
o en su-1
lugar:
25 = 1*16 + 1*8 + 1*4 - 1*2 - 1*1
Ahora esto parece binario.
Dado cualquier número positivo, debería ser trivial ver que:
- Cada número impar tiene infinitas expansiones binarias verdaderas
- Cada número par no tiene expansiones binarias verdaderas
Por lo tanto, para que una verdadera expansión binaria esté bien definida, requerimos que la expansión sea la menor , es decir, con la longitud más corta.
Dado cualquier número entero positivo e impar n
, devuelve su verdadera expansión binaria, del dígito más significativo al dígito menos significativo (o en orden inverso).
Reglas:
- Como se trata de código de golf , debe intentar hacerlo en el menor recuento de bytes posible. Las construcciones están permitidas.
- Cualquier salida que pueda representar y enumerar los coeficientes es aceptable: una matriz, una cadena de coeficientes con separadores, etc.
- Se aplican lagunas de golf estándar.
- Su programa debería funcionar para valores dentro del tamaño entero estándar de su idioma.
Casos de prueba
25 -> [1,1,1,-1,-1]
47 -> [1,1,-1,1,1,1]
1 -> [1]
3 -> [1,1]
1234567 -> [1,1,-1,-1,1,-1,1,1,-1,1,-1,1,1,-1,1,-1,-1,-1,-1,1,1]
0
lugar del estado-1
de bajo voltaje. La persona que llama que recibe los bits sabe lo que significan. (Todavía es un ejercicio de manipulación de bits no trivial, ya que una rotación hacia la derecha solo funciona si tiene 32 bits significativos. Por ejemplo, un número de 5 bits necesita un ancho de rotación de 5)111-1-1
una salida válida para25
?Respuestas:
Japt , 6 bytes
Pruébalo en línea!
Explicación:
fuente
Pyth ,
1211 bytesPruébalo aquí!
¿Cómo?
En primer lugar, nos damos cuenta de que la tarea es simplemente "sustituir la
0
s en la escritura binaria con-1
sy desplazarse a la derecha por 1 lugar". - Eso es exactamente lo que debemos hacer! La conversión binaria nos da una lista de0
sy1
s. Todo lo que hay que hacer aquí es encontrar una manera de convertir golfy0
a-1
. El operador bit a bit|
(bitwise OR) es nuestro amigo. El mapa sobre la representación binaria cambió con|
y-1
. Si el número actual es0
, se convierte a-1
.fuente
Perl 6
Versión de cadena, 31 bytes
Pruébalo en línea!
Lista de versiones, 36 bytes
Pruébalo en línea!
fuente
JavaScript (ES6),
3534 bytesFragmento de prueba
Mostrar fragmento de código
fuente
Perl 6 , 72 bytes
Seguramente hay una mejor manera, pero esto es lo que tengo ...
Pruébalo en línea!
Explicación : Es una función que toma un argumento (
->$a
). Primero obtenemos el número de coeficientes necesarios ($a.base(2).chars
= número de caracteres en la representación de base 2), luego hacemos un producto cartesiano (X
) de tantos pares(1,-1)
. (Los[X]
medios: reduzca la siguiente lista conX
). Entonces obtenemos una lista de todas las combinaciones posibles de 1s y -1s. Luego filtramos (grep
) solo las listas que codifican el número dado$a
. Solo hay uno, por lo que obtenemos una lista de una lista con los coeficientes.El bloque grep hace esto: toma su argumento como una lista (
@^a
), lo invierte y lo comprime con una lista infinita0,1,2,...
utilizando el operador "desplazamiento de bit izquierdo"+<
. La compresión se detiene tan pronto como se agota la lista más corta (¡bueno para nosotros!) Luego sumamos todos los resultados y los comparamos con el número dado. Tuvimos que usar.reverse
porque el OP exige que los coeficientes estén en el orden de más significativo a menos significativo.fuente
Jalea , 5 bytes
Pruébalo en línea!
fuente
05AB1E ,
65 bytesPruébalo en línea!
fuente
D<
puede ser®
(®
es el valor predeterminado-1
).J, 11 bytes
Pruébalo en línea!
Gracias a @JosiahWinslow por el algoritmo.
¿Alguna idea sobre hacer la conversión más corta? Mis pensamientos son usar
!.
-fit (nvm, solo cambia la tolerancia de la conversión).Usar
{
-take es más largo por 1 personaje.fuente
Java 8, 101 bytes
Puerto de @Oliver Japt respuesta 's , con unos cuantos más bytes ..;)
Definitivamente se puede jugar al golf utilizando un enfoque matemático en lugar de este enfoque de cadena.
Explicación:
Pruébalo aquí.
fuente
R ,
908846 bytesPruébalo en línea!
Implementa el algoritmo de Oliver , pero devuelve los dígitos en orden inverso. Como estamos garantizados de que
n
nunca es par, el bit menos significativo (el primero) es siempre1
, por lo que lo eliminamos y agregamos una1
al final para simular la rotación en R. Gracias a Shaggy por ayudarme a arreglar mis matemáticas .Simplemente colocando
rev( )
las llamadas de función en el pie de página debería devolver los valores en el mismo orden.respuesta original, 88 bytes:
Función anónima; devuelve los valores en orden inverso con los nombres de columna adjuntos.
Pruébalo en línea!
Explicación:
fuente
from the most significant digit to the least significant digit (or in reversed order).
por lo tanto, esto debería ser perfectamente aceptable.25
, por ejemplo, sería[1,1,1,-1,-1]
o[-1,-1,1,1,1]
.2*bits - 1
lugar de1-2*bits
. Gracias.Perl 5 , 30 bytes
Código de 29 bytes, 1 byte para el
-p
interruptor.Pruébalo en línea!
fuente
CJam, 12 bytes
Un puerto de mi respuesta Golfscript.
fuente
Ruby ,
44 37 3332 bytesPruébalo en línea!
fuente
Golfscript,
141314 bytes-1 byte porque olvidé que
%
existía. +1 byte porque también olvidé que input es una cadena.fuente
{}
para convertirlo en un bloque. Los programas completos solo pueden obtener entradas como cadenas.{2base{.+(}%\}
por 15 bytes. Del mismo modo, su respuesta CJam.~
.