Check if a Number is Power of 2

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.

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.

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.

#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;
}

#include <iostream>
using namespace std;

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++) {
        cout << numbers[i] << ": " << (isPowerOfTwo(numbers[i]) ? "true" : "false") << endl;
    }
    return 0;
}

def is_power_of_two(n: int) -> bool:
    if n <= 0:
        return False
    return (n & (n - 1)) == 0

numbers = [1, 2, 3, 4, 16, 18, 32, 0, -4]
for num in numbers:
    print(f"{num}: {str(is_power_of_two(num)).lower()}")

public class PowerOfTwoChecker {
    public static boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return (n & (n - 1)) == 0;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 16, 18, 32, 0, -4};
        for (int num : numbers) {
            System.out.println(num + ": " + isPowerOfTwo(num));
        }
    }
}

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

const numbers = [1, 2, 3, 4, 16, 18, 32, 0, -4];
numbers.forEach(num => {
    console.log(`${num}: ${isPowerOfTwo(num)}`);
});

package main

import "fmt"

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

func main() {
    numbers := []int{1, 2, 3, 4, 16, 18, 32, 0, -4}
    for _, num := range numbers {
        fmt.Printf("%d: %t\n", num, isPowerOfTwo(num))
    }
}

fn is_power_of_two(n: i32) -> bool {
    if n <= 0 {
        return false;
    }
    (n & (n - 1)) == 0
}

fn main() {
    let numbers = [1, 2, 3, 4, 16, 18, 32, 0, -4];
    for &num in &numbers {
        println!("{}: {}", num, is_power_of_two(num));
    }
}

fun isPowerOfTwo(n: Int): Boolean {
    if (n <= 0) return false
    return (n and (n - 1)) == 0
}

fun main() {
    val numbers = listOf(1, 2, 3, 4, 16, 18, 32, 0, -4)
    for (num in numbers) {
        println("$num: ${isPowerOfTwo(num)}")
    }
}

func isPowerOfTwo(_ n: Int) -> Bool {
    if n <= 0 { return false }
    return (n & (n - 1)) == 0
}

let numbers = [1, 2, 3, 4, 16, 18, 32, 0, -4]
for num in numbers {
    print("\(num): \(isPowerOfTwo(num))")
}

function isPowerOfTwo(n: number): boolean {
    if (n <= 0) return false;
    return (n & (n - 1)) === 0;
}

const numbers: number[] = [1, 2, 3, 4, 16, 18, 32, 0, -4];
numbers.forEach(num => {
    console.log(`${num}: ${isPowerOfTwo(num)}`);
});

Time complexity

Space complexity

O(1)

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