3
\$\begingroup\$

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 ?

\$\endgroup\$
9
  • \$\begingroup\$ What version of Python do you use and what is your actual problem statement? Why do you need a list? In what format do you want the result? \$\endgroup\$
    – Mast
    Aug 11, 2018 at 8:45
  • 1
    \$\begingroup\$ @Mast I have python 3.6. 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. \$\endgroup\$ Aug 11, 2018 at 8:46
  • 1
    \$\begingroup\$ You could probably turn it into a one-liner generator statement, which creates the list for you. But I'm not well-versed enough in those to figure out how. \$\endgroup\$
    – Mast
    Aug 11, 2018 at 9:04
  • \$\begingroup\$ @Mast Even I couldn't do it. \$\endgroup\$ Aug 11, 2018 at 9:06
  • 1
    \$\begingroup\$ One important question to ask yourself is is this actually a performance bottleneck. Surely you don't want to be doing something to very negatively affects performance, but often in Python code that is more idiomatic is better than obfuscated code that performs better (unless this code is on a critical path). \$\endgroup\$ Aug 24, 2018 at 12:56

3 Answers 3

5
\$\begingroup\$

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:

enter image description here

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."

\$\endgroup\$
5
  • \$\begingroup\$ That involves creating a string. Is it actually faster than a loop that just does arithmetic? \$\endgroup\$ Aug 11, 2018 at 19:51
  • \$\begingroup\$ @200_success I can’t claim it will be faster. In fact, I haven’t even run the code; I just typed it in on my phone. However, it does address the questions: “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? \$\endgroup\$
    – AJNeufeld
    Aug 11, 2018 at 20:45
  • \$\begingroup\$ @AJNeufeld, harold's solution is faster, I checked it using timeit \$\endgroup\$ Aug 12, 2018 at 4:07
  • 2
    \$\begingroup\$ Harold's solution is faster only for some numbers "(depending on the size and sparseness of the input)". When testing 31-bit numbers (0x4#######) with 24 or more 1-bits, my solution is faster; with 23 or less 1-bits, Harold's is faster. \$\endgroup\$
    – AJNeufeld
    Aug 12, 2018 at 23:05
  • 1
    \$\begingroup\$ @200_success Apparently, the "creating a string" method can actually be faster. \$\endgroup\$
    – AJNeufeld
    Aug 13, 2018 at 19:03
5
\$\begingroup\$

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.

\$\endgroup\$
-1
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ Readability is not an issue. Can you please show me how I can "allocate memory for a list before filling it" \$\endgroup\$ Aug 11, 2018 at 10:42
  • \$\begingroup\$ It depends on context. If you know boundaries for num you could just allocate result = maxSize * [None] and fill it. It will be significantly faster than .appending. Maybe you should take a look at docs.python.org/3/library/stdtypes.html#int.to_bytes \$\endgroup\$
    – Nondv
    Aug 11, 2018 at 11:05
  • \$\begingroup\$ Just to be clear: I don't really know python. I used it like 5 years ago when studied at school \$\endgroup\$
    – Nondv
    Aug 11, 2018 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.