Sum of Powers of 2

Question

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 code-golf, so the shortest answer in each language wins.

Answer 1

JavaScript (ES6), 28 bytes

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

Try it online!

Answer 2

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]

Answer 3

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.

Answer 4

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

Answer 5

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!

Answer 6

Catholicon, 3 bytes

ṫĊŻ

Try it online!

Explanation:

ṫ       Decompose         into the largest values where:
 Ċ               the input
  Ż       the bit count is truthy (equal to one)

Answer 7

APL (Dyalog Extended), 7 bytes^SBCS

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

Answer 8

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.

Answer 9

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)

Answer 10

Wolfram Language (Mathematica), 17 bytes

#~NumberExpand~2&

Try it online!

Mathematica strikes again.

Answer 11

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.

Answer 12

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!

Answer 13

C (gcc), 39 bytes

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

Try it online!

Answer 14

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

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

Try it online!

Answer 15

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

Answer 16

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!

Answer 17

Julia 0.6, 13 bytes

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

Try it online!

Answer 18

Haskell, 29 bytes

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

Try it online!

Answer 19

Ruby, 25 bytes

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

Try it online!

Answer 20

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!

Answer 21

APL (Dyalog Extended), 6 bytes

2*⍸⌽⊤⎕

2 to the * power of the ⍸ indices of the true bits of the ⌽ reversed ⊤ binary encoding of the ⎕ input

Try it online!

Answer 22

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]

Answer 23

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

Answer 24

APL(NARS) 18 chars, 36 bytes

{(⍵⊤⍨8⍴2)/⌽1,2*⍳7}

test:

  f←{(⍵⊤⍨8⍴2)/⌽1,2*⍳7}
  f 86
64 16 4 2 
  f 240
128 64 32 16 
  f 1
1 
  f 64
64 
  f 3
2 1 

Answer 25

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!

Answer 26

CJam, 12 bytes

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

Try it online!

Answer 27

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)

Answer 28

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

Answer 29

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

Answer 30

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