Suma de poderes de 2

31

El reto

Dada una entrada entera xdonde 1 <= x <= 255, devuelve los resultados de potencias de dos que, cuando se suman, dan x.

Ejemplos

Dada la entrada:

86

Su programa debería generar:

64 16 4 2

Entrada:

240

Salida:

128 64 32 16

Entrada:

1

Salida:

1

Entrada:

64

Salida:

64

La salida puede contener ceros si la cierta potencia de dos no está presente en la suma.

Por ejemplo, la entrada 65puede salir 0 64 0 0 0 0 0 1.

Tanteo

Este es el , por lo que gana la respuesta más corta en cada idioma.

SpookyGengar
fuente
55
¿La lista tiene que ser ordenada de mayor a menor?
Adám
2
¿Podemos generar algunos ceros redundantes?
Jonathan Allan
44
RE: "ordenado de mayor a menor" ¿por qué agregar una restricción que no era parte del desafío e invalida la mayoría de las respuestas existentes? (¡¿Y qué pasa con little-endian ?!) + invalida mi respuesta de Python ya que los conjuntos no tienen ningún orden.
Jonathan Allan
55
@ JonathanAllan He eliminado la restricción. Lo tendré en cuenta la próxima vez que publique otra pregunta: todavía soy bastante nuevo en esto. :)
SpookyGengar
66
Creo que quizás quieras decir que cualquier poder de dos solo se puede usar una vez. De lo contrario, alguien podría generar "1 1 1" para la entrada 3.
Black Owl Kai

Respuestas:

38

JavaScript (ES6), 28 bytes

f=n=>n?[...f(n&~-n),n&-n]:[]

Pruébalo en línea!

Arnauld
fuente
99
¡Eres la única persona en todo el mundo que puede hacerme votar las respuestas de JavaScript!
sergiol
44
@sergiol, ¿por qué normalmente no votarías una solución JS? Una buena solución es una buena solución, independientemente del idioma utilizado o de quién la publicó.
Shaggy
@Shaggy Porque Arnauld parece ser la única persona que hace tales soluciones Javascript. ¡Sus respuestas son puro genio!
sergiol
3
@sergiol Gracias por el cumplido, pero eso no es del todo cierto. Regularmente me superan las respuestas más inteligentes, y de eso se trata este sitio. ^^
Arnauld
@ Oliver no estoy seguro. Parece que los ceros iniciales (antes de 128) están prohibidos. De lo contrario, otra variante posible es f=n=>n&&f(n&~-n)+[,n&-n].
Arnauld
12

Pure Bash , 20

echo $[2**{7..0}&$1]

Pruébalo en línea!

Explicación

          {7..0}     # Brace expansion: 7 6 5 4 3 2 1 0
       2**{7..0}     # Brace expansion: 128 64 32 16 8 4 2 1
       2**{7..0}&$1  # Brace expansion: 128&n 64&n 32&n 16&n 8&n 4&n 2&n 1&n (Bitwise AND)
     $[2**{7..0}&$1] # Arithmetic expansion
echo $[2**{7..0}&$1] # and output
Trauma digital
fuente
12

Jalea , 4 bytes

-2 ya que podemos generar ceros en lugar de potencias no utilizadas de 2 :)

Ḷ2*&

Pruébalo en línea!

¿Cómo?

Ḷ2*& - Link: integer, n         e.g. 10
Ḷ    - lowered range of n            [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9]
 2*  - two to the power of           [  1,  2,  4,  8, 16, 32, 64,128,256,512]
   & - bit-wise and                  [  0,  2,  0,  8,  0,  0,  0,  0,  0,  0]
Jonathan Allan
fuente
11

Jalea , 6 bytes

BUT’2*

Pruébalo en línea!

Explicación

PERO aquí hay una explicación (nota: asumí que solo podemos generar los poderes de 2 y nada más):

BUT’2* – Monadic link. Takes a number N as input. Example: 86
B      – Convert N to binary.                              [1, 0, 1, 0, 1, 1, 0]
 U     – Reverse.                                          [0, 1, 1, 0, 1, 0, 1]
  T    – Truthy indices.                                   [2, 3, 5, 7]
   ’   – Decrement.                                        [1, 2, 4, 6]
    2* – Raise 2 to that power.                            [2, 4, 16, 64]

"Prueba" de que funciona correctamente. La representación estándar de un entero X en la base 2 es una lista {x1,x2,x3,,xn} , donde xi{0,1},i1,n¯ , tal que:

X=i=1nxi2ni
Los índicesi tal quexi=0 obviamente no tienen contribución, por lo que solo estamos interesados ​​en encontrar aquellos quexi=1 . Desde restari den no es conveniente (las potencias de dos tienen exponentes de la formani , dondei es cualquier índice de un1 ), en lugar de encontrar los índices de verdad en esta lista, lo invertimos y luego los encontramos "al revés"UT. Ahora que hemos encontrado los índices correctos, todo lo que tenemos que hacer es elevar2 a esos poderes.

