32
\$\begingroup\$

The Challenge

Given an integer input x where 1 <= x <= 255, return the results of powers of two that when summed give x.

Examples

Given the input:

86

Your program should output:

64 16 4 2

Input:

240

Output:

128 64 32 16

Input:

1

Output:

1

Input:

64

Output:

64

The output may contain zeros if the certain power of two is not present in the sum.

For example, input 65 may output 0 64 0 0 0 0 0 1.

Scoring

This is , so the shortest answer in each language wins.

\$\endgroup\$
  • 5
    \$\begingroup\$ Does the list have to be sorted highest to lowest? \$\endgroup\$ – Adám Jan 28 '19 at 20:56
  • 2
    \$\begingroup\$ May we output some redundant zeros? \$\endgroup\$ – Jonathan Allan Jan 28 '19 at 20:58
  • 4
    \$\begingroup\$ RE: "sorted highest to lowest" why add a restriction that was not part of the challenge and invalidates most existing answers? (Also what about little-endian?!) + it invalidates my Python answer since sets do not have any order. \$\endgroup\$ – Jonathan Allan Jan 28 '19 at 21:38
  • 5
    \$\begingroup\$ @JonathanAllan I've removed the restriction. I'll keep that in mind next time I post another question - I'm still fairly new to this. :) \$\endgroup\$ – SpookyGengar Jan 28 '19 at 22:28
  • 6
    \$\begingroup\$ I think you might want to state that any power of two may only be used once. Otherwise somebody could output "1 1 1" for the input 3. \$\endgroup\$ – Black Owl Kai Jan 29 '19 at 10:58

56 Answers 56

40
\$\begingroup\$

JavaScript (ES6), 28 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
  • 10
    \$\begingroup\$ You're the only person in the whole world who can make me upvote JavaScript answers! \$\endgroup\$ – sergiol Jan 29 '19 at 0:05
  • 4
    \$\begingroup\$ @sergiol, why wouldn't you normally upvote a JS solution? A good solution is a good solution regardless of the language used or who posted it. \$\endgroup\$ – Shaggy Jan 29 '19 at 13:23
  • \$\begingroup\$ @Shaggy Because Arnauld seems the only person to do such Javascript solutions. His answers are pure genius! \$\endgroup\$ – sergiol Jan 29 '19 at 15:11
  • 3
    \$\begingroup\$ @sergiol Thanks for the compliment, but that's not quite true. I'm regularly outgolfed by more clever answers -- and that's what this site is all about. ^^ \$\endgroup\$ – Arnauld Jan 29 '19 at 15:18
  • \$\begingroup\$ @Oliver I'm not sure. It seems like leading zeros (before 128) are forbidden. Otherwise, another possible variant is f=n=>n&&f(n&~-n)+[,n&-n]. \$\endgroup\$ – Arnauld Jan 29 '19 at 19:47
13
\$\begingroup\$

Pure Bash, 20

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

Try it online!

Explanation

          {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
| improve this answer | |
\$\endgroup\$
13
\$\begingroup\$

Jelly, 4 bytes

-2 since we may output zeros in place of unused powers of 2 :)

Ḷ2*&

Try it online!

How?

Ḷ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]
| improve this answer | |
\$\endgroup\$
11
\$\begingroup\$

Jelly, 6 bytes

BUT’2*

Try it online!

Explanation

BUT here is an explanation (note: I had assumed that we may only output the powers of 2 themselves and nothing else):

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]

"Proof" that it works correctly. The standard representation of an integer \$ X\$ in base 2 is a list \$\{x_1, x_2, x_3,\cdots, x_n\}\$, where \$x_i\in\{0,1\},\:\forall\:\: i\in\overline{1,n}\$, such that: $$X=\sum_{i=1}^n x_i\cdot 2^{n-i}$$ The indices \$i\$ such that \$x_i=0\$ obviously have no contribution so we're only interested in finding those such that \$x_i=1\$. Since subtracting \$i\$ from \$n\$ is not convenient (the powers of two all have exponents of the form \$n-i\$, where \$i\$ is any index of a \$1\$), instead of finding the truthy indices in this list we reverse it and then find them "backwards" with UT. Now that we've found the correct indices all we have to do is raise \$2\$ to those powers.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ "ASCII-only" Sneaky there... \$\endgroup\$ – Erik the Outgolfer Jan 28 '19 at 21:05
  • 1
    \$\begingroup\$ @EriktheOutgolfer I guess BUT2*H would work though. \$\endgroup\$ – Mr. Xcoder Jan 28 '19 at 21:08
  • 1
    \$\begingroup\$ Pretty impressive that this works with an input of 302231454903657293676544. \$\endgroup\$ – Michael Karas Feb 3 '19 at 13:47
