Wie zerlege ich eine Zahl in Potenzen von 2?

Question

Ich versuche, eine Funktion zu erstellen, die eine Zahl als Argument erhält und Aktionen an dieser Nummer ausführt, um ihre nächstliegenden Zweierpotenzen zu ermitteln, die sich dann zu dieser Zahl addieren. Zum Beispiel, wenn der Benutzer 4 eingibt, wird die Funktion 4 anhängen, weil es bereits eine Potenz von 2 ist. Wenn der Benutzer eine 14 eingibt, sollte die Funktion sehen, dass 14 keine Potenz von 2 und die nächsten Potenz von 2 ist 14 sind 2,4 und 8.

Key notes: Ich gehe nur bis 2^9.

Was ich bisher:

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) 

Das Problem hier ist, wenn der Benutzer läßt tritt in 5 sagen, wie (n) 5 besteht aus dem Strom 2^2 = 4 und 2^0 = 1 4 + 1 = 5. Wie kann ich meine Funktion um diesen Prozess erweitern?

danke!

Answer 1

Ein einfacher (aber wirklich nicht effektiver) Weg ist Backtracking. Beachten Sie, dass die nächste Potenz von zwei leicht mit math.log Funktion beruht (die nächste Zweierpotenz von n ist 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)) 

Ausgang:

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

Answer 2

Die Idee zu konvertieren ist die Nummer zu Binär und dann erhalten Potenzen von zwei aus der Binärdarstellung:

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

Answer 3

Versuchen Sie mit Binärdateien:

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 4

Die beste und schnellste Weg, dies zu tun, natürlich, mit binären Zahlen, aber hier ist ein Weg, um mit einem 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 5

Anstatt das Problem zu lösen , wie wäre es mit ein paar Informationen, um Ihnen zu helfen, es zu lösen? Schau dir ein paar Beispiele an und löse sie. Hier sind ein paar,

Angenommen N = 2, dann ist die Antwort = {2 = 2^1}.

Es sei N = 3, dann ist die Antwort = ist {2 = 2^2^1,1 = 0} (beachten Sie, dass 2 ** 0 = 1)

Es sei N = 4 ist, dann ist die Antwort = {4 = 2^2}

...

Es sei N = 63, dann ist die Antwort = {32 = 2^5, 2^16 = 4, 8 = 2^3, 4 = 2^2, 2 = 2^1, 1 = 2^0}

Es sei N = 64, dann ist die Antwort = {64 = 2^6}

...

Es sei N = 259, dann ist die Antwort = {256 = 2^8, 2 = 2^1, 1 = 2^0}

Haben Sie das Muster sehen?

---

Wollen Sie einen Algorithmus?

Denken Sie über diese einfachen Schritte, und sie zusammen in einer Schleife kombinieren,

Können Sie überprüfen, ob die Zahl ungerade ist? Wenn die Nummer ungerade ist, dann haben Sie ein bisschen 'an' erkannt. Subtrahiere einen (mache die Zahl gerade).

Können Sie durch 2 teilen? Was machst du mit dem Ergebnis?

Answer 6

Die folgende binäre Lösung kombiniert @ Verwendung der Elch von enumerate() mit @ gbriones.gdl die Verwendung von Schritt Indizierung und Kommentar des @ gbriones.gdl etwa ein Futter es (eigentlich war es ein Kommentar über nicht one-Futter es, aber One-Lining macht Spaß.

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

Answer 7

effizienteste Weg, dies zu tun:

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

Answer 8

Wir haben einige nette Antworten für diese jetzt Frage. Ich dachte, ich würde sie ein wenig mit dis und timeit analysieren.

Hier ist der Testcode I verwendet:

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

---

Und hier sind die Ergebnisse:

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 

---

Aus den timeit Ergebnissen können wir, dass @ nullptr-Lösung sehen ist ganz nett, wie ich vermutet habe, gefolgt von @moose's Lösung. Danach kam meine Kombination aus @ eloses und @ gbriones.gdl's Lösungen, dicht gefolgt von @ gbriones.gdl's Lösung. Meine Generatorlösung war, sagen wir, sehr suboptimal, aber das hatte ich irgendwie erwartet.

dis Ergebnisse sind zur Vollständigkeit enthalten.