Soma dos poderes de 2

31

O desafio

Dada uma entrada inteira em xque 1 <= x <= 255, retorne os resultados de potências de dois que, quando somadas, dão x.

Exemplos

Dada a entrada:

86

Seu programa deve gerar:

64 16 4 2

Entrada:

240

Saída:

128 64 32 16

Entrada:

1

Saída:

1

Entrada:

64

Saída:

64

A saída pode conter zeros se a potência de dois não estiver presente na soma.

Por exemplo, a entrada 65pode ser emitida 0 64 0 0 0 0 0 1.

Pontuação

Isso é , então a resposta mais curta em cada idioma vence.

SpookyGengar
fonte
5
A lista precisa ser classificada da maior para a menor?
Adám 28/01
2
Podemos gerar alguns zeros redundantes?
Jonathan Allan
4
RE: "classificado da maior para a menor" por que adicionar uma restrição que não fazia parte do desafio e invalida a maioria das respostas existentes? (Também sobre o little-endian ?!) + ele invalida minha resposta do Python, pois os conjuntos não têm nenhuma ordem.
Jonathan Allan
5
@ JonathanAllan Eu removi a restrição. Vou ter isso em mente na próxima vez que postar outra pergunta - ainda sou bastante novo nisso. :)
SpookyGengar 28/01
6
Eu acho que você pode querer afirmar que qualquer poder de dois pode ser usado apenas uma vez. Caso contrário, alguém poderia emitir "1 1 1" para a entrada 3.
Black Owl Kai

Respostas:

38

JavaScript (ES6), 28 bytes

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

Experimente online!

Arnauld
fonte
9
Você é a única pessoa no mundo inteiro que pode me fazer votar positivamente em respostas em JavaScript!
sergiol 29/01
4
@ergiol, por que você normalmente não votaria em uma solução JS? Uma boa solução é uma boa solução, independentemente do idioma usado ou de quem a postou.
Shaggy
@ Shaggy Porque Arnauld parece a única pessoa a fazer essas soluções Javascript. Suas respostas são pura genialidade!
sergiol 29/01
3
@sergiol Obrigado pelo elogio, mas isso não é bem verdade. Sou regularmente derrotado por respostas mais inteligentes - e é disso que trata este site. ^^
Arnauld
@ Oliver Eu não tenho certeza. Parece que zeros à esquerda (antes de 128) são proibidos. Caso contrário, outra variante possível é f=n=>n&&f(n&~-n)+[,n&-n].
Arnauld
12

Pure Bash , 20

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

Experimente online!

Explicação

          {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
fonte
12

Gelatina , 4 bytes

-2, pois podemos gerar zeros no lugar de potências não utilizadas de 2 :)

Ḷ2*&

Experimente online!

Quão?

Ḷ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
fonte
11

Gelatina , 6 bytes

BUT’2*

Experimente online!

Explicação

MAS aqui está uma explicação (nota: eu assumi que só podemos produzir os poderes de 2 e nada mais):

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]

"Prova" de que funciona corretamente. A representação padrão de um número inteiro X na base 2 é uma lista {x1,x2,x3,,xn} , em que xi{0,1},i1,n¯ , de modo que:

X=Eu=1nxEu2n-Eu
Os índicesEumodo quexEu=0 0obviamente não têm contribuição, portanto, estamos interessados ​​apenas em encontrar aqueles quexEu=1. Como subtrairEudennão é conveniente (todos os poderes de dois têm expoentes da forman-Eu, ondeEu é qualquer índice de um1), em vez de encontrar os índices verdadeiros nesta lista, nós o revertemos e depois os encontramos "para trás" com UT. Agora que encontramos os índices corretos, tudo o que precisamos fazer é aumentar 2 para esses poderes.

Mr. Xcoder
fonte
1
"Somente ASCII" sorrateira lá ...
Erik o Outgolfer
1
@EriktheOutgolfer Eu acho BUT2*Hque funcionaria embora.
Sr. Xcoder 28/01
1
É bastante impressionante que isso funcione com uma entrada de 302231454903657293676544.
Michael Karas
9

Python , 35 bytes

lambda n:[n&2**i for i in range(8)]

Little-endian com zeros com potências não utilizadas de 2.

Experimente online!

Jonathan Allan
fonte
8

APL (Dyalog Extended) , 7 bytes SBCS

Função de prefixo tácito anônimo. Requer indexação baseada em 0 ( ⎕IO←0).

2*⍸⍢⌽⍤⊤

Experimente online!

2 dois
* elevado à potência de
 os Ɩ ndices onde a verdadeira
 enquanto
 invertida  da representação binária

Adão
fonte
8