10
\$\begingroup\$

Python, 35 bytes

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

Little-endian with zeros at unused powers of 2.

Try it online!

| improve this answer | |
\$\endgroup\$
9
\$\begingroup\$

Catholicon, 3 bytes

ṫĊŻ

Try it online!

Explanation:

ṫ       Decompose         into the largest values where:
 Ċ               the input
  Ż       the bit count is truthy (equal to one)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Interesting! Get TIO'd :D \$\endgroup\$ – Jonathan Allan Jan 28 '19 at 22:25
  • \$\begingroup\$ Works with 302231454903657293676544. Nice. \$\endgroup\$ – Michael Karas Feb 3 '19 at 13:54
8
\$\begingroup\$

APL (Dyalog Extended), 7 bytesSBCS

Anonymous tacit prefix function. Requires 0-based indexing (⎕IO←0).

2*⍸⍢⌽⍤⊤

Try it online!

2 two
* raised to the power of
 the ɩndices where true
 while
 reversed
 of
 the binary representation

| improve this answer | |
\$\endgroup\$
8
\$\begingroup\$

Sledgehammer 0.2, 3 bytes

⡔⡸⢣

Decompresses into {intLiteral[2],call[NumberExpand,2]}.

Sledgehammer is a compressor for Wolfram Language code using Braille as a code page. The actual size of the above is 2.75 bytes, but due to current rules on meta, padding to the nearest byte is counted in code size.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Huh! Neat little language, and all the characters are actually printable. \$\endgroup\$ – LegionMammal978 Jan 29 '19 at 15:41
  • \$\begingroup\$ And now I can't get the Peter Gabriel song out of my mind... \$\endgroup\$ – Digital Trauma Jan 31 '19 at 22:14
8
\$\begingroup\$

05AB1E, 3 bytes

Ýo&

Port of @JonathanAllan's Jelly answer, so make sure to upvote him!

Contains zeros (including -loads of- trailing zeros).

Try it online or verify all test cases.

Explanation:

Ý      # 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)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ ... what?! Never honestly seen bitwise and used in osabie. Nice one. \$\endgroup\$ – Magic Octopus Urn Jan 29 '19 at 15:40
  • \$\begingroup\$ @MagicOctopusUrn I indeed also don't use it very often. Can't even find any other answer I've used & in. xD I have used Bitwise-XOR a couple of times, like here or here and Bitwise-NOT once here (which I later removed again after golfing further..). I do use Bitwise-AND, XOR, OR, NOT, SHIFT, etc. pretty often in Java, but in 05AB1E not so much. :) \$\endgroup\$ – Kevin Cruijssen Jan 29 '19 at 15:55
7
\$\begingroup\$

Wolfram Language (Mathematica), 17 bytes

#~NumberExpand~2&

Try it online!

Mathematica strikes again.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This also works with input of 302231454903657293676544. \$\endgroup\$ – Michael Karas Feb 3 '19 at 13:56
7
\$\begingroup\$

R, 27 23 bytes

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

Try it online!

Unrolled code and explanation :

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 thanks to @Kirill L.
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 23 bytes with bitwise and. \$\endgroup\$ – Kirill L. Jan 29 '19 at 9:53
  • \$\begingroup\$ @KirillL.: brilliant ! \$\endgroup\$ – digEmAll Jan 29 '19 at 13:16
7
\$\begingroup\$

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

Contains 5 unprintable characters.

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

Explanation

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

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ But we need to get rid of zeros, like n=>new int[8].Select((j,i)=>1<<i&n).Where(i=>i!=0) The part before Where is five bytes shorter btw \$\endgroup\$ – polfosol ఠ_ఠ Jan 29 '19 at 8:49
  • \$\begingroup\$ @polfosol The output may contain zeros \$\endgroup\$ – Jo King Jan 29 '19 at 9:06
  • 2
    \$\begingroup\$ @JoKing Still, n=>new int[8].Select((j,i)=>1<<i&n) is 35 bytes long and we won't need additional flags and text encodings. \$\endgroup\$ – polfosol ఠ_ఠ Jan 29 '19 at 13:02
  • 1
    \$\begingroup\$ Using ascii characters 0-7 should be shorter, eg n=>"INSERT ASCII HERE".Select(a=>1<<a&n) But I'm on a mobile device that can't display or type unprintables, so I'll have to wait till I get home to update the answer \$\endgroup\$ – Embodiment of Ignorance Jan 29 '19 at 16:34
