Python and Powers Math

How to check if a given number is a power of two?

Bit Manipulations

One approach would be to use bit manipulations:

(n & (n-1) == 0) and n != 0

Explanation: every power of 2 has exactly 1 bit set to 1 (the bit in that number's log base-2 index). So when subtracting 1 from it, that bit flips to 0 and all preceding bits flip to 1. That makes these 2 numbers the inverse of each other so when AND-ing them, we will get 0 as the result.

For example:

                    n = 8

decimal |   8 = 2**3   |  8 - 1 = 7   |   8 & 7 = 0
        |          ^   |              |
binary  |   1 0 0 0    |   0 1 1 1    |    1 0 0 0
        |   ^          |              |  & 0 1 1 1
index   |   3 2 1 0    |              |    -------
                                           0 0 0 0
-----------------------------------------------------
                    n = 5

decimal | 5 = 2**2 + 1 |  5 - 1 = 4   |   5 & 4 = 4
        |              |              |
binary  |    1 0 1     |    1 0 0     |    1 0 1
        |              |              |  & 1 0 0
index   |    2 1 0     |              |    ------
                                           1 0 0

So, in conclusion, whenever we subtract one from a number, AND the result with the number itself, and that becomes 0 - that number is a power of 2!

Of course, AND-ing anything with 0 will give 0, so we add the check for n != 0.

math functions

You could always use math functions, but notice that using them without care could cause incorrect results:

• math.log(x[, base]) with base=2:

  import math
  
  math.log(n, 2).is_integer()
  

• math.log2(x):

  math.log2(n).is_integer()
  

Worth noting that for any n <= 0, both functions will throw a ValueError as it is mathematically undefined (and therefore shouldn't present a logical problem).

• math.frexp(x):
  

  abs(math.frexp(n)[0]) == 0.5
  

As noted above, for some numbers these functions are not accurate and actually give FALSE RESULTS:

• math.log(2**29, 2).is_integer() will give False
• math.log2(2**49-1).is_integer() will give True
• math.frexp(2**53+1)[0] == 0.5 will give True!!

This is because math functions use floats, and those have an inherent accuracy problem.

(Expanded) Timing

Some time has passed since this question was asked and some new answers came up with the years. I decided to expand the timing to include all of them.

According to the math docs, the log with a given base, actually calculates log(x)/log(base) which is obviously slow. log2 is said to be more accurate, and probably more efficient. Bit manipulations are simple operations, not calling any functions.

So the results are:

Ev: 0.28 sec

log with base=2: 0.26 sec

count_1: 0.21 sec

check_1: 0.2 sec

frexp: 0.19 sec

log2: 0.1 sec

bit ops: 0.08 sec

The code I used for these measures can be recreated in this REPL (forked from this one).

What is the fastest way to calculate / create powers of ten?

You're comparing apples to oranges here. 10 ** n computes an integer (when n is non-negative), whereas float(f'1e{n}') computes a floating-point number. Those won't take the same amount of time, but they solve different problems so it doesn't matter which one is faster.

But it's worse than that, because there is the overhead of calling a function, which is included in your timing for all of your alternatives, but only some of them actually involve calling a function. If you write 10 ** n then you aren't calling a function, but if you use partial(pow, 10) then you have to call it as a function to get a result. So you're not actually comparing the speed of 10 ** n fairly.

Instead of rolling your own timing code, use the timeit library, which is designed for doing this properly. The results are in seconds for 1,000,000 repetitions (by default), or equivalently they are the average time in microseconds for one repetiton.

Here's a comparison for computing integer powers of 10:

>>> from timeit import timeit
>>> timeit('10 ** n', setup='n = 500')
1.09881673199925
>>> timeit('pow(10, n)', setup='n = 500')
1.1821871869997267
>>> timeit('f(n)', setup='n = 500; from functools import partial; f = partial(pow, 10)')
1.1401332350014854

And here's a comparison for computing floating-point powers of 10: note that computing 10.0 ** 500 or 1e500 is pointless because the result is simply an OverflowError or inf.

>>> timeit('10.0 ** n', setup='n = 200')
0.12391662099980749
>>> timeit('pow(10.0, n)', setup='n = 200')
0.17336435099969094
>>> timeit('f(n)', setup='n = 200; from functools import partial; f = partial(pow, 10.0)')
0.18887039500077663
>>> timeit('float(f"1e{n}")', setup='n = 200')
0.44305286100097874
>>> timeit('np.power(10.0, n, dtype=float)', setup='n = 200; import numpy as np')
1.491982370000187
>>> timeit('f(n)', setup='n = 200; from functools import partial; import numpy as np; f = partial(np.power, 10.0, dtype=float)')
1.6273324920002779

So the fastest of these options in both cases is the obvious one: 10 ** n for integers and 10.0 ** n for floats.

Related Topics