The code below isn't working right for some inputs.
a, i = set(), 1
while i <= 10000:
a.add(i)
i <<= 1
N = int(input())
if N in a:
print("True")
else:
print("False")
My initial idea was to check for each input if it's a power of 2 by starting from 1 and multiplying by 2 until exceeding the input number, comparing at each step. Instead, I store all the powers of 2 in a set beforehand, in order to check a given input in O(1). How can this be improved?
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 functionsYou 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(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 Falsemath.log2(2**49-1).is_integer() will give Truemath.frexp(2**53+1)[0] == 0.5 will give True!!This is because math functions use floats, and those have an inherent accuracy problem.
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
logwithbase=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).
Refer to the excellent and detailed answer to "How to check if a number is a power of 2" — for C#. The equivalent Python implementation, also using the "bitwise and" operator &, is this:
def is_power_of_two(n):
return (n != 0) and (n & (n-1) == 0)
As Python has arbitrary-precision integers, this works for any integer n as long as it fits into memory.
To summarize briefly the answer cited above: The first term, before the logical and operator, simply checks if n isn't 0 — and hence not a power of 2. The second term checks if it's a power of 2 by making sure that all bits after that bitwise & operation are 0. The bitwise operation is designed to be only True for powers of 2 — with one exception: if n (and thus all of its bits) were 0 to begin with.
To add to this: As the logical and "short-circuits" the evaluation of the two terms, it would be more efficient to reverse their order if, in a particular use case, it is less likely that a given n be 0 than it being a power of 2.
In binary representation, a power of 2 is a 1 (one) followed by zeros. So if the binary representation of the number has a single 1, then it's a power of 2. No need here to check num != 0:
print(1 == bin(num).count("1"))
The bin builtin returns a string "0b1[01]?" (regex notation) for every strictly positive integer (if system memory suffices, that is), so that we can write the Boolean expression
'1' not in bin(abs(n))[3:]
that yields True for n that equals 0, 1 and 2**k.
1 is 2**0 so it is unquestionably a power of two, but 0 is not, unless you take into account the limit of x=2**k for k → -∞. Under the second assumption we can write simply
check0 = lambda n: '1' not in bin(abs(n))[3:]
and under the first one (excluding 0)
check1 = lambda n: '1' not in bin(abs(n))[3:] and n != 0
Of course the solution here proposed is just one of the many possible ones that
you can use to check if a number is a power of two... and for sure not the most
efficient one but I'm posting it in the sake of completeness :-)
Note: this should be a comment on Tomerikoo's answer (currently the most upvoted) but unfortunately Stack Overflow won't let me comment due to reputation points.
Tomerikoo's answer is very well explained and thought-out. While it covers most applications, but I believe needs a slight modification to make it more robust against a trivial case. Their answer is:
(n & (n-1) == 0) and n != 0
The second half checks if the input is an actual 0 which would invalidate the bitwise-and logic. There is another one trivial case when this could happen: input is 1 and the bitwise-and takes place with 0 again, just on the second term. Strictly speaking, 2^0=1 of course but I doubt that it's useful for most applications. A trivial modification to account for that would be:
(n & (n-1) == 0) and (n != 0 and n-1 != 0)
The following code checks whether n is a power of 2 or not:
def power_of_two(n):
count = 0
st = str(bin(n))
st = st[2:]
for i in range(0,len(st)):
if(st[i] == '1'):
count += 1
if(count == 1):
print("True")
else:
print("False")
Many beginners won't know how code like (n != 0) and (n & (n-1) == 0) works.
But if we want to check whether a number is a power of 2 or not, we can convert the number to binary format and see it pretty clearly.
For Example:
^ (to the power of)
2^0 = 1 (Bin Value : 0000 0001)
2^1 = 2 (Bin Value : 0000 0010)
2^2 = 4 (Bin Value : 0000 0100)
2^3 = 8 (Bin Value : 0000 1000)
2^4 = 16 (Bin Value : 0001 0000)
2^5 = 32 (Bin Value : 0010 0000)
2^6 = 64 (Bin Value : 0100 0000)
2^7 = 128 (Bin Value : 1000 0000)
If you look at the binary values of all powers of 2, you can see that there is only one bit True. That's the logic in this program.
So If we count the number of 1 bit's in a binary number and if it is equal to 1, then the given number is power of 2, otherwise it is not.
n = int(input())
if '1' in list(bin(n))[3:]: #also can use if '1' in bin(n)[3:] OR can also use format(n, 'b')[1:]
print("False")
else:
print("True")
For every number which is power of 2 say(N = 2^n), where n = +integer bin(N)=bin(2^(+int)) will have string of form: 0b10000000 e.i 0b1.....zero only if not 0, N is not power of 2.
Also, format(n, 'b') returns bin(n)[2:] so can be used
>>> format(14, '#b'), format(14, 'b')
('0b1110', '1110')
>>> f'{14:#b}', f'{14:b}'
('0b1110', '1110')
Use *2 instead of bit shifts. Multiplication or addition are much more readable.
Most of the above answers use bin() of format(int(input()), "b")
The below code also works: Ev(x) returns True if x is power of 2
# Ev(x) ~ ispoweroftwo(x)
def Ev(x):
if x==2: return True
elif x%2: return False
return Ev(x//2)
The above code is based on generating bin()
#This function returns binary of integers
def binary(x):
a = ""
while x!= 0:
a += str(x%2)
x = x//2
return a[::-1]
I = int(input())
print(format(I, "b")) # To cross-check if equal of not
print(binary(I))
I have tried to add my answer because I found what we are doing using bin(x)[3:] or format(x, "b") is almost like asking the boolean answer of whether or not a given number x is divisible by two.....and we keep asking the same