6
\$\begingroup\$

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

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

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ aw, close :P \$\endgroup\$ – ASCII-only Jan 29 '19 at 7:45
  • 1
    \$\begingroup\$ Fails for inputs 1, 2, 4, 8, 16, etc. (the x>y should be x>=y instead). \$\endgroup\$ – Kevin Cruijssen Jan 29 '19 at 9:37
  • 1
    \$\begingroup\$ @ASCIIOnly - I'm telling you, the range operator is going to be sweet :) \$\endgroup\$ – dana Jan 29 '19 at 13:43
  • \$\begingroup\$ @ASCII-only Mean while, you can use the flag /u:System.Linq.Enumerable and try this for 31 bytes \$\endgroup\$ – Embodiment of Ignorance Jan 29 '19 at 23:18
  • \$\begingroup\$ @EmbodimentofIgnorance sure. but i'd prefer not to list language as "C# /u:System.Linq.Enumerable" :P \$\endgroup\$ – ASCII-only Jan 30 '19 at 4:54
5
\$\begingroup\$

C (gcc), 39 bytes

f(n){for(;n;n&=n-1)printf("%d ",n&-n);}

Try it online!

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Also works with input of 302231454903657293676544 \$\endgroup\$ – Michael Karas Feb 3 '19 at 14:00
5
\$\begingroup\$

Haskell, 29 bytes

(mapM(\n->[0,2^n])[7,6..0]!!)

Try it online!

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Ruby, 25 bytes

->n{8.times{|i|p n&2**i}}

Try it online!

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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.) \$\endgroup\$ – Peter Cordes Jan 30 '19 at 3:46
  • \$\begingroup\$ 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 \$\endgroup\$ – Peter Cordes Jan 30 '19 at 3:48
  • \$\begingroup\$ 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 \$\endgroup\$ – Peter Cordes Jan 30 '19 at 4:11
  • \$\begingroup\$ 44 bytes \$\endgroup\$ – ceilingcat Feb 9 '19 at 1:25
4
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice one. You can do N&2pU with -mf to avoid the 0s \$\endgroup\$ – Oliver Jan 29 '19 at 2:54
4
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Both your answers output an empty set for 15, instead of [1,2,4,8] \$\endgroup\$ – Kevin Cruijssen Jan 29 '19 at 7:14
  • 1
    \$\begingroup\$ @KevinCruijssen needed 2**0, nice catch. Ý over L. \$\endgroup\$ – Magic Octopus Urn Jan 29 '19 at 15:29
  • 1
    \$\begingroup\$ Ah, I know the feeling. Also had L instead of Ý at first in my answer. \$\endgroup\$ – Kevin Cruijssen Jan 29 '19 at 15:31
4
\$\begingroup\$

Julia 0.6, 13 bytes

n->n&2.^(0:7)

Try it online!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

CJam, 12 bytes

{:T{2\#T&}%}

Try it online!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ you can omit the { x} \$\endgroup\$ – ngn Jan 31 '19 at 12:49
  • \$\begingroup\$ @ngn Thanks! I tried it and it worked, but I wasn't sure it is acceptible. \$\endgroup\$ – Galen Ivanov Jan 31 '19 at 15:25
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – MickyT Jan 31 '19 at 19:49
  • \$\begingroup\$ @MickyT that worked like a charm. Thanks a lot \$\endgroup\$ – t-clausen.dk Feb 1 '19 at 0:02
3
\$\begingroup\$

Python 2, 43 40 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ @JonathanAllan this definitely helped. Thanks for notifying me. \$\endgroup\$ – ovs Jan 28 '19 at 22:20
  • 1
    \$\begingroup\$ ...and the restriction has been lifted, so -1 byte :) \$\endgroup\$ – Jonathan Allan Jan 28 '19 at 22:35
3
\$\begingroup\$

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`
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.