231. Power of Two - Detailed Explanation

Problem Statement

Given an integer n, return true if n 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ˣ.

Examples

Input: n = 1
Output: true
Explanation: 1 = 2⁰.
Input: n = 16
Output: true
Explanation: 16 = 2⁴.
Input: n = 218
Output: false
Explanation: 218 is not a power of two.

Constraints

–2³¹ ≤ n ≤ 2³¹ – 1

Hints

How many bits are set in the binary representation of a power of two?
If you subtract 1 from a power of two, what happens to its binary form?

Approach 1 Brute Force Division

Explanation

Keep dividing n by 2 as long as it’s even and greater than 0. If you end at 1, it was a power of two; otherwise not.

Step‑by‑step Walkthrough

If n ≤ 0, return false.
While n % 2 == 0, do n /= 2.
After the loop, check if n == 1.

Visual Example

n = 16  
16 % 2 == 0 → n = 8  
8 % 2 == 0  → n = 4  
4 % 2 == 0  → n = 2  
2 % 2 == 0  → n = 1  
Loop ends; n == 1 → true

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time O(log n) because each division halves n.
Space O(1).

Approach 2 Bit Manipulation (Optimal)

Explanation

A positive power of two has exactly one bit set in its binary form (100…0). For such a number n, the expression n & (n - 1) clears that lowest set bit, resulting in zero. So n > 0 && (n & (n - 1)) == 0 detects powers of two in constant time.

Step‑by‑step Walkthrough

If n ≤ 0, return false.
Compute n & (n - 1).
If the result is 0, n had only one '1' bit → return true; else false.

Visual Example

n = 16 → binary 10000  
n - 1 = 15 → binary 01111  
10000 & 01111 = 00000 → zero → true

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time O(1).
Space O(1).

Common Mistakes

Not handling non‑positive n (should return false for zero and negatives).
Using floating‑point checks like repeated division by 2.0 which can incur precision errors.
Forgetting that (n & (n - 1)) trick only applies to integers.

Edge Cases

n = 0 → false
Negative n → false
Maximum 32‑bit integer n = 2³¹ - 1 → not a power of two → false.

Alternative Variations

Check if a number is a power of three or power of four using similar bit or math tricks.
Count the number of set bits and ensure it equals 1.
Use logarithms: log₂(n) is integer (watch floating‑point).