Marreta 0.2, 3 bytes

⡔⡸⢣

Descomprime em {intLiteral[2],call[NumberExpand,2]} .

O Sledgehammer é um compressor para o código da Wolfram Language usando o Braille como uma página de código. O tamanho real das opções acima é de 2,75 bytes, mas devido às regras atuais da meta, o preenchimento do byte mais próximo é contado no tamanho do código.

lirtosiast
fonte
2
Hã! Linguagem simples e elegante, e todos os caracteres são realmente imprimíveis.
LegionMammal978 29/01
E agora não consigo tirar a música de Peter Gabriel da minha mente ...
Digital Trauma
8

05AB1E , 3 bytes

Ýo&

Porto de @JonathanAllan resposta Jelly , por isso não deixe de votar nele!

Contém zeros (incluindo cargas de zeros à direita).

Experimente online ou verifique todos os casos de teste .

Explicação:

Ý      # 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
fonte
1
... o que?! Nunca visto honestamente bitwise andusado em osabie. Agradável.
Magic Octopus Urn
@MagicOctopusUrn De fato, também não o uso com muita frequência. Não consigo encontrar nenhuma outra resposta em que eu usei &. XD Eu usei o Bitwise-XOR algumas vezes, como aqui ou aqui e o Bitwise-NOT uma vez aqui (que depois removi novamente depois de jogar mais ..). Eu uso Bitwise-AND, XOR, OR, NOT, SHIFT, etc. com bastante frequência em Java, mas em 05AB1E não tanto. :)
Kevin Cruijssen 29/01
8

Catholicon , 3 bytes

ṫĊŻ

Experimente online!

Explicação:

ṫ       Decompose         into the largest values where:
 Ċ               the input
  Ż       the bit count is truthy (equal to one)
Okx
fonte
Interessante! TIO'd: D
Jonathan Allan
Funciona com 302231454903657293676544. Legal.
Michael Karas
7

R , 27 23 bytes

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

Experimente online!

Código desenrolado e explicação:

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 graças a @Kirill L.
digEmAll
fonte
1
23 bytes com bits e.
Kirill L.
@KirillL .: brilhante!
digEmAll 29/01
7

C # (compilador interativo do Visual C #) , 29 bytes

Contém 5 caracteres não imprimíveis.

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

Explicação

//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)

Experimente online!

Modalidade de ignorância
fonte
Mas precisamos nos livrar de zeros, como n=>new int[8].Select((j,i)=>1<<i&n).Where(i=>i!=0)A parte anterior Whereé cinco bytes mais curta btw
polfosol ఠ_ఠ 29/01
@polfosolThe output may contain zeros
Jo King
2
@JoKing Ainda assim, n=>new int[8].Select((j,i)=>1<<i&n)tem 35 bytes e não precisaremos de sinalizadores e codificações de texto adicionais.
polfosol ఠ_ఠ 29/01
1
O uso de caracteres ascii de 0 a 7 deve ser mais curto, por exemplo, n=>"INSERT ASCII HERE".Select(a=>1<<a&n)mas eu estou em um dispositivo móvel que não pode exibir ou digitar não imprimíveis, então terei que esperar até chegar em casa para atualizar a resposta
Modalidade de ignorância
6

C # (compilador interativo do Visual C #) , 38 bytes

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

Experimente online!

dana
fonte
aw, fechar: P
ASCII-only
1
Falha de entradas 1, 2, 4, 8, 16, etc (o x>ydeve ser x>=yem vez disso).
Kevin Cruijssen 29/01
1
@ASCIIOnly - Estou lhe dizendo, o operador de faixa será ótimo :)
dana
@ Somente ASCII Enquanto isso, você pode usar o sinalizador /u:System.Linq.Enumerablee tentar fazer isso por 31 bytes
Modalidade de Ignorância
@EmbodimentofIgnorance sure. mas eu preferiria não listar o idioma como "C # /u:System.Linq.Enumerable": P
somente ASCII
5

05AB1E, 7 bytes

2вRƶ<oò

explicação:

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

Experimente online!

Jackson
fonte
Também funciona com a entrada de 302231454903657293676544
Michael Karas
5

C (clang) , 133 110 63 58 bytes

Solução de 58 bytes graças a @ceilingcat .

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

Experimente online!

