Как разложить число на 2?

Question

Я пытаюсь создать функцию, которая получает число в качестве аргумента и выполняет действия на этом номере, чтобы узнать его ближайшие полномочия 2, которые затем будут добавлены к этому числу. Например, если пользователь вводит 4, функция добавит 4, потому что она уже имеет силу 2. Если пользователь вводит 14, функция должна видеть, что 14 не является силой 2 и ближайшими степенями 2, которые составляют 14 - 2,4 и 8.

Ключевые примечания: Я добираюсь до 2^9.

Что я до сих пор:

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) 

Проблема здесь в том случае, если пользователь вводит в позволяет сказать, 5, как (п) 5 состоит из мощности 2^2 = 4 и 2^0 = 1 4 + 1 = 5. Как я могу расширить свою функцию, включив этот процесс?

спасибо!

Answer 1

Один простой (но действительно не эффективный) способ сделать это - использовать обратное отслеживание. Обратите внимание, что ближайшая степень двойки легко основана с помощью math.log функции (Ближайший мощность двух п является 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)) 

Выход:

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

Answer 2

Идея заключается в том, чтобы преобразовать число до двоичного, а затем получить полномочия двух из двоичного представления:

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

Попробуйте использовать двоичные файлы:

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

Самый лучший и быстрый способ сделать это, конечно же, с двоичными числами, но вот способ с генератором:

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

Вместо того, чтобы решить эту проблему , как насчет некоторой информации, которая поможет вам решить эту проблему? Взгляните на несколько примеров и решите их. Вот несколько,

Предположим, что N = 2, тогда ответ = {2 = 2^1}.

Пусть N = 3, то ответ = {2 = 2^1,1 = 2^0} (заметим, что 2 ** 0 = 1)

Пусть N = 4, то ответ = {4 = 2^2}

...

Пусть N = 63, то ответ = {32 = 2^5, 16 = 2^4, 8 = 2^3, 4 = 2^2, 2 = 2^1, 1 = 2^0}

Пусть N = 64, то ответ = {64 = 2^6}

...

Пусть N = 259, то ответ = {256 = 2^8, 2 = 2^1, 1 = 2^0}

Вы видите картину?

---

Хотите алгоритм?

Подумайте об этих простых шагов, и объединить их вместе в цикле,

Вы можете проверить, если число нечетное? Когда число нечетное, вы обнаружите бит «включено». Вычтите один (сделайте число четным).

Можете вы делиться на 2? Что вы делаете с результатом?

Answer 6

Следующее бинарное решение сочетает в себе @ использовании лосиного из enumerate() с @ gbriones.gdl также для использования шага индексации и @ gbriones.gdl в комментарии об одном-выравнивая его (на самом деле, это был комментарий о не один-выравнивая его, но однострочное развлечение).

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

Answer 7

Наиболее эффективный способ сделать это:

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

Answer 8

У нас есть некоторые хорошие ответы на этот вопрос в настоящее время. Я решил, что проанализирую их немного с dis и timeit.

Вот тестовый код, который я использовал:

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

---

И вот результаты:

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 

---

Из timeit результатов, мы можем увидеть решение, которое @ nullptr в довольно неплохо, как я подозревал, а затем решение @ moose. После этого появилась моя комбинация решений @ moose и @ gbriones.gdl, которые очень внимательно следили за решением @ gbriones.gdl. Мое решение генератора было, скажем так, очень субоптимальным, но я ожидал такого.

dis Результаты включены в комплектность.