Power of Two
You get an integer n. Return true if n is a power of two, meaning n = 2^k for some whole number k ≥ 0, and false otherwise. So 1, 2, 4 and 8 count, while 0, 6 and every negative number do not.
Function
- ninteger
- the integer to test, which may be zero or negative
- Returnsboolean
- true if n equals 2^k for some k ≥ 0, false otherwise
Constraints
-231 ≤ n ≤ 231-1
Examples
- Input
- n = 16
- Output
- true
- Explanation
- 16 = 2 × 2 × 2 × 2 = 2^4. In binary it is
10000, a single 1 bit.
- Input
- n = 24
- Output
- false
- Explanation
- 24 = 8 × 3. Halving gives 12, 6 and then 3, which is odd but not 1. In binary 24 is
11000, two 1 bits.
- Input
- n = 1
- Output
- true
- Explanation
- 1 = 2^0, so it is a power of two. Its binary form
1has exactly one 1 bit.
+17 hidden tests on Submit
Follow-up
With the same bit tricks, can you test whether n is a power of four without a loop?
Hints
Open them one at a time. Each one gives away a little more.
Write a few powers of two in binary:
1,10,100,1000. What do all of them have in common that 6 (110) does not?A power of two has exactly one 1 bit. Compare
nwithn-1in binary: subtracting 1 flips the lowest 1 bit to 0 and every 0 below it to 1.So
nis a power of two exactly when it is positive and AND-ing it withn-1gives 0. Test the sign before the bits, since 0 and negative numbers are never powers of two.
Solution
A power of two has a fixed shape in binary: one 1 bit followed by zeros, like 10000 for 16. You can confirm that shape by halving n until it turns odd, which takes up to 31 steps. Or you can confirm it in one step with n & (n-1), which clears the lowest 1 bit and leaves 0 only when that bit was the only one. In both versions the sign check comes first, because zero and negative numbers break the obvious code.
Divide by 2 while the number is even
Intuition
If n = 2^k, you can divide it by 2 exactly k times and land on 1, and every value along the way is even. If n has an odd factor bigger than 1, the halving stops at an odd number that is not 1. For 16: 16, 8, 4, 2, 1, so the answer is true. For 24: 24, 12, 6, 3, and 3 is odd but not 1, so the answer is false.
Return false for n ≤ 0 before the loop. No power of two is zero or negative, and the loop would never end on 0, because 0 is even and half of 0 is still 0.
Each step halves n, so a 32-bit input takes at most 31 steps: O(log n) time and O(1) space.
Algorithm
- If
n ≤ 0, return false. - While
nis even, divide it by 2. - Return whether
nis now 1.
def isPowerOfTwo(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1Clear the lowest set bit with n & (n-1)
Intuition
Write a power of two in binary and it is a single 1 followed by zeros: 16 is 10000. Subtracting 1 turns that 1 into 0 and every 0 below it into 1: 15 is 01111. The two numbers share no 1 bit, so 16 & 15 is 0.
Any other positive number has at least two 1 bits. Subtracting 1 changes only the lowest 1 bit and the zeros under it, so every higher 1 bit appears in both numbers and the AND is not 0. For 24, which is 11000, you get 23 = 10111, and 24 & 23 is 10000, which is 16.
Check n > 0 first. 0 & -1 is 0, and in 32-bit arithmetic -2^31 is a lone 1 bit followed by 31 zeros, so the AND alone would call both of them powers of two. The whole test is one comparison, one subtraction and one AND: O(1) time and space. Lua 5.1 has no AND operator, so the Lua code builds the AND one bit at a time, up to 31 steps for a 32-bit n; the test is the same.
Algorithm
- If
n ≤ 0, return false. - Compute
n & (n-1), which isnwith its lowest 1 bit cleared. - Return whether that result is 0.
def isPowerOfTwo(n):
# One set bit: n - 1 flips it and every bit below, so the AND is 0.
return n > 0 and n & (n - 1) == 0
Pitfalls and edge cases
The bit test is one line, and most of the mistakes are about the inputs it was not designed for.
- Skipping the sign check.
0 & (0-1)is 0, so 0 passes the AND test. With 32-bit integers-2^31passes too, because its binary form is a single 1 bit. Both must return false. - Running the halving loop on 0. Zero is even, and halving it gives 0 again, so the loop never ends.
- Dropping the parentheses.
==binds tighter than&, so in C, C++ and JavaScriptn & n - 1 == 0is read asn & ((n - 1) == 0)and gives the wrong answer without any error; Java and C# reject it as a type error. Write(n & (n - 1)) == 0. - Using logarithms. In double precision,
log(536870912) / log(2)comes out as 29.000000000000004 instead of 29, so a whole number check calls2^29false.
Frequently asked questions4
How do you check if a number is a power of two?
Return true when n > 0 and n & (n-1) equals 0. A power of two has exactly one 1 bit, and subtracting 1 clears it while setting only the bits below it, so the AND is 0. Without bit operations, halve n while it is even and check that you end at 1.
Why does n & (n-1) clear the lowest set bit?
Subtracting 1 borrows from the lowest 1 bit: that bit becomes 0 and every 0 below it becomes 1, while the higher bits stay the same. AND-ing with the original keeps only the bits set in both, which are exactly the higher bits. For a power of two there are no higher bits, so the result is 0.
What is the time complexity of Power of Two?
The n & (n-1) check runs in O(1) time and space: one comparison, one subtraction and one AND. The halving loop runs in O(log n) time, at most 31 steps for a 32-bit integer.
Is 1 a power of two? Is 0?
1 is a power of two, because 2^0 = 1, and its binary form has one 1 bit. 0 is not: no whole exponent gives 0, and it has no 1 bit at all. Negative numbers are never powers of two either.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def isPowerOfTwo(n):
# Write code hereCase 1
Case 2
Case 3
Input
n = 16
Expected
true