Sr. Xcoder
fuente
1
"ASCII-only" Sneaky there ...
Erik the Outgolfer
1
@EriktheOutgolfer, creo BUT2*Hque funcionaría.
Sr. Xcoder
1
Bastante impresionante que esto funcione con una entrada de 302231454903657293676544.
Michael Karas
8

APL (Dyalog Extended) , SBCS de 7 bytes

Función de prefijo tácito anónimo. Requiere indexación basada en 0 ( ⎕IO←0).

2*⍸⍢⌽⍤⊤

Pruébalo en línea!

2 dos
* elevado a la potencia de
 los Ɩ ndices donde la verdadera
 mientras que
 invierte
 de
 la representación binaria

Adán
fuente
8

Almádena 0.2, 3 bytes

⡔⡸⢣

Se descomprime en {intLiteral[2],call[NumberExpand,2]} .

Sledgehammer es un compresor para el código Wolfram Language que utiliza Braille como página de códigos. El tamaño real de lo anterior es 2.75 bytes, pero debido a las reglas actuales en meta, el relleno al byte más cercano se cuenta en el tamaño del código.

lirtosiast
fuente
2
Huh Lenguaje pequeño y ordenado, y todos los personajes son realmente imprimibles.
LegionMammal978
Y ahora no puedo sacar la canción de Peter Gabriel de mi mente ...
Digital Trauma
8

05AB1E , 3 bytes

Ýo&

Puerto de la respuesta Jelly @JonathanAllan , ¡así que asegúrate de votarlo!

Contiene ceros (incluidas las cargas de ceros finales).

Pruébalo en línea o verifique todos los casos de prueba .

Explicación:

Ý      # Create a list in the range [0, (implicit) input]
       #  i.e. 15 → [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
       #  i.e. 16 → [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
 o     # Take 2 to the power of each value
       #  → [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768]
       #  → [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536]
  &    # Bitwise-AND each value with the (implicit) input
       # 15 → [1,2,4,8,0,0,0,0,0,0,0,0,0,0,0,0]
       # 16 → [0,0,0,0,16,0,0,0,0,0,0,0,0,0,0,0,0]
       # (and output the result implicitly)
Kevin Cruijssen
fuente
1
... ¡¿qué?! Nunca honestamente visto bitwise andusado en osabie. Buena esa.
Urna de pulpo mágico
@MagicOctopusUrn De hecho, tampoco lo uso con mucha frecuencia. Ni siquiera puedo encontrar ninguna otra respuesta que haya usado &. XD He usado Bitwise-XOR un par de veces, como aquí o aquí, y Bitwise-NO una vez aquí (que luego eliminé nuevamente después de jugar más golf ...). Utilizo Bitwise-AND, XOR, OR, NOT, SHIFT, etc. con bastante frecuencia en Java, pero en 05AB1E no tanto. :)
Kevin Cruijssen
8

Catholicon , 3 bytes

ṫĊŻ

Pruébalo en línea!

Explicación:

ṫ       Decompose         into the largest values where:
 Ċ               the input
  Ż       the bit count is truthy (equal to one)
Okx
fuente
¡Interesante! TIO'd: D
Jonathan Allan
Funciona con 302231454903657293676544. Agradable.
Michael Karas
7

R , 27 23 bytes

bitwAnd(scan(),2^(7:0))

Pruébalo en línea!

Código desenrollado y explicación:

A = scan()         # get input number A from stdin
                   # e.g. A = 65

bitwAnd( A , 2^(7:0))  # bitwise AND between all powers of 2 : 2^7 ... 2^0 and A
                       # and implicitly print the result
                       # e.g. B = bitwAnd(65, c(128,64,32,16,8,4,2,1)) = c(0,64,0,0,0,0,0,1)
  • 4 bytes gracias a @Kirill L.
digEmAll
fuente
1
23 bytes con bit a bit y.
Kirill L.
@KirillL .: ¡genial!
digEmAll
7

C # (compilador interactivo de Visual C #) , 29 bytes

Contiene 5 caracteres no imprimibles.

n=>"€@ ".Select(a=>a&n)

Explicación

//Lambda taking one parameter 'n'
n=>
//String with ASCII characters 128, 64, 32, 16, 8, 4, 2, and 1
"€@ "
//Iterate through all the chars of the above string and transform them to
.Select(a=>
//A bitwise AND operation between the integer value of the current char and the input value
a&n)

Pruébalo en línea!

