Somme des pouvoirs de 2

31

Le défi

Étant donné une entrée entière xoù 1 <= x <= 255, renvoyer les résultats de puissances de deux qui, une fois sommées, donnent x.

Exemples

Compte tenu de l'entrée:

86

Votre programme devrait produire:

64 16 4 2

Contribution:

240

Sortie:

128 64 32 16

Contribution:

1

Sortie:

1

Contribution:

64

Sortie:

64

La sortie peut contenir des zéros si la puissance certaine de deux n'est pas présente dans la somme.

Par exemple, saisissez 65 peut sortir 0 64 0 0 0 0 0 1.

Notation

C'est le golf de code , donc la réponse la plus courte dans chaque langue l'emporte.

code-golf binary code-golf sequence integer chess code-golf number arithmetic matrix code-golf code-golf combinatorics grid set-partitions code-golf array-manipulation graph-theory code-golf number code-golf string decision-problem code-golf matrix cellular-automata 3d code-challenge restricted-source printable-ascii code-golf board-game code-golf geometry grid code-golf word-puzzle code-golf matrix sorting code-golf code-golf string decision-problem code-golf matrix cellular-automata code-golf decision-problem code-golf math number arithmetic restricted-source code-golf code-golf number integer matrix code-golf date code-golf matrix code-golf sequence combinatorics chemistry code-golf array-manipulation popularity-contest code-golf code-golf natural-language code-golf number integer sorting substitution code-golf string number date encode code-golf decision-problem code-golf string subsequence code-golf string alphabet code-golf SpookyGengar
la source
5
La liste doit-elle être triée du plus haut au plus bas?
mars
2
Pouvons-nous produire des zéros redondants?
Jonathan Allan
4
RE: "trié du plus haut au plus bas" pourquoi ajouter une restriction qui ne faisait pas partie du défi et invalide la plupart des réponses existantes? (Et qu'en est-il du petit-boutien?!) + Cela invalide ma réponse Python car les ensembles n'ont pas d'ordre.
Jonathan Allan
5
@JonathanAllan J'ai supprimé la restriction. Je garderai cela à l'esprit la prochaine fois que je posterai une autre question - je suis encore assez nouveau dans ce domaine. :)
SpookyGengar
6
Je pense que vous voudrez peut-être déclarer que tout pouvoir de deux ne peut être utilisé qu'une seule fois. Sinon, quelqu'un pourrait sortir "1 1 1" pour l'entrée 3.
Black Owl Kai

Réponses:

38

JavaScript (ES6), 28 octets

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

Essayez-le en ligne!

Arnauld
la source
9
Vous êtes la seule personne au monde qui peut me faire voter contre les réponses JavaScript!
sergiol
4
@sergiol, pourquoi ne voteriez-vous pas normalement pour une solution JS? Une bonne solution est une bonne solution quelle que soit la langue utilisée ou qui l'a publiée.
Shaggy
@Shaggy Parce qu'Arnauld semble la seule personne à faire de telles solutions Javascript. Ses réponses sont du pur génie!
sergiol
3
@sergiol Merci pour le compliment, mais ce n'est pas tout à fait vrai. Je suis régulièrement dépassé par des réponses plus intelligentes - et c'est ce que propose ce site. ^^
Arnauld
@Oliver, je ne suis pas sûr. Il semble que les zéros non significatifs (avant 128) soient interdits. Sinon, une autre variante possible est f=n=>n&&f(n&~-n)+[,n&-n].
Arnauld
12

Pure Bash , 20

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

Essayez-le en ligne!

Explication

          {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 numérique
la source
12

Gelée , 4 octets

-2 puisque nous pouvons produire des zéros à la place des puissances inutilisées de 2 :)

Ḷ2*&

Essayez-le en ligne!

Comment?

Ḷ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
la source
11

Gelée , 6 octets

BUT’2*

Essayez-le en ligne!

Explication

MAIS voici une explication (note: j'avais supposé que nous ne pouvions sortir que les puissances de 2 elles-mêmes et rien d'autre):

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]

"Preuve" que cela fonctionne correctement. La représentation standard d'un entier X dans la base 2 est une liste {x1,x2,x3,⋯,xn} , où xi∈{0,1},∀i∈1,n¯ , tel que:

X=∑i=1nxi⋅2n−i
Les indicesi tels quexi=0 n'ont évidemment aucune contribution, nous ne sommes donc intéressés qu'à trouver ceux tels quexi=1 . Puisque soustrairei den n'est pas commode (les puissances de deux ont toutes des exposants de la formen−i , oùi est n'importe quel indice d'un1), au lieu de trouver les indices véridiques dans cette liste, nous l'inversons puis les retrouvons "à l'envers" avec UT. Maintenant que nous avons trouvé les bons indices, tout ce que nous avons à faire est d'élever 2 à ces pouvoirs.

M. Xcoder
la source
1
"ASCII uniquement" Sneaky ’là-bas ...
Erik the Outgolfer
1
@EriktheOutgolfer, je suppose que BUT2*Hcela fonctionnerait cependant.
M. Xcoder
1
Assez impressionnant que cela fonctionne avec une entrée de 302231454903657293676544.
Michael Karas
8

