# Sum of Powers of 2

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.

• Does the list have to be sorted highest to lowest? – Adám Jan 28 '19 at 20:56
• May we output some redundant zeros? – Jonathan Allan Jan 28 '19 at 20:58
• 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. – Jonathan Allan Jan 28 '19 at 21:38
• @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. :) – SpookyGengar Jan 28 '19 at 22:28
• 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. – Black Owl Kai Jan 29 '19 at 10:58

# Java 8, 46 bytes

n->{for(;n>0;n&=n-1)System.out.println(n&-n);}


Try it online.

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

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
System.out.println(  //   Print with trailing newline:
n&-n);}            //    n bitwise-AND -n

• Breakthrough in Java: 36 chars, by using this rule. Let's go back 5 years and golf all Java answers ever produced! – Olivier Grégoire Jan 29 '19 at 16:29
• @OlivierGrégoire Hmm, although I agree that it's most likely allowed, I'll pass tbh. I have used that rule when the input is for example an array, and we modify the input-array instead of returning a new one to save bytes. But adding an additional empty List argument just to store the output in to save byte with .add instead of System.out.println seems a bit cheaty imho. – Kevin Cruijssen Jan 29 '19 at 17:13
• Kind of like how Array.sort() doesn't actually return anything, it just modifies the input. That seems legit. In C# you can use void f(out int x) or void f(ref int x) to return the result, but that doesn't seem to help w/ golf in my experiments. – dana Feb 1 '19 at 9:17

say"@F"&2**$_ for 0..7  if newlines allowed as delimiter 22 bytes 28 bytes # Python 2, 36 bytes def f(x):n=1;exec'print n&x;n*=2;'*8  Try it online! # PowerShell, 45 37 bytes param($a)7..0|%{1-shl$_}|?{$_-band$a}  Try it online! Takes input $a, loops from 7 to 0, each iteration performing a bit-shift left (-shl) to formulate the powers-of-two for each exponent. We then pull out those ? (where) the number $_ shares a value -binaryand with the input number. -8 bytes thanks to mazzy • 1-shl$_ instead '2*'*$_+'1'|iex? – mazzy Jan 29 '19 at 3:54 • @mazzy Oh, good call. I forgot we're dealing with numbers that work with -shl. – AdmBorkBork Jan 29 '19 at 13:03 # 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  # JavaScript - 33 bytes n=>[..."01234567"].map(i=>n&2**i)  # 32 bytes, Oliver's suggestion n=>[...2**29+'4'].map(x=>n&2**x)  # SAS, 91 bytes data;input n;length o$99;z=1;do while(n);if mod(n,2) then o=z||o;n=int(n/2);z+z;end;cards;


Input is entered on separate lines after the cards; statement, like so:

data;input n;length o $99;z=1;do while(n);if mod(n,2) then o=z||o;n=int(n/2);z+z;end;cards; 86 240 1 64  Outputs a dataset with a string representation of the binary values in the o variable Explanation: data; input n; /* Read a line of input */ length o$99; /* Output string (max of 99 characters) */
z=1; /* First power of 2 */
do while(n); /* While remainder is not 0 */
if mod(n,2) then o=z||o; /* If current binary digit is 1, append power of two to start of output */
n=int(n/2); /* Move to next binary digit */
z+z; /* Double current power of two to get next power of two (add it to itself) */
end;
cards;
86
240
1


# 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!

# QBasic, 62 60 bytes

INPUT n
t=2^n
WHILE n
IF t<=n THEN
?t
n=n-t
ENDIF
t=t/2
WEND


Here's a REPL, slightly expanded to not break QB.js's compiler...

## How does it work?

INPUT n     gets the input
t=2^n       sets t to a power of 2, overshooting the first power of two
WHILE n     while we haven't fully deconstucted the input
IF t<=n THEN        if we found a power of two that is in this number
?t          then print it
n=n-t           and 'deconstruct' n by that amount
ENDIF
t=t/2       drop down to the next power of two and
WEND        repeat testing


Edit Saved 2 bytes, while n>0 is equivalent to while n.

# Wolfram Language 58 bytes

