Express a number as a sum of powers of 2

Question

This is my function:

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

I have python 3.6(Windows 10 64-bit). I want the result in the form of a list. My problem statement is to express a integer(num) in the form of sum of powers of 2.

Do I have to create a list in the beginning and then append to it each time ? Can I return a list directly without creating it in the beginning ?

This will will speed up my execution time, right ?

Answer 1

It is probably cheating, but the bin(x) function would do most of the heavy lifting, converting x into a string of bits. Iterate in the reverse direction (via [::-1]) to match bits with their proper two-to-the-power-of index, select only those indices where bit is "1", and create the list with list comprehension. It could be done in one statement.

def two_powers(num):
    return [ 1 << idx for idx, bit in enumerate(bin(num)[:1:-1]) if bit == "1" ]

Note: bin() actually returns a string prefixed with "0b". The above code skips the prefix, by using an end index in the slice: [:1:-1].

---

As @200_success mentions, creating and decimating the binary string might not be the most efficient approach. A bit of research turned up int.bit_length() which can be used to determine an upper bound in the range() for list comprehension. Improved solution:

def two_powers(num):
    return [ 1 << idx for idx in range(num.bit_length()) if num & (1 << idx) ]

---

Timing for the original method, Harold's, and my method, on 32 & 64 bit numbers, with most significant bit set, for various density of 1 bits:

As can be seen, and as expected, Harold's method is best when there are more zero bits than one bits. With more one bits than zero bits, it can perform worse than the original. The list comprehension method is always slightly better than the original, but not by a lot.

The real surprise is the bin(num) version, which converts the number to a string. I threw that into my timing for a laugh, and it turned out to be way better than my improved version. Moral of the story: "Test it! Don't guess."

Answer 2

List building performance aside, there is a way to get the powers of two out without touching the bits in between, by using the formulas:

isolateLowestSetBit(x) = x & -x
resetLowestSetBit(x) = x & (x - 1)

These have been explained elsewhere.

Using those definitions, you can extract the powers of two like this:

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

Since it potentially avoids testing many bits (depending on the size and sparseness of the input) it may be faster. It can also work out not so well, for very dense numbers.

Answer 3

I think that list generator won't improve your performance in this case because it will require you to create another list (since range is not a good fit for this). You could create a generator that yields powers but it basically will be moving one piece of code to another function

So I don't think you can optimize this. Unless you allocate memory for a list before filling it but it won't improve readability.

IMHO

UPD. maybe this will be helpful: https://docs.python.org/3/library/stdtypes.html#int.to_bytes