APL (Dyalog Extended) , SBCS 7 octets

Fonction de préfixe tacite anonyme. Nécessite une indexation basée sur 0 ( ⎕IO←0).

2*⍸⍢⌽⍤⊤

Essayez-le en ligne!

2 deux
* élevé à la puissance de
⍸ la ɩ ndices où vrai
⍢ alors
⌽ inversé
⍤ de
⊤ la représentation binaire

Adam
la source
8

Sledgehammer 0,2, 3 octets

⡔⡸⢣

Se décompresse en {intLiteral[2],call[NumberExpand,2]} .

Sledgehammer est un compresseur pour le code Wolfram Language utilisant le braille comme page de codes. La taille réelle de ce qui précède est de 2,75 octets, mais en raison des règles actuelles sur les méta, le remplissage à l'octet le plus proche est compté dans la taille du code.

lirtosiast
la source
2
Hein! Petite langue soignée, et tous les personnages sont en fait imprimables.
LegionMammal978
Et maintenant, je ne peux plus sortir la chanson de Peter Gabriel de mon esprit ...
Digital Trauma
8

05AB1E , 3 octets

Ýo&

Port de @JonathanAllan 's Jelly answer , alors assurez-vous de lui donner un vote positif!

Contient des zéros (y compris des charges de zéros de fin).

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

Ý      # 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
la source
1
... quoi?! Jamais vu honnêtement bitwise andutilisé en osabie. Joli.
Urne de poulpe magique le
@MagicOctopusUrn Je ne l'utilise d'ailleurs pas très souvent. Je ne trouve même pas d'autre réponse dans laquelle j'ai utilisé &. XD J'ai utilisé Bitwise-XOR plusieurs fois, comme ici ou ici et Bitwise-NOT une fois ici (que j'ai retiré plus tard après avoir joué plus loin ..). J'utilise Bitwise-AND, XOR, OR, NOT, SHIFT, etc. assez souvent en Java, mais en 05AB1E pas tellement. :)
Kevin Cruijssen
8

Catholicon , 3 octets

ṫĊŻ

Essayez-le en ligne!

Explication:

ṫ       Decompose         into the largest values where:
 Ċ               the input
  Ż       the bit count is truthy (equal to one)
Okx
la source
Intéressant! Obtenez TIO'd: D
Jonathan Allan
Fonctionne avec 302231454903657293676544. Nice.
Michael Karas
7

R , 27 23 octets

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

Essayez-le en ligne!

Code déroulé et explication:

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 octets grâce à @Kirill L.
digEmAll
la source
1
23 octets avec et au niveau du bit.
Kirill L.
@KirillL .: génial!
digEmAll
7

C # (Visual C # Interactive Compiler) , 29 octets

Contient 5 caractères non imprimables.

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

Explication

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

Essayez-le en ligne!

Incarnation de l'ignorance
la source
Mais nous devons nous débarrasser des zéros, comme n=>new int[8].Select((j,i)=>1<<i&n).Where(i=>i!=0)la partie précédente Whereest plus courte de cinq octets
polfosol os_ఠ
@polfosolThe output may contain zeros
Jo King
2
@JoKing Still, n=>new int[8].Select((j,i)=>1<<i&n)fait 35 octets de long et nous n'aurons pas besoin de drapeaux et d'encodages de texte supplémentaires.
polfosol ఠ_ఠ
1
L'utilisation des caractères ascii 0-7 devrait être plus courte, par exemple, n=>"INSERT ASCII HERE".Select(a=>1<<a&n)mais je suis sur un appareil mobile qui ne peut pas afficher ou taper les caractères non imprimables, donc je vais devoir attendre jusqu'à ce que je rentre à la maison pour mettre à jour la réponse
Embodiment of Ignorance
6

C # (Visual C # Interactive Compiler) , 38 octets

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

Essayez-le en ligne!

Dana
la source
aw, close: P
ASCII uniquement
1
Ne parvient pas pour les entrées 1, 2, 4, 8, 16, etc. (le x>ydevrait être à la x>=yplace).
Kevin Cruijssen
1
@ASCIIOnly - Je vous le dis, l' opérateur de la plage va être gentil :)
dana
@ ASCII seulement en moyenne, vous pouvez utiliser le drapeau /u:System.Linq.Enumerableet essayer ce pour 31 octets
de l'ignorance
@EmbodimentofIgnorance bien sûr. mais je préfère ne pas lister la langue comme "C # /u:System.Linq.Enumerable": P
ASCII uniquement
5

05AB1E, 7 octets

2вRƶ<oò

explication:

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

Essayez-le en ligne!

Jackson
la source
Fonctionne également avec l'entrée de 302231454903657293676544
Michael Karas
5

C (bruit) , 133 110 63 58 octets

Solution de 58 octets grâce à @ceilingcat .

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

Essayez-le en ligne!