Flatten[2^#&/@(Position[Reverse@IntegerDigits[#,2],1]-1)]&


IntegerDigits[#,2] returns the binary representation of the input, #, as a list of 1's and 0's.

Reverse@ reverses that list.

(Position[...,1]-1) lists the positions of the 1's in the reversed list and decrements each position by 1.

2^#&/@ 2 is raised to the power of (position -1) for each integer in the list.

Flatten removes nested braces.

• The sort-order restriction has been lifted (also you may have zeros in place of unused powers of 2 now, if that helps) – Jonathan Allan Jan 28 '19 at 22:44
• @JonathanAllan, Thanks, it saves 6 bytes. There are no zeros generated by this approach. – DavidC Jan 28 '19 at 23:24

# Alchemist, 116 bytes

_->In_a+c
0f+a+0d->d
0f+a+d->e
0f+g->c
0_+0f+0g+0a+0d->f
0f+0g+0a+d->Out_c+Out_" "+f
f+e->f+a
f+c->f+2g
f+0c+0e+a->a


Try it online!

Uses a different approach to the existing Alchemist answer. Instead of counting back from 128, we count upwards, which can then support any positive input.

### Explanation:

_->In_a          # Get input number of a atoms
+c        # And initialise the power of 2
0f+a+0d->d       # Divmod the input by 2
0f+a+d->e

0f+0g+0a+d->Out_c+Out_" "+f    # If there is a remainder, print the current power of 2
0_+0f+0g+0a+0d->f              # Otherwise, do nothing

f+e->f+a         # Reset the number to the division by 2
f+0c+0e+a->a     # While the number is not zero, restart the loop

f+c->f+2g        # And double the power of 2
0f+g->c


# x86-64 machine code, 12 bytes

This is a function you can call with the x86-64 System V calling convention, with this signature:
void binary_placevalues_withzero(uint8_t out[8] /*rdi*/, uint8_t val /*sil*/); or
void binary_placevalues_withzero(uint64_t *out /*rdi*/, uint8_t val /*sil*/); as a quick hack for making the output something you can print as one hex number for all 8 bytes.

It isolates the place values in increasing order into the output array, producing a result like 80 00 00 00 00 00 00 01 for esi = 129.

We start with mask = 1, and left-shift the mask by 1 until it overflows an 8-bit register.

nasm -l listing
25 address   code bytes    global binary_placevalues_withzero
26                         binary_placevalues_withzero:
27 00000020 B101               mov  cl,1
28                         .loop:
29 00000022 88C8               mov  al,cl
30 00000024 21F0               and  eax, esi     ; al,sil would cost a REX prefix
31 00000026 AA                 stosb             ; *rdi++ = val & mask
32 00000027 00C9               add  cl,cl        ; left-shift the mask
33 00000029 73F7               jnc  .loop        ; until it shifts out
34 0000002B C3                 ret


An alternate version that only writes non-zero entries (thus producing an output array of length __builtin_popcount(val)) is also 12 bytes. This needs val zero-extended into ESI to avoid test false positives, unlike the version that doesn't skip zeros.

void binary_placevalues(uint8_t out[8] /*rdi*/, unsigned val /*esi*/);

    11                         global binary_placevalues
12                         binary_placevalues:
13 00000010 B001               mov  al,1
14                         .loop:
15 00000012 85F0               test  eax, esi    ; ESI must have its high bits clear, so high garbage in EAX doesn't matter
16 00000014 7401               jz   .skip
17 00000016 AA                 stosb             ; store if the mask matches
18                         .skip:
19 00000017 00C0               add  al,al        ; left-shift the mask
20 00000019 73F7               jnc  .loop
21 0000001B C3                 ret
22


As usual, ISA extensions that let us save instructions cost more code bytes: a BMI1 version is 14 bytes. (https://www.felixcloutier.com/x86/BLSI.html and https://www.felixcloutier.com/x86/BLSR.html). Very efficient, though: each of these BLSI/BLSR instructions is only 1 uop.

     1                         global binary_placevalues_bmi1
2                         binary_placevalues_bmi1:
3                         .loop:
4 00000000 C4E278F3DE         blsi  eax, esi    ; bit lowest-set isolate:  n &-n
5 00000005 AA                 stosb
6 00000006 C4E248F3CE         blsr  esi, esi    ; bit lowest-set reset: (n-1) & n, and sets ZF according to the result.
7 0000000B 75F3               jnz .loop
8 0000000D C3                 ret


(If there was high garbage in ESI, this would keep going, storing 0 bytes when EAX held an isolated bit outside the low 8.)

If you wanted speed, with BMI2 pdep you'd use a 64-bit mask that deposited the low 8 bits at their corresponding position within each byte. 1 uop / 3 cycle latency on Haswell/Skylake, at the cost of a 10-byte instruction to create the mask. :P But slow on Ryzen.

I'm not sure this is optimal. I don't think manually implementing n & -n and so on with xor/sub/and and so on would be a win, though.

• Hah! I wrote up a solution that did exactly that before I saw your answer. I pushed the results onto the stack, which was elegant, but meant I had to preserve and restore the return address (cost 2 bytes for push+pop) and also had to maintain a counter so the caller would know how many values to pop from the stack (cost 3 bytes for xor to zero + inc inside loop). Total was 20 bytes. That's about as good as it's going to get. All the instructions are 1 or 2 bytes. Might be able to shave off 2-4 bytes by taking a pointer to a pre-allocated buffer as an argument, like you did here. – Cody Gray Feb 9 '19 at 8:51
• @CodyGray: heh, that's fun. If you pop the ret addr, jmp rsi is 2 bytes, same as push/ret. But unbalances the return-address predictor stack, so in practice more instructions is better in this case. I kind of glossed over returning a size for the versions that skip 0 elements. The caller could pass a pre-zeroed buffer and treat the result as an implicit-length array (which works for my array-arg way, but not so much on the stack. Well I guess you could push 0 / call. But yeah, I was glad to find a fixed-length version with zeros so I didn't have to justify that or popcnt. – Peter Cordes Feb 9 '19 at 8:59

# Retina 0.8.2, 25 bytes

.+
$* M!(\G1|\1\1)*1 %1  Try it online! Explanation: .+$*


Convert to unary.

M!(\G1|\1\1)*1


Match as many powers of 2 as possible, and then an extra 1. This gives a total sum of the next power of 2. The regular expression is greedy (default), so tries to consume the largest possible power of 2 at each match. The M! then causes the matches themselves to be listed on separate lines.

%1


Convert each line back to decimal.

# Charcoal, 12 bytes

Ｉ⮌Ｅ⮌↨Ｎ²×ιＸ²κ


Try it online! Link is to verbose version of code. Includes zero values (+2 bytes to remove). Explanation:

     Ｎ          Input number
↨           Converted to base (MSB first)
²         Literal 2
⮌            Reversed (i.e. LSB first)
Ｅ             Map over bits
ι       Current bit
×        Multiplied by
²     Literal 2
Ｘ      Raised to power
κ    Current index
⮌              Reversed (back to MSB first)
Ｉ               Cast to string
Implicitly print on separate lines

• Apparently the restriction on output order has been removed, which means that the first ⮌ can be removed for a 1-byte saving. – Neil Jan 29 '19 at 9:51
• Nice. This also works with an input of 302231454903657293676544. – Michael Karas Feb 3 '19 at 13:53

# Alchemist, 274 bytes

_->9a+In_x+s
s+a->s+b+c
s+x->s+y+z
s+0a+0x+b->b+d+m
s+0a+0x+0b->n+e
d+m->d+2n
d+0m->e
e+n->e+m
e+0n+b->d
e+0n+0b->h
h+m->h+u+v
h+0m->t
t+y+u->t
t+0y+u->f
t+y+0u->g+p
t+0y+0u->p
g+0p+z+v->g
g+0v->f
f+c->f+a
f+z->f+x
f+u->f
f+v->f
f+y->f
f+0v+0u+0z+0c+0y+a->s
p->Out_v+Out_" "


Try it online!

## Ungolfed & Serialized

The algorithm is generating the powers of two from above, subtracting them from the input, check whether it's less or equal (output & decrement value in that case) or not and repeat while having enough copies of every value, to restore stuff (reading in Alchemist is pretty much destructive).

The "states" s0X can be merged, same with nxt without changing correctness of the program by combining all the zero-rules. The order of setting up copies or cleanup doesn't matter1:

_ -> 9a + In_x + s00

# Setup copies of x and a
s00 + a -> s00 + b + c
s00 + 0a -> s01
s01 + x -> s01 + y + z
s01 + 0x + b-> b+s1 + m
s01 + 0x +0b -> n+s2

# Compute power of
s1 +  m -> s1 + 2n
s1 + 0m -> s2

s2 +  n      -> s2 + m
s2 + 0n +  b -> s1
s2 + 0n + 0b -> s3

# Duplicate the power of two
s3 + m -> s3 + u+v
s3 +0m -> tst

# Check if it's below the value
tst +  y +  u -> tst
tst + 0y +  u -> nxt0                  # if not continue
tst +  y + 0u -> go + Out_v + Out_" "  # if not equal, output & continue
tst + 0y + 0u -> Out_v + Out_" "       # if equal, output

# Decrement the current value
go + z + v -> go
go + 0v -> nxt0

# Clear & restore for "next iteration"
nxt0 + c -> nxt0 + a  # restore counter
nxt0 + 0c->nxt1
nxt1 + z -> nxt1 + x  # restore current value (possibly decremented)
nxt1 + 0z -> nxt2
nxt2 + u -> nxt2      # clean up remainder of power of two ..
nxt2 + 0u -> nxt3
nxt3 + v -> nxt3      # .. and its copy
nxt3 + 0v -> nxt4
nxt4 + y -> nxt4      # clean up the rest of comparison
nxt4 + 0y + a -> s00


Try it online!

1: The way to read it is like this: The first atom on the left-handside encodes a state (to serialize control-flow), the other atoms are counters which are replaced by the right-handside.

• explanation pls – ASCII-only Jan 29 '19 at 1:49
• @ASCII-only: Done :) – ბიმო Jan 29 '19 at 1:57
• btw pls compress debug output, i.e. rule 100 times -> [rule] x 100 – ASCII-only Jan 29 '19 at 2:19
• argh i keep getting close (read: i'm terrible at this) – ASCII-only Jan 29 '19 at 2:35
• 145? m = halve, n = compare, o = restore x, p = refill d. a = value to compare to, b = value to compare a with to restore x, c = value to refill d with – ASCII-only Jan 29 '19 at 2:38

# Pari/GP, 31 bytes

n->[2^i|i<-[0..n],bittest(n,i)]


Try it online!

# MATL, 5 bytes

BXdXB


Try it online!

### Explanation

B    % Convert to binary (as a vector)
Xd   % Give a diagonal matrix with the vector on its diagonal
XB   % Convert each row of the matrix to decimal

• Nice result with 302231454903657293676544 working. – Michael Karas Feb 3 '19 at 13:59

# F# (.NET Core), 41 bytes

fun x->Seq.map(fun y->x&&&pown 2 y)[0..7]


Try it online!

# 05AB1E, 6 bytes

bRεNo*


## Explanation

       # Implicit input n
b      # Convert to binary
R     # Reverse
ε    # For each digit d in the binary number
N   # Push its index N
o* # Compute d*2^N
# Implicit output of list of results


# J, 13 bytes

(2^I.)&.|.@#:


Try it online!

# Ruby, 26 bytes

->n{(0..7).map{|i|n&2**i}}


Try it online!

Same approach as Jonathan Allan's answer.

# JS, 103 bytes

m=Math;f=a=>2**(m.floor(m.log2(a)));x=prompt()*1;y="";while(x>0&&x<256){z=f(x);y=y+" "+z;x=x-z}alert(y)


# ArnoldC, 609 bytes

IT'S SHOWTIME
HEY CHRISTMAS TREE N
YOU SET US UP 0
GET YOUR ASS TO MARS N
DO IT NOW
I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY
HEY CHRISTMAS TREE I
YOU SET US UP 128
HEY CHRISTMAS TREE B
YOU SET US UP 0
STICK AROUND I
GET TO THE CHOPPER B
HERE IS MY INVITATION I
LET OFF SOME STEAM BENNET N
ENOUGH TALK
BECAUSE I'M GOING TO SAY PLEASE B
BULLSHIT
TALK TO THE HAND I
GET TO THE CHOPPER N
HERE IS MY INVITATION N
GET DOWN I
ENOUGH TALK
YOU HAVE NO RESPECT FOR LOGIC
GET TO THE CHOPPER I
HERE IS MY INVITATION I
HE HAD TO SPLIT 2
ENOUGH TALK
CHILL
YOU HAVE BEEN TERMINATED


Try it online!

I apologise.

# Chip-w, 115 bytes

H!ZZ--ZZZ--ZZZ--ZZZZ-Z-ZZZ-Z-ZZt
@^))e G>)e F>)e E>).d[DC].b[Bze
a,x]dc[(' b[('ca[L'e'*sece'A]a
H]--b['*fa['b^-['


Try it online!

Takes a single raw byte as input, and returns some mix of 128 64 32 16 8 4 2 1 and 000 00 00 00 0 0 0 0

In the TIO, the argument -wgNN will provide this program with a byte of value 0xNN. So, -wg5c provides 0x5c. The special value -wgkk will instead generate a random byte.

Chip is a 2D language where each element can interact with its four neighbors with single bit values only. An unsmooshed version of the above would look like this:

!ZZZ--ZZZ--ZZZ--ZZZ--ZZ--ZZ--ZZ--Zt
)))---))---))---))---)---)---)---)-e
|||H  ||G  ||F  ||E  |D  |C  |B  |A
xx)]d xx]d xx]d xx]d )]d x]d x]d x]d
xxx]c ))]c xx]c x)]c x]c )]c x]c x]c
x)x]b )x]b ))]b x)]b x]b x]b )]b x]b
)xx]a xx]a )x]a )x]a x]a x]a x]a )]a

