Menu
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!
506
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.
117
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]
Most efficient way of doing this:
def myfunc(x):
powers = []
i = 1
while i <= x:
if i & x:
powers.append(i)
i <<= 1
return powers
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
