231. Power of Two
easyDecide whether an integer is a power of two — ideally without a loop. A bit-trick favorite: powers of two are exactly the integers where (n & (n - 1)) == 0.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given an integer n, return true if it is a power of two. Otherwise, return false. An integer n is a power of two, if there exists an integer x such that n == 2^x.
Constraints
-2^31 <= n <= 2^31 - 1
Examples
Example 1
n = 1trueExplanation: 2^0 = 1.
Example 2
n = 16trueExplanation: 2^4 = 16.
Example 3
n = 3falseSolve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Powers of two are exactly the positive integers with exactly one set bit in binary.
Hint 2
n & (n - 1) clears the lowest set bit. If the result is 0, n had exactly one set bit (and n > 0).
Hint 3
So the one-liner is: return n > 0 && (n & (n - 1)) == 0. The n > 0 guard rules out 0 and negatives.
Hint 4
Alternative: n & -n isolates the lowest set bit. If n & -n == n, n had only that one bit.
Solution approach
Reveal approach
Use the bit identity: powers of two have exactly one set bit, and n & (n - 1) clears the lowest set bit. So n is a power of two iff n > 0 and (n & (n - 1)) == 0. The n > 0 guard handles 0 (which has no set bits) and negatives (whose two's-complement representations have many set bits). O(1) time and space. A second equally-clean approach: n & -n returns the lowest set bit alone; if that equals n, then n had only that one bit. Both are interview-grade answers; pick whichever you can explain more clearly.
Complexity
- Time
- O(1)
- Space
- O(1)
Related patterns
- bit-manipulation
- math
Related problems
- 326. Power of Three
- 342. Power of Four
- 191. Number of 1 Bits
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
- Apple
More Math practice problems
- 7. Reverse Integer
- 8. String to Integer (atoi)
- 9. Palindrome Number
- 12. Integer to Roman
- 13. Roman to Integer
- 29. Divide Two Integers
- 38. Count and Say
- 43. Multiply Strings