s*f


Here we can see eight blocks, one for each power of two, from left to right. Each block contains a grid specifying which bits should be turned on for each character of that power. The input bits (capital letters) are connected as switches to control whether each digit should be its actual value, or zero.

# x86 Machine Code, 20 bytes

; ECX is the input value ('x')
; EDX is a temporary, used for manipulations of 'x'
; EAX is a counter, which will also be the return value
; EBP is a temporary holding space for the return address

GetSumOfPowersOf2:
5D            pop    ebp              ; save return address
31 C0         xor    eax, eax         ; counter = 0

MainLoop:
89 CA         mov    edx, ecx         ; \
F7 DA         neg    edx              ; | temp = (x & -x)
21 CA         and    edx, ecx         ; /
52            push   edx              ; push temp onto stack
40            inc    eax              ; increment counter
89 CA         mov    edx, ecx         ; \
4A            dec    edx              ; | x = (x & (x - 1))
21 D1         and    ecx, edx         ; /
75 F1         jne    SHORT MainLoop   ; loop while x != 0

55            push   ebp              ; restore return address
C3            ret                     ; return to return address, with result in EAX


These bytes define a function, which takes as input a single 32-bit integer argument in the ECX register (the choice of which register to pass the input in is rather arbitrary, but ECX is the one used in the __fastcall calling convention). This is the value x from the question.