um aracnídeo de pedra
fonte
No C89, você pode declarar como main(){}e o tipo de retorno assume como padrão int. O mesmo para variáveis ​​no escopo global. Além disso, pelo menos em implementações normais como clang, printf e scanf funcionam sem protótipos. Você recebe avisos, é claro, mas ainda é válido o C89 (talvez) ou pelo menos o K&R C para que eles sejam declarados implicitamente. Os tipos dos objetos C que você passa como args definem como eles são passados, portanto, a char*e int*funcionará apenas sem truncar ponteiros para 32 bits no x86-64 ou algo assim. (As promoções de argumento padrão acontecem, o mesmo que para as funções variáveis ​​que são de qualquer maneira.)
Peter Cordes
Ou isso pretende ser C11 válido sem comportamento indefinido? Nesse caso, proclame-o com orgulho. :) E BTW, escrever uma função que aceita uma matriz de saída como um argumento provavelmente seria menor. De qualquer forma, veja Dicas para jogar golfe em C
Peter Cordes
Você pode usar o bit &a bit para verificar se um pouco está definido. Like y&(1<<x)&&printf("%d ",1<<x);. Ou para não pular zeros, apenas printf("%d ", y&(1<<x)). Ou, em vez de contar as posições dos bits, use x=256e x>>=1para mudar a máscara. main(y){int x=256;for(scanf("%d",&y);x>>=1;)printf("%d ",y&x);}63 bytes Experimente online! clang até compilar isso com-std=c11
Peter Cordes
44 bytes
ceilingcat
4

MATL , 5 bytes

BPfqW

Experimente online!

Explicação

Considere a entrada 86como um exemplo.

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

Perl 6 , 16 12 bytes

-4 bytes graças a Jonathan Allan

*+&2**all ^8

Experimente online!

Retorna uma junção total com 8 elementos. Esta é uma maneira bastante não-padrão de retornar, mas geralmente, as junções podem atuar como listas ordenadas (pelo menos até a implementação do autotreading) e é possível extrair os valores de uma.

Explicação:

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

Japonês, 8 5 bytes

Æ&2pX

Tente

Æ&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

Alternativo

Sugerido por Oliver para evitar os 0s na saída usando a -mfflag.

N&2pU

Tente

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
fonte
1
Agradável. Você pode fazer N&2pUcom -mfpara evitar o 0s
Oliver
4

05AB1E , 9 bytes

Ýoʒ›}æʒOQ

Experimente online!


Isso também é correto para 6 bytes, mas não é concluído a tempo no TIO para 86:

05AB1E , 6 bytes

ÝoæʒOQ

Experimente online!

Urna de polvo mágico
fonte
1
Ambas as suas respostas produzem um conjunto vazio para 15, em vez de[1,2,4,8]
Kevin Cruijssen 29/01
1
@KevinCruijssen necessário 2**0, boa captura. Ýacabou L.
Magic Octopus Urn
1
Ah, eu conheço o sentimento. Também teve em Lvez de Ýprimeiro na minha resposta.
Kevin Cruijssen 29/01
4

K (oK) , 19 16 bytes

-3 bytes graças a ngn!

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

Experimente online!

oK não tem poweroperador, por isso preciso de uma função auxiliar {*/x#2}(copie 2 xvezes e reduza a lista resultante por multiplicação)

Galen Ivanov
fonte
você pode omitir o{ x}
NGN
@ngn Obrigado! Eu tentei e funcionou, mas não tinha certeza se é aceitável.
Galen Ivanov
4

Alquimista , 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

Experimente online! ou Teste todas as entradas!

Explicação

_->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
Somente ASCII
fonte
4

PHP ,41 39 bytes

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

Experimente online!

Ou 38 sem >>=operador divertido e PHP 5.6+:

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

Ou 36 com saída little-endian ("0 2 4 0 16 0 64 0"):

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

Na verdade, eu só queria usar o >>=operador, então estou aderindo ao 39 .

Testes:

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

TSQL, 43 39 bytes

Não é possível encontrar uma solução mais curta, então aqui está um loop padrão. -4 bytes graças a MickyT e KirillL

DECLARE @y int=255

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

Experimente

t-clausen.dk
fonte
usando o bit a bit e (&), você pode salvar alguns com o seguinte ,@ int=128s:print @y&@ set @/=2IF @>0GOTO s. Isso é sugerido por @KirillL para a resposta R
MickyT 31/01
@MickyT que funcionou como um encanto. Muito obrigado
t-clausen.dk
3

Python 2 , 43 40 bytes

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

Experimente online!

ovs
fonte
1
@ JonathanAllan isso definitivamente ajudou. Obrigado por me notificar.
ovs 28/01
1
... e a restrição foi levantada, então -1 byte :)
Jonathan Allan
3

C # (compilador interativo do Visual C #), 33 bytes

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

Porta da resposta JavaScript (ES6) de @Arnauld , por isso, certifique-se de que o vota!

Experimente online.

Explicação:

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
fonte