How do I decompose a number into powers of 2?

Question

I'm trying to create a function that receives a number as an argument and performs actions on that number to find out its closest powers of 2 that will then add up to that number. For example, if the user enters 4, the function will append 4 because it is already a power of 2. If the user enters a 14 the function should see that 14 is not a power of 2 and the closest powers of 2 that make up 14 are 2,4, and 8.

Key notes: I am only going up to 2^9.

What i have so far:

def powers_finder(n):
    powers=[]
    i=0
    total=0
    while i<10:
         value=2**i
         total=total+value
         i=i+1
         #This if statement is for if the user enters a power of 2 as n
         #Then the number will be appended right away into my powers list.
         if value==n:
            powers.append(value)

The problem here being if the user enters in lets say 5 as (n) 5 is made up of the power 2^2=4 and 2^0=1 4+1=5. How can i extend my function to include this process?

thank you!

Answer 1

The best and fastest way to do this is, of course, with binary numbers, but here's a way with a generator:

def powers_finder(num):
    d = []
    while sum(d) < num:
        p = powers_of_2()
        a=b=1
        while sum(d)+a<=num:
            b=a
            a = next(p)
        d.append(b)
    d.reverse()
    return d

def powers_of_2():
    n=1
    while 1:
        yield n
        n*=2

---

>>> print(powers_finder(5))
[1, 4]
>>> print(powers_finder(8))
[8]
>>> print(powers_finder(9))
[1, 8]
>>> print(powers_finder(14))
[2, 4, 8]

Answer 2

We have some nice answers for this question now. I figured I'd analyze them a bit with dis and timeit.

Here is the test code I used:

import dis
import timeit

def gbriones_gdl(num):
    result = []
    binary = bin(num)[:1:-1]
    for x in range(len(binary)):
        if int(binary[x]):
            result.append(2**x)
    return result

def nullptr(num):
    powers = []
    i = 1
    while i <= num:
        if i & num:
            powers.append(i)
        i <<= 1
    return powers

def t3_gen(num):
    d = []
    while sum(d) < num:
        p = powers_of_2()
        a=b=1
        while sum(d)+a<=num:
            b=a
            a = next(p)
        d.append(b)
    d.reverse()
    return d

def powers_of_2():
    n=1
    while 1:
        yield n
        n*=2

def t3_enum(num):
    return [2**p for p,v in enumerate(bin(num)[:1:-1]) if int(v)]

def moose(num):
    get_bin = lambda x: x >= 0 and str(bin(x))[2:] or "-" + str(bin(x))[3:]
    bin_str = get_bin(num)  # convert num to a binary string
    powers = []
    for i, digit in enumerate(bin_str[::-1]):
        if digit == '1':
            powers.append(2**i)
    return powers

print('Each function gives correct results:', nullptr(1048575) == moose(1048575) ==
t3_enum(1048575) == gbriones_gdl(1048575) ==
t3_gen(1048575))
print()

print('nullptr'.ljust(15), timeit.timeit('nullptr(1048575)', 'from __main__ import nullptr', number=100000))
print('moose'.ljust(15), timeit.timeit('moose(1048575)', 'from __main__ import moose', number=100000))
print('t3_enum'.ljust(15), timeit.timeit('t3_enum(1048575)', 'from __main__ import t3_enum', number=100000))
print('gbriones_gdl'.ljust(15), timeit.timeit('gbriones_gdl(1048575)', 'from __main__ import gbriones_gdl', number=100000))
print('t3_gen'.ljust(15), timeit.timeit('t3_gen(1048575)', 'from __main__ import t3_gen', number=100000))
print('\nnullptr:\n===========================')
print(dis.dis(nullptr))
print('\nmoose:\n===========================')
print(dis.dis(moose))
print('\nt3_enum:\n===========================')
print(dis.dis(t3_gen))
print('gbriones_gdl:\n===========================')
print(dis.dis(t3_enum))
print('\nt3_gen:\n===========================')
print(dis.dis(gbriones_gdl))

---

And here are the results:

Each function gives correct results: True

nullptr         0.7847449885390462
moose           1.810839785503465
t3_enum         2.898256901365956
gbriones_gdl    3.0904670146624778
t3_gen          21.366890624367063

nullptr:
===========================
 14           0 BUILD_LIST               0
              3 STORE_FAST               1 (powers)

 15           6 LOAD_CONST               1 (1)
              9 STORE_FAST               2 (i)

 16          12 SETUP_LOOP              52 (to 67)
        >>   15 LOAD_FAST                2 (i)
             18 LOAD_FAST                0 (num)
             21 COMPARE_OP               1 (<=)
             24 POP_JUMP_IF_FALSE       66

 17          27 LOAD_FAST                2 (i)
             30 LOAD_FAST                0 (num)
             33 BINARY_AND
             34 POP_JUMP_IF_FALSE       53

 18          37 LOAD_FAST                1 (powers)
             40 LOAD_ATTR                0 (append)
             43 LOAD_FAST                2 (i)
             46 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             49 POP_TOP
             50 JUMP_FORWARD             0 (to 53)

 19     >>   53 LOAD_FAST                2 (i)
             56 LOAD_CONST               1 (1)
             59 INPLACE_LSHIFT
             60 STORE_FAST               2 (i)
             63 JUMP_ABSOLUTE           15
        >>   66 POP_BLOCK

 20     >>   67 LOAD_FAST                1 (powers)
             70 RETURN_VALUE
