Power of Two
Easy · Bit Manipulation · Math · Bit Manipulation · Recursion
Problem
Given an integer n, return true if n equals 2^x for some whole number x >= 0, and false otherwise.
1 counts, because it is 2^0. Zero and negative numbers never do. Try to answer without a loop or recursion.
Examples
Input: n = 64 Output: true
64 is 2^6: in binary 1000000, a single set bit.
Input: n = 12 Output: false
12 is 1100 in binary. It has two set bits, so it is not a power of two.
Input: n = -8 Output: false
Negative numbers are never powers of two.
Constraints
- -2^31 <= n <= 2^31 - 1
Approaches
- Divide by two until odd — time O(log n), space O(1)
Follow-up
The same one-bit idea answers related questions in constant time: n & -n isolates the lowest set bit, n & (n - 1) removes it, and a power of four is a power of two whose single bit sits at an even position (n & 0x55555555). For a power of three there is no bit trick, but 1162261467 % n == 0 works, because that is the largest power of three that fits in 32 bits.
Related problems
Start free on Cariara · Coding problems · System design studio