une arachnide de pierre
la source
En C89, vous pouvez déclarer like main(){}et le type de retour par défaut int. Idem pour les variables à portée globale. De plus, au moins sur les implémentations normales comme clang, printf et scanf fonctionnent sans prototypes. Vous obtenez des avertissements bien sûr, mais c'est toujours C89 valide (peut-être) ou au moins K&R C pour qu'ils soient implicitement déclarés. Les types des objets C que vous passez en tant qu'args définissent comment ils sont passés, donc un char*et fonctionnera int*simplement sans tronquer les pointeurs à 32 bits sur x86-64 ou quoi que ce soit. (Les promotions d'argument par défaut se produisent, comme pour les fonctions variadiques qu'elles sont de toute façon.)
Peter Cordes
Ou vise-t-il à être valide C11 sans comportement indéfini? Si c'est le cas, proclamez-le fièrement. :) Et BTW, écrire une fonction qui prend un tableau de sortie comme argument serait probablement plus petit. Quoi qu'il en soit, voir Conseils pour jouer au golf en C
Peter Cordes
Vous pouvez utiliser au niveau du bit &pour vérifier si un bit est défini. Comme y&(1<<x)&&printf("%d ",1<<x);. Ou pour ne pas sauter de zéros, juste printf("%d ", y&(1<<x)). Ou au lieu de compter les positions des bits, utilisez x=256et x>>=1pour déplacer le masque. main(y){int x=256;for(scanf("%d",&y);x>>=1;)printf("%d ",y&x);}63 octets Essayez-le en ligne! clang compilera même cela avec-std=c11
Peter Cordes
44 octets
plafond
4

MATL , 5 octets

BPfqW

Essayez-le en ligne!

Explication

Considérez l'entrée 86comme un exemple.

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
la source
4

Perl 6 , 16 12 octets

-4 octets grâce à Jonathan Allan

*+&2**all ^8

Essayez-le en ligne!

Renvoie une jonction All avec 8 éléments. Il s'agit d'un moyen de retour plutôt non standard, mais généralement, les jonctions peuvent agir comme des listes ordonnées (au moins jusqu'à ce que la lecture automatique soit implémentée) et il est possible d'extraire les valeurs d'une liste.

Explication:

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

Japt, 8 5 octets

Æ&2pX

L'essayer

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

Suggéré par Oliver pour éviter les 0s dans la sortie en utilisant l' -mfindicateur.

N&2pU

L'essayer

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
Hirsute
la source
1
Joli. Vous pouvez faire N&2pUavec -mfpour éviter le 0s
Oliver
4

05AB1E , 9 octets

Ýoʒ›}æʒOQ

Essayez-le en ligne!

Ceci est également correct pour 6 octets, mais il ne se termine pas à temps sur TIO pour 86:

05AB1E , 6 octets

ÝoæʒOQ

Essayez-le en ligne!

Urne Magique De Pieuvre
la source
1
Vos deux réponses donnent un ensemble vide pour 15, au lieu de[1,2,4,8]
Kevin Cruijssen
1
@KevinCruijssen nécessaire 2**0, belle prise. Ýfini L.
Urne de poulpe magique le
1
Ah, je connais le sentiment. Avait également Lau lieu de Ýd'abord dans ma réponse.
Kevin Cruijssen
4

K (oK) , 19 16 octets

-3 octets grâce à ngn!

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

Essayez-le en ligne!

oK n'a pas d' poweropérateur, c'est pourquoi j'ai besoin d'une fonction d'aide {*/x#2}(copiez 2 xfois et réduisez la liste résultante par multiplication)

Galen Ivanov
la source
vous pouvez omettre le{ x}
ngn
@ngn Merci! Je l'ai essayé et cela a fonctionné, mais je n'étais pas sûr qu'il soit acceptable.
Galen Ivanov
4

Alchimiste , 125 octets

_->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

Essayez-le en ligne! ou Testez chaque entrée!

Explication

_->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 seulement
la source
4

PHP ,41 39 octets

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

Essayez-le en ligne!

Ou 38 sans >>=opérateur amusant et PHP 5.6+:

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

Ou 36 avec sortie little-endian ("0 2 4 0 16 0 64 0"):

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

Vraiment, je voulais juste utiliser l' >>=opérateur, donc je m'en tiens au 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
640 Ko
la source
4

TSQL, 43 39 octets

Impossible de trouver une solution de fantaisie plus courte, alors voici une boucle standard. -4 octets grâce à MickyT et KirillL

DECLARE @y int=255

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

Essaye le

t-clausen.dk
la source
en utilisant les bits et (&), vous pouvez en enregistrer quelques-uns avec ce qui suit ,@ int=128s:print @y&@ set @/=2IF @>0GOTO s. C'est suggéré par @KirillL pour la réponse R
MickyT
@MickyT qui fonctionnait comme un charme. Merci beaucoup
t-clausen.dk
3

Python 2 , 43 40 octets

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

Essayez-le en ligne!

ovs
la source
1
@JonathanAllan, cela a certainement aidé. Merci de m'avoir prévenu.
OVS
1
... et la restriction a été levée, donc -1 octet :)
Jonathan Allan
3

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

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

Port de la réponse JavaScript (ES6) de @Arnauld , alors assurez-vous de voter pour lui!

Essayez-le en ligne.

Explication:

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
la source