None

moose:
===========================
 44           0 LOAD_CONST               1 (<code object <lambda> at 0x0000000002A8E660, file "power_2_adder.py", line 44>)
              3 LOAD_CONST               2 ('moose.<locals>.<lambda>')
              6 MAKE_FUNCTION            0
              9 STORE_FAST               1 (get_bin)

 45          12 LOAD_FAST                1 (get_bin)
             15 LOAD_FAST                0 (num)
             18 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             21 STORE_FAST               2 (bin_str)

 46          24 BUILD_LIST               0
             27 STORE_FAST               3 (powers)

 47          30 SETUP_LOOP              71 (to 104)
             33 LOAD_GLOBAL              0 (enumerate)
             36 LOAD_FAST                2 (bin_str)
             39 LOAD_CONST               0 (None)
             42 LOAD_CONST               0 (None)
             45 LOAD_CONST               6 (-1)
             48 BUILD_SLICE              3
             51 BINARY_SUBSCR
             52 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             55 GET_ITER
        >>   56 FOR_ITER                44 (to 103)
             59 UNPACK_SEQUENCE          2
             62 STORE_FAST               4 (i)
             65 STORE_FAST               5 (digit)

 48          68 LOAD_FAST                5 (digit)
             71 LOAD_CONST               4 ('1')
             74 COMPARE_OP               2 (==)
             77 POP_JUMP_IF_FALSE       56

 49          80 LOAD_FAST                3 (powers)
             83 LOAD_ATTR                1 (append)
             86 LOAD_CONST               5 (2)
             89 LOAD_FAST                4 (i)
             92 BINARY_POWER
             93 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             96 POP_TOP
             97 JUMP_ABSOLUTE           56
            100 JUMP_ABSOLUTE           56
        >>  103 POP_BLOCK

 50     >>  104 LOAD_FAST                3 (powers)
            107 RETURN_VALUE
None

t3_enum:
===========================
 23           0 BUILD_LIST               0
              3 STORE_FAST               1 (d)

 24           6 SETUP_LOOP             101 (to 110)
        >>    9 LOAD_GLOBAL              0 (sum)
             12 LOAD_FAST                1 (d)
             15 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             18 LOAD_FAST                0 (num)
             21 COMPARE_OP               0 (<)
             24 POP_JUMP_IF_FALSE      109

 25          27 LOAD_GLOBAL              1 (powers_of_2)
             30 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
             33 STORE_FAST               2 (p)

 26          36 LOAD_CONST               1 (1)
             39 DUP_TOP
             40 STORE_FAST               3 (a)
             43 STORE_FAST               4 (b)

 27          46 SETUP_LOOP              44 (to 93)
        >>   49 LOAD_GLOBAL              0 (sum)
             52 LOAD_FAST                1 (d)
             55 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             58 LOAD_FAST                3 (a)
             61 BINARY_ADD
             62 LOAD_FAST                0 (num)
             65 COMPARE_OP               1 (<=)
             68 POP_JUMP_IF_FALSE       92

 28          71 LOAD_FAST                3 (a)
             74 STORE_FAST               4 (b)

 29          77 LOAD_GLOBAL              2 (next)
             80 LOAD_FAST                2 (p)
             83 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             86 STORE_FAST               3 (a)
             89 JUMP_ABSOLUTE           49
        >>   92 POP_BLOCK

 30     >>   93 LOAD_FAST                1 (d)
             96 LOAD_ATTR                3 (append)
             99 LOAD_FAST                4 (b)
            102 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            105 POP_TOP
            106 JUMP_ABSOLUTE            9
        >>  109 POP_BLOCK

 31     >>  110 LOAD_FAST                1 (d)
            113 LOAD_ATTR                4 (reverse)
            116 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
            119 POP_TOP

 32         120 LOAD_FAST                1 (d)
            123 RETURN_VALUE
None
gbriones_gdl:
===========================
 41           0 LOAD_CONST               1 (<code object <listcomp> at 0x0000000002A8E540, file "power_2_adder.py", line 41>)
              3 LOAD_CONST               2 ('t3_enum.<locals>.<listcomp>')
              6 MAKE_FUNCTION            0
              9 LOAD_GLOBAL              0 (enumerate)
             12 LOAD_GLOBAL              1 (bin)
             15 LOAD_FAST                0 (num)
             18 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             21 LOAD_CONST               0 (None)
             24 LOAD_CONST               3 (1)
             27 LOAD_CONST               4 (-1)
             30 BUILD_SLICE              3
             33 BINARY_SUBSCR
             34 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             37 GET_ITER
             38 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             41 RETURN_VALUE