Encarnación de la ignorancia
fuente
Pero necesitamos deshacernos de los ceros, como n=>new int[8].Select((j,i)=>1<<i&n).Where(i=>i!=0)La parte anterior Wherees cinco bytes más corta por cierto
polfosol ఠ_ఠ
@polfosolThe output may contain zeros
Jo King
2
@JoKing Aún así, n=>new int[8].Select((j,i)=>1<<i&n)tiene 35 bytes de longitud y no necesitaremos marcas adicionales ni codificaciones de texto.
polfosol ఠ_ఠ
1
El uso de caracteres ascii 0-7 debería ser más corto, por ejemplo, n=>"INSERT ASCII HERE".Select(a=>1<<a&n)pero estoy en un dispositivo móvil que no puede mostrar o escribir no imprimibles, así que tendré que esperar hasta llegar a casa para actualizar la respuesta
Encarnación de la ignorancia
6

C # (compilador interactivo de Visual C #) , 38 bytes

x=>{for(int y=8;y-->0;Print(x&1<<y));}

Pruébalo en línea!

dana
fuente
aw, cierre: P
solo ASCII
1
Fails for inputs 1, 2, 4, 8, 16, etc. (the x>y should be x>=y instead).
Kevin Cruijssen
1
@ASCIIOnly - I'm telling you, the range operator is going to be sweet :)
dana
@ASCII-only Mean while, you can use the flag /u:System.Linq.Enumerable and try this for 31 bytes
Embodiment of Ignorance
@EmbodimentofIgnorance sure. but i'd prefer not to list language as "C# /u:System.Linq.Enumerable" :P
ASCII-only
5

05AB1E, 7 bytes

2вRƶ<oò

explanation:

2в        convert input to binary array
R         reverse array
ƶ<        multiply each item by it's index and subtract 1
oò        2^item then round down

Try it online!

Jackson
fuente
Also works with input of 302231454903657293676544
Michael Karas
5

C (clang), 133 110 63 58 bytes

58-byte solution thanks to @ceilingcat.

x=256;main(y){for(scanf("%d",&y);x/=2;)printf("%d ",y&x);}

Try it online!

a stone arachnid
fuente
In C89, you can declare like main(){} and the return type defaults to int. Same for variables at global scope. Also, at least on normal implementations like clang, printf and scanf work without prototypes. You get warnings of course, but it's still valid C89 (maybe) or at least K&R C for them to be implicitly declared. The types of the C objects you pass as args defines how they're passed, so a char* and int* will Just Work without truncating pointers to 32-bit on x86-64 or anything. (Default argument promotions happen, same as for variadic functions which they are anyway.)
Peter Cordes
Or is this aiming to be valid C11 with no undefined behaviour? If so, proudly proclaim it. :) And BTW, writing a function that takes an output array as an arg would probably be smaller. Anyway, see Tips for golfing in C
Peter Cordes
You can use bitwise & to check if a bit is set. Like y&(1<<x)&&printf("%d ",1<<x);. Or to not skip zeros, just printf("%d ", y&(1<<x)). Or instead of counting bit positions, use x=256 and x>>=1 to shift the mask. main(y){int x=256;for(scanf("%d",&y);x>>=1;)printf("%d ",y&x);} 63 bytes Try it online! clang will even compile that with -std=c11
Peter Cordes
44 bytes
ceilingcat
4

MATL, 5 bytes

BPfqW

Try it online!

Explanation

Consider input 86 as an example.

B    % Implicit input. Convert to binary (highest to lowest digits)
     % STACK: [1 0 1 0 1 1 0]
P    % Flip
     % STACK: [0 1 1 0 1 0 1]
f    % Find: indices of nonzeros (1-based)
     % STACK: [2 3 5 7]
q    % Subtract 1, element-wise
     % STACK: [1 2 4 6]
W    % Exponential with base 2, element-wise. Implicit display
     % STACK: [2 4 16 64]
Luis Mendo
fuente
4

Perl 6, 16 12 bytes

-4 bytes thanks to Jonathan Allan

*+&2**all ^8

Try it online!

Returns an All Junction with 8 elements. This is a rather non-standard way of returning, but generally, Junctions can act as ordered (at least until autothreading is implemented) lists and it is possible to extract the values from one.

Explanation:

*+&              # Bitwise AND the input with
   2**           # 2 raised to the power of
      all ^8     # All of the range 0 to 7
Jo King
fuente
4

Japt, 8 5 bytes

Æ&2pX

Try it

Æ&2pX     :Implicit input of integer U
Æ         :Map each X in the range [0,U)
 &        :  Bitwise AND of U with
  2pX     :  2 to the power of X

Alternative

Suggested by Oliver to avoid the 0s in the output using the -mf flag.

N&2pU

Try it

N&2pU     :Implicitly map each U in the range [0,input)
N         :The (singleton) array of inputs
 &        :Bitwise AND with
  2pX     :2 to the power of U
          :Implicitly filter and output
