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
"1", and create the list with list comprehension. It could be done in one statement.
return [ 1 << idx for idx, bit in enumerate(bin(num)[:1:-1]) if bit == "1" ]
bin() actually returns a string prefixed with
"0b". The above code skips the prefix, by using an end index in the slice:
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.
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
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."