x is assumed to be non-zero, since it is given that 1 <= x <= 255. This allows us to only test the loop condition at the bottom of the loop.

The bulk of the code is a big ol' loop that calculates the powers of two using binary bit-twiddling and pushes them onto the stack. On x86, the PUSH instruction pushes a register value onto the stack and requires only 1 byte to encode, so it's a natural choice. The caller of this function will then just retrieve the return values by POPing them off the stack. Although this is a non-standard convention (by convention, a function's result is either returned in a register or stored into a memory address via a pointer), it works.

Well, as long as you attend to one little detail: the fact that the CALL instruction pushes the return address onto the stack, and the fact that the RET instruction knows where to return by popping the return address pushed onto the stack by the CALL instruction. So, if we want to return values on the stack, we need to preserve the return address at the top of the function. This is done by POPing the value at the top of the stack into the EBP register for safe-keeping, PUSHing the return values onto the stack during the loop, and then PUSHing the value in EBP (the preserved return address) onto the stack at the position where the RET instruction will expect to find it.

With this arrangement, when control returns to the caller, all they'll have to do is POP off the return values. Of course, they need to know how many values to pop off the stack, so we have to maintain a counter inside of the loop. The EAX register was chosen for this counter, since in all x86 calling conventions, functions return their result in the EAX register. This function returns as its result the number of values to pop off of the stack.

The caller would do something like this to exercise the function:

    mov   ecx, 86             ; put input value ('x') into ECX for passing to function
call  GetSumOfPowersOf2   ; call the function
mov   ecx, eax            ; save the function's return value (number of values to pop off stack)
GetAndPrint:
pop   eax                 ; pop value off of stack into EAX
call  PrintValueInEAX     ; print the value stored in EAX
dec   ecx                 ; decrement counter
jnz   SHORT GetAndPrint   ; loop while counter != 0


# Pushy, 9 bytes

oBL:K2*#.


Try it online!

oB         \ Push binary digits to stack (least significant bit at the top).
L:       \ len(stack) times do:
K2*    \     Multiply all items by 2
#.  \     Pop and print the top item
`