Check if a Number is Power of 2 - Visualization

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given a positive integer n, determine whether it is a power of two.

A number is a power of two if it is greater than zero and has exactly one bit set in its binary representation (e.g., 1, 2, 4, 8, 16, ...).

Return true if n is a power of two, otherwise return false.

Examples❯

n Output Description
1 true 1 is 2⁰, and binary is 0001 — one bit is set
2 true 2 is 2¹, and binary is 0010 — one bit is set
3 false Binary is 0011 — more than one bit is set
4 true 4 is 2², and binary is 0100 — one bit is set
5 false Binary is 0101 — more than one bit is set
16 true 16 is 2⁴, binary is 00010000 — one bit is set
18 false Binary is 00010010 — more than one bit is set
1024 true 1024 is 2¹⁰, binary is 10000000000 — one bit is set
0 false Zero has no bits set — not a power of two
-8 false Negative numbers are not considered powers of two
"" false Empty input is invalid — treated as 0
null false Null input is invalid — treated as 0

Solution❯

Understanding the Problem

We are given a positive integer n, and we need to determine if it is a power of two.

A number is considered a power of two if it can be written as 2k where k is a non-negative integer. Examples include: 1, 2, 4, 8, 16, 32, and so on.

The key observation is that powers of two have exactly one bit set in their binary representation. For example:

  • 1 = 0001
  • 2 = 0010
  • 4 = 0100
  • 8 = 1000

If a number has only one bit set, then n & (n - 1) will be 0.

Step-by-Step Solution with Example

step 1: Understand what input we are working with

Suppose we are given n = 8.

The binary representation of 8 is 1000, which clearly has only one bit set.

step 2: Check if the number is greater than 0

We start by checking if n > 0. If it's not, we return false immediately because negative numbers and zero cannot be powers of two.

Here, 8 > 0, so we proceed to the next step.

step 3: Apply the bitwise trick n & (n - 1)

Let’s compute n - 1 which is 7. In binary, that’s 0111.

Now compute 8 & 7:


  1000  (8)
& 0111  (7)
  ----
  0000

Since the result is 0, this means n is a power of two.

step 4: Return true if result is 0, otherwise false

Because we got 0 from the bitwise AND, we return true.

Edge Cases

  • n = 0: Not a power of two. Return false.
  • n = 1: Considered a power of two (20). Return true.
  • n = -8: Negative numbers can never be powers of two. Return false.
  • n = 18: Binary is 10010, which has more than one bit set. Return false.

Final Thoughts

This approach is highly efficient because it uses bitwise operations, which are fast and require only constant time.

For beginners, remember: the trick n & (n - 1) helps you check if there's only one bit set. That’s the magic behind detecting powers of two!

Always start with validating the input, especially for 0 and negative numbers.

Algorithm Steps❯

  1. Check if n is less than or equal to 0. If yes, return false.
  2. Perform bitwise AND between n and n - 1: n & (n - 1).
  3. If the result is 0, it means n is a power of two (only one bit is set).
  4. Otherwise, it's not a power of two.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdbool.h>

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

int main() {
    int numbers[] = {1, 2, 3, 4, 16, 18, 32, 0, -4};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    for (int i = 0; i < size; i++) {
        printf("%d: %s\n", numbers[i], isPowerOfTwo(numbers[i]) ? "true" : "false");
    }
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The bitwise operation `n & (n - 1)` is a constant-time operation, so the function completes in constant time for any input.
Average CaseO(1)Regardless of the value of n, only a fixed number of bitwise and comparison operations are performed.
Worst CaseO(1)Even in the worst case, such as very large values of n, the number of operations remains constant due to direct bitwise checks.

Space Complexity❯

O(1)

Explanation: No extra data structures or memory allocations are used — only a few primitive variables for computation, making it constant space.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...