Check if a Number is Power of 2
Solve this Problem
Given an integer
n, determine whether it's a power of 2 (1, 2, 4, 8, 16, ...). Zero and negative numbers are never powers of 2.
Repeatedly dividing by 2 until an odd remainder or 1 shows up works, but a power of 2 has a distinctive binary shape: exactly one bit set, with every bit below it clear. Subtracting 1 from such a number flips that single bit off and every lower bit on — a pattern that never overlaps with the original number, so n & (n - 1) collapses straight to 0 only when n had exactly one bit set to begin with.
Test Case 1:
Input:n = 1
Output:true
Explanation:2⁰ = 1, the smallest power of two.
Test Case 2:
Input:n = 16
Output:true
Explanation:16 = 10000 — exactly one bit set, so it's a power of 2.
Test Case 3:
Input:n = 3
Output:false
Explanation:3 = 011 has two set bits, so it isn't a power of 2.
Constraints
- ◆
-2³¹ ≤ n ≤ 2³¹ − 1
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Repeated Division
BruteZero and negative numbers are never powers of 2. Otherwise, keep dividing by 2 as long as the result is even; if the number ever stops dividing evenly and it isn't exactly 1, it wasn't a power of 2 to begin with.
Time
O(log n)Space
O(1)Java
1class Solution {
2 public boolean isPowerOfTwo(int n) {
3 if (n <= 0) {
4 return false;
5 }
6 int value = n;
7 while (value % 2 == 0) {
8 value = value / 2;
9 }
10 return value == 1;
11 }
12}Optimal — Bit Trick n & (n - 1)
OptimalA power of 2 has exactly one bit set, with every lower bit clear. Subtracting 1 from it flips that single bit off and every bit below it on — a pattern that shares nothing in common with the original number, so ANDing the two together collapses straight to 0. Any number with more than one set bit keeps at least one higher bit unchanged after subtracting 1, so the AND stays nonzero.
Time
O(1)Space
O(1)Java
1class Solution {
2 public boolean isPowerOfTwo(int n) {
3 if (n <= 0) {
4 return false;
5 }
6 int masked = n & (n - 1);
7 return masked == 0;
8 }
9}