None

t3_gen:
===========================
  6           0 BUILD_LIST               0
              3 STORE_FAST               1 (result)

  7           6 LOAD_GLOBAL              0 (bin)
              9 LOAD_FAST                0 (num)
             12 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             15 LOAD_CONST               0 (None)
             18 LOAD_CONST               1 (1)
             21 LOAD_CONST               3 (-1)
             24 BUILD_SLICE              3
             27 BINARY_SUBSCR
             28 STORE_FAST               2 (binary)

  8          31 SETUP_LOOP              62 (to 96)
             34 LOAD_GLOBAL              1 (range)
             37 LOAD_GLOBAL              2 (len)
             40 LOAD_FAST                2 (binary)
             43 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             46 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             49 GET_ITER
        >>   50 FOR_ITER                42 (to 95)
             53 STORE_FAST               3 (x)

  9          56 LOAD_GLOBAL              3 (int)
             59 LOAD_FAST                2 (binary)
             62 LOAD_FAST                3 (x)
             65 BINARY_SUBSCR
             66 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             69 POP_JUMP_IF_FALSE       50

 10          72 LOAD_FAST                1 (result)
             75 LOAD_ATTR                4 (append)
             78 LOAD_CONST               2 (2)
             81 LOAD_FAST                3 (x)
             84 BINARY_POWER
             85 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             88 POP_TOP
             89 JUMP_ABSOLUTE           50
             92 JUMP_ABSOLUTE           50
        >>   95 POP_BLOCK

 11     >>   96 LOAD_FAST                1 (result)
             99 RETURN_VALUE
None

---

From the timeit results, we can see that @nullptr's solution is quite nice, as I suspected, followed by @moose's solution. After that came my combination of @moose's and @gbriones.gdl's solutions, followed very closely by @gbriones.gdl's solution. My generator solution was, shall we say, very suboptimal, but I kind of expected that.

dis results are included for completeness.

Answer 3

One simple (but really not effective) way of doing this is to use backtracking. Note that the closest power of two is easily founded by using math.log function (The closest power of two of n is 2^round(log(n, 2))):

from math import log

def powers_finder(n):
    return powers_finder_rec(n, [2**x for x in range(round(log(n, 2)+1))])

def powers_finder_rec(n, powers):
    if sum(powers) == n:
        return powers

    for i, j in enumerate(powers):
        (res1, res2) = (powers_finder_rec(n-j, powers[:i] + powers[i+1:]),  
                                    powers_finder_rec(n, powers[:i] + powers[i+1:]))
        if res1 or res2:
            return [j] + res1 if res1 else res2

    return []

print(powers_finder(13))
print(powers_finder(112))

Output:

[1, 4, 8]
[16, 32, 64]

Answer 4

Try with binaries:

def power_find(n):
    result = []
    binary = bin(n)[:1:-1]
    for x in range(len(binary)):
        if int(binary[x]):
            result.append(2**x)
    return result

>>> power_find(11)
[1, 2, 8]

Answer 5

Rather than solve the problem, how about some information to help you solve it? Take a look at a few examples, and solve them. Here are a few,

Suppose N=2, then the answer is = {2=2^1}.

Suppose N=3, then the answer is = {2=2^1,1=2^0} (note that 2**0=1)

Suppose N=4, then the answer is = {4=2^2}

...

Suppose N=63, then the answer is = {32=2^5, 16=2^4, 8=2^3, 4=2^2, 2=2^1, 1=2^0}

Suppose N=64, then the answer is = {64=2^6}

...

Suppose N=259, then the answer is = {256=2^8, 2=2^1, 1=2^0}

Do you see the pattern?

---

Want an algorithm?

Think about these simple steps, and combine them together in a loop,

Can you check if the number is odd? When the number is odd, then you have detected a bit 'on'. Subtract one (make the number even).

Can you divide by 2? What do you do with the result?

Answer 6

The idea is to convert the number to binary and then get powers of two from the binary representation:

#!/usr/bin/env python


def get_powers(n):
    """Get positive powers of two which add up to n.

    Parameters
    ----------
    n : positive integer

    Returns
    -------
    list of integers which are powers of 2

    Examples
    --------
    >>> get_powers(14)
    [2, 4, 8]

    >>> get_powers(5)
    [1, 4]
    """
    get_bin = lambda x: x >= 0 and str(bin(x))[2:] or "-" + str(bin(x))[3:]
    bin_str = get_bin(n)  # convert n to a binary string
    powers = []
    for i, digit in enumerate(bin_str[::-1]):
        if digit == '1':
            powers.append(2**i)
    return powers