What Is The Fastest Way To Represent Number As The Sum Of Powers Of Two In Python

For example >>> two_powers(42) >>> (2, 8, 32) My current naive implementation (taken from here) looks like that def two_powers(num): return tuple(2 ** i for

Solution 1:

Try this:

def two_powers(num):
    powers = []
    while num != 0:
        powers.append(num & -num)
        num = num & (num - 1)
    return powers

Solution 2:

Your solution is good actually, with a slight (big!) detail of efficiency:

Use

1<<i 

(bitwise shift) instead of

2**i

So, to copy you, consider the following :

deftwo_powers(num):
    returnset(1 << i for i, j inenumerate(bin(num)[-1: 1: -1]) if j == '1')
print two_powers(42)

Solution 3:

You can make use of the log2 and generator expression until you are run out of powers of two.

import math

deftwo_powers(num):
    while num > 0:
        power = int(math.log(num, 2))
        yield2**power
        num = num - 2**power

Sample run:

>>>tuple(two_powers(42)))
(32, 8, 2)
>>>tuple(two_powers(43)))
(32, 8, 2, 1)

Solution 4:

You can do this:

import math

def two_powers(num):
    # Compute number of bits for big numbers
    num_bits = math.floor(math.log2(num)) + 1 if num >= (1 << 32) else 32# Take those bits where there is a "one" in the numberreturn [1 << p for pin range(num_bits) if num & (1 << p)]

print(two_powers(42))
# [2, 8, 32]

EDIT: Wrt the number of bits, you can make more splits if you are really concerned about performance, either down to save iterations or up to avoid computing the logarithm (or if you know your input numbers are going to be in some particular range):

import math

def two_powers(num):
    # Compute number of bits for big numbersif num < (1 << 8):
        num_bits = 8elif num < (1 << 16):
        num_bits = 16elif num < (1 << 24):
        num_bits = 24elif num < (1 << 32):
        num_bits = 32else:
        num_bits = math.floor(math.log2(num)) + 1
    # Take those bits where there is a "one" in the numberreturn [1 << p for pin range(num_bits) if num & (1 << p)]

print(two_powers(42))
# [2, 8, 32]

Solution 5:

You can use a generator with a shifting bit mask:

deftwo_powers(n):
    m = 1while n >= m:
        if n & m:
            yield m
        m <<= 1

So that:

tuple(two_powers(42))

would be:

(2, 8, 32)