Power of Two
Power of Two is LeetCode 231 (Easy). Given an integer n, return true if n is a power of two, and false otherwise.
nis a power of two whenn = 2^xfor some integerx ≥ 0.ncan be zero or negative; no power of two is.nfits in a 32-bit signed int, so the largest power of two to recognise is 2³⁰.- Follow-up: solve it without loops or recursion.
- -2³¹ <= n <= 2³¹ - 1
Intuition
Look at the powers of 2 in binary:
1 = 0001,2 = 0010,4 = 0100,8 = 1000.
Each one has exactly one bit set. Every other positive number has at least two, because it is a sum of two or more different powers of two (12 = 8 + 4 = 1100).
So the question becomes: does n have exactly one 1-bit? The expression n & (n - 1) answers it in one step. Subtracting 1 flips the lowest set bit to 0 and every 0 below it to 1:
12 = 1100→11 = 1011, and1100 & 1011 = 1000: a bit survives, so 12 is not a power of two.16 = 10000→15 = 01111, and10000 & 01111 = 00000: nothing survives, so 16 is.
n & (n - 1) removes the lowest set bit. It is 0 exactly when that was the only one.
Questions about powers of 2, "exactly one" of something, or clearing the lowest set bit are bit manipulation. n & (n - 1) is the key identity: it also counts set bits (Brian Kernighan's method, one step per 1-bit) and appears in Counting Bits and Number of 1 Bits.
Approach
Before reading on: write 8, 7, 12 and 11 in binary. What does 8 & 7 give? What about 12 & 11? Then decide what the answer should be for n = 0 and whether the bit test gets it right on its own.
Two ways to solve it
Reject n ≤ 0, then check that clearing the lowest set bit leaves 0.
- Speed: three operations for any
n. - Follow-up: no loop and no recursion.
- Idea: a power of two has exactly one 1-bit.
The answer interviewers expect.
Reject n ≤ 0, halve n while it is even, and check that 1 is what remains.
- Simple: needs no binary reasoning.
- Speed: at most 30 halvings for an int.
- Follow-up: fails it, since it loops.
A fine first answer before the bit trick.
The bit trick answers in constant time and meets the no-loop follow-up, so it is the one to know. The steps, code and live demo below follow it, and the division loop is further down.
Reject n ≤ 0 first
Zero and negative numbers are never powers of two, so return false for them before the bit test runs. n & (n - 1) is also 0 for n = 0, so without this check zero would wrongly pass.
Clear the lowest set bit
Compute n & (n - 1). Subtracting 1 turns the lowest 1-bit into 0 and the 0s below it into 1s; the AND then keeps only the higher bits that both numbers share. Removing the lowest set bit leaves 0 only when that bit was the only one.
Test for zero
If the result is 0, n had exactly one set bit, so it is a power of two. Otherwise at least one more bit is set.
Power of Two solution in Python | C++ | Java
10000. Every power of two is a single 1 followed by 0s, so the question is whether 16 has exactly one set bit. The code checks that without counting.n and n - 1 differ.1100. Every power of two is a single 1 followed by 0s, so the question is whether 12 has exactly one set bit. The code checks that without counting.n and n - 1 differ.1. Every power of two is a single 1 followed by 0s, so the question is whether 1 has exactly one set bit. The code checks that without counting.n and n - 1 differ.-1 is all ones in two's complement (the lowest 8 are shown), so 0 & -1 = 0. The bit test passes, yet 0 is not a power of two. That is why the sign check comes first.2^x is positive for every x, so any n <= 0 returns false before the bit test runs. For negative n it also avoids n - 1 overflowing at -2³¹.Divide by 2 in a loop
A power of two is 2 multiplied by itself some number of times, so removing every factor of 2 must leave exactly 1. Any odd factor left over means it was not a power of two.
Common pitfalls
Skipping the n ≤ 0 check
return (n & (n - 1)) == 0
if n <= 0:
return False
return (n & (n - 1)) == 00 & -1 is 0, so 0 is reported as a power of two. In C++ and Java, n = -2³¹ is also wrong: n - 1 overflows, and in C++ that is undefined behaviour.
Leaving out the parentheses in C++ and Java
return n & (n - 1) == 0;
return (n & (n - 1)) == 0;
== binds tighter than & in C-family languages, so this computes n & ((n - 1) == 0). In Java it does not compile; in C++ it compiles and returns true only for n = 1.
Edge cases
1 = 2⁰, so the answer is true. 1 & 0 = 0, so the test gets it right without a special case.
Complexity
n. Dividing by 2 in a loop is O(log n) instead.Power of Two FAQ
How do you check if a number is a power of two with bits?
- Reject
n ≤ 0: no power of two is zero or negative. - Test
(n & (n - 1)) == 0. - Why: a power of two has exactly one set bit, and
n - 1flips that bit off, so the AND is 0 only in that case. - Complexity: O(1) time and space.
- Example:
16 & 15 = 10000 & 01111 = 0, so 16 is a power of two;12 & 11 = 1000, so 12 is not.
What are the powers of 2?
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, … Each is double the one before, and in binary each is a 1 followed only by 0s. In a 32-bit signed int the largest is 2³⁰ = 1,073,741,824.
Can you solve power of two without loops or recursion?
Yes. n > 0 and (n & (n - 1)) == 0 uses neither. Two other loop-free tests: n > 0 and (n & -n) == n, because n & -n keeps only the lowest set bit, and n > 0 and (1 << 30) % n == 0, since the only divisors of 2³⁰ are the powers of 2 up to it.