Shaggy
fuente
1
Nice one. You can do N&2pU with -mf to avoid the 0s
Oliver
4

05AB1E, 9 bytes

Ýoʒ›}æʒOQ

Try it online!


This is also correct for 6-bytes, but it doesn't complete in time on TIO for 86:

05AB1E, 6 bytes

ÝoæʒOQ

Try it online!

Magic Octopus Urn
fuente
1
Both your answers output an empty set for 15, instead of [1,2,4,8]
Kevin Cruijssen
1
@KevinCruijssen needed 2**0, nice catch. Ý over L.
Magic Octopus Urn
1
Ah, I know the feeling. Also had L instead of Ý at first in my answer.
Kevin Cruijssen
4

K (oK), 19 16 bytes

-3 bytes thanks to ngn!

{*/x#2}'&|(8#2)\

Try it online!

oK does not have power operator, that's why I need a helper function {*/x#2} (copy 2 x times and reduce the resulting list by multiplication)

Galen Ivanov
fuente
you can omit the { x}
ngn
@ngn Thanks! I tried it and it worked, but I wasn't sure it is acceptible.
Galen Ivanov
4

Alchemist, 125 bytes

_->In_x+128a+m
m+x+a->m+b
m+0x+a->n+a
m+0a->o+Out_b+Out_" "
n+b->n+x+c
n+0b+a->n+c
n+0a->p
o+b->o+c
o+0b->p
p+2c->p+a
p+0c->m

Try it online! or Test every input!

Explanation

_->In_x+128a+m           # Initialize universe with input, 128a (value to compare to) and m (state)
m+x+a->m+b               # If c has been halved, subtract min(a, x) from a and x and put its value into b
m+0x+a->n+a              # If x < a, continue to state n
m+0a->o+Out_b+Out_" "    # Else print and continue to state o
n+b->n+x+c               # Add min(a, x) (i.e. x) back to x, and add it to c (we're collecting a back into c)
n+0b+a->n+c              # Then, add the rest of a to c
n+0a->p                  # Then, go to state p
o+b->o+c                 # Add min(a, x) (i.e. a) to c - x _is_ greater than a and so contains it in its binary representation, so we're not adding back to x
o+0b->p                  # Then, go to state p
p+2c->p+a                # Halve c into a
p+0c->m                  # Then go to state m
ASCII-only
fuente
4

PHP, 41 39 bytes

for($c=256;$c>>=1;)echo$argv[1]&$c,' ';

Try it online!

Or 38 with no fun >>= operator and PHP 5.6+:

for($x=8;$x--;)echo$argv[1]&2**$x,' ';

Or 36 with little-endian ("0 2 4 0 16 0 64 0") output:

while($x<8)echo$argv[1]&2**$x++,' ';

Really I just wanted to use the >>= operator, so I'm sticking with the 39.

Tests:

$php pow2.php 86
0 64 0 16 0 4 2 0

$php pow2.php 240
128 64 32 16 0 0 0 0

$php pow2.php 1
0 0 0 0 0 0 0 1

$php pow2.php 64
0 64 0 0 0 0 0 0

$php pow2.php 65
0 64 0 0 0 0 0 1
640KB
fuente
4

TSQL, 43 39 bytes

Can't find a shorter fancy solution, so here is a standard loop. -4 bytes thanks to MickyT and KirillL

DECLARE @y int=255

,@ int=128s:PRINT @y&@ SET @/=2IF @>0GOTO s

Try it out

t-clausen.dk
fuente
using the bitwise and (&) you can save a few with the following ,@ int=128s:print @y&@ set @/=2IF @>0GOTO s. This is hinted by @KirillL for the R answer
MickyT
@MickyT that worked like a charm. Thanks a lot
t-clausen.dk
3

Python 2, 43 40 bytes

f=lambda n,p=1:n/p*[1]and f(n,p*2)+[p&n]

Try it online!

ovs
fuente
1
@JonathanAllan this definitely helped. Thanks for notifying me.
ovs
1
...and the restriction has been lifted, so -1 byte :)
Jonathan Allan
3

C# (Visual C# Interactive Compiler), 33 bytes

n=>{for(;n>0;n&=n-1)Print(n&-n);}

Port of @Arnauld's JavaScript (ES6) answer, so make sure to upvote him!

Try it online.

Explanation:

n=>{            // Method with integer parameter and no return-type
  for(;n>0      //  Continue looping as long as `n` is larger than 0:
      ;         //    After every iteration:
       n&=n-1)  //     Bitwise-AND `n` by `n-1`
    Print(      //   Print with trailing newline:
      n&-n);}   //    `n` bitwise-AND `-n`
Kevin Cruijssen
fuente