DSA AnimatorDSA animations
Power of Two LC #231 Easy Bit Manipulation · n & (n−1)
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ˣ.

Example 1
Input: n = 1
Output: true
Explanation: 2⁰ = 1.
Example 2
Input: n = 16
Output: true
Explanation: 2⁴ = 16.
Example 3
Input: n = 3
Output: false
Explanation: 3 is not a power of two.
Constraints: −2³¹ ≤ n ≤ 2³¹ − 1
Try Examples
Custom:
Approach
Single Bit Check — n > 0 && (n & (n−1)) == 0
Powers of 2 have exactly one set bit. n−1 flips all bits below that bit. The AND cancels them out to 0. One condition, O(1) time.
Binary Comparison
n = —
n−1 = —
AND = —
Variables
n
—
n − 1
—
n & (n−1)
—
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Powers of 2 have exactly one set bit in their binary representation
2
n−1 flips all bits up to and including the lowest set bit of n
3
n & (n−1) clears the lowest set bit — result is 0 only if n had one bit
4
Also check n > 0 to exclude 0 and negative numbers
Time
O(1)
Space
O(1)
Why It Works

A power of 2 like 8 (1000) has exactly one set bit. Subtracting 1 gives 7 (0111) — all bits below the set bit flip to 1, and the set bit itself becomes 0. The AND of 8 & 7 = 0. For any number that is not a power of 2, like 6 (110), subtracting 1 gives 5 (101). The AND 6 & 5 = 4 ≠ 0, so the check fails. The extra n > 0 guard handles 0 and negatives, since 0 & −1 would otherwise give 0 incorrectly.

How to solve Power of Two

LeetCode 231 · Easy · Bit Manipulation · Pattern: Single Set Bit

Why the obvious approach is slow

You can keep dividing by 2 while the number is even, and check if you reach 1. That takes O(log n) steps.

The key idea

In binary, a power of two has exactly one 1 bit. Removing the lowest set bit, with n AND n −1, leaves 0 only in that case. Also require n to be positive, because 0 and negative numbers are not powers of two.

Remember

A power of two has exactly one set bit. n greater than 0 and n AND n −1 equal to 0.

Run the animation above on your own input, or watch the 1:29 video explanation of Power of Two with a dry run and Java code.

More Bit Manipulation problems