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])
withbase=2
:import math math.log(n, 2).is_integer()
-
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 giveFalse
math.log2(2**49-1).is_integer()
will giveTrue
math.frexp(2**53+1)[0] == 0.5
will giveTrue
!!
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
withbase=2
: 0.26 seccount_1: 0.21 sec
check_1: 0.2 sec
frexp
: 0.19 sec
log2
: 0.1 secbit ops: 0.08 sec
The code I used for these measures can be recreated in this REPL (forked from this one).