Collecting the 2-power decomposition of n (Python, C++)

Question

I am writing a quick program to decompose a number into powers of 2. Is this an efficient way to do it:

    pows=[]
    pos = 0
    while n>0:
        if n%2==1: pows.append(2**pos)
        n/=2
        pos+=1

I've written this in Python but I'm also interested in how it's done in C++.

I don't know if this is a "smart" way to do it or if it's considered horribly inefficient.

You can make it more efficient by accumulating the actual power of 2 instead of the exponent. That way you avoid computing 2**pos. (i.e. start with `power = 1` and then in every loop do: `power += power` (or `power *= 2`). Also, in python3 `n /= 2` is not integer division, if you care about python3. — rici, Nov 25 '13 at 16:39
@user111373 _'Is it faster to use "bitmasks"?'_ Yes,defnitely! See James Kanze's answer. — πάντα ῥεῖ, Nov 25 '13 at 17:14

score 1 · Answer 1 · answered Nov 25 '13 at 16:38

1

Any modern compiler is probably going to be smart enough to optimize this. Get your code to run correctly first, and worry about optimizing for speed after profiling (if it is too slow).

answered Nov 25 '13 at 16:38

zennehoy

6,405
28
55

The Python expression `2**pos` would be `pow(2, pos)` in C++. I'd be very surprised if an optimizer eliminated it, and it will probably represent a very large percentage of his CPU. I'd generally argue very strongly against premature optimization, but in this case: never introduce floating point unless you have to is an even more important rule. – James Kanze Nov 25 '13 at 17:15
@JamesKanze 2**pos should of course be implemented as (1< – zennehoy Nov 25 '13 at 17:23
@zennehoy is 2** or 1<< faster in Python? – user111373 Nov 25 '13 at 18:02
@user111373 Since both are built-in operators, they should both compile to the same byte-code (shift left in this case). Similarly, `n%2` should be optimized to `n&1`, and `n/=2` should be optimized to `n>>1`. This is all stuff a decent compiler should do for you. – zennehoy Nov 26 '13 at 08:25

score 1 · Accepted Answer · answered Nov 25 '13 at 17:12

The most natural implementation in C++ would use a bit mask for the powers of two, something like:

std::vector<unsigned> p2;
unsigned m = 1;
while ( m != 0 ) {
    if ( (m & i) != 0 ) {
        p2.push_back( m );
    }
    m <<= 1;
}

You certainly don't want to call the pow function each time in the loop. A somewhat trickery way, which is likely faster (since it will usually pass less times in the loop) would be:

std::vector<unsigned> p2;
std::cout << i << ": ";
while ( i != 0 ) {
    unsigned n = i & i - 1;
    p2.push_back( i ^ n );
    i = n;
}

I would recommend the first (which is readily understandable) unless the profiler really says you must use the second.

Collecting the 2-power decomposition of n (Python, C++)

2 Answers2