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 :

def two_powers(num):
    return set(1 << i for i, j in enumerate(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

def two_powers(num):
    while num > 0:
        power = int(math.log(num, 2))
        yield 2**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 number
    return [1 << p for p in 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 numbers
    if num < (1 << 8):
        num_bits = 8
    elif num < (1 << 16):
        num_bits = 16
    elif num < (1 << 24):
        num_bits = 24
    elif num < (1 << 32):
        num_bits = 32
    else:
        num_bits = math.floor(math.log2(num)) + 1
    # Take those bits where there is a "one" in the number
    return [1 << p for p in 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:

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

So that:

tuple(two_powers(42))

would be:

(2, 8, 32)