How to check if a number is a power of 2?

How to Check if a Number is a Power of 2

A number is a power of 2 if it can be expressed as (2^n) where (n) is a non-negative integer. In binary representation, powers of 2 have a single bit set to 1, with all other bits being 0 (e.g., 1 (0001), 2 (0010), 4 (0100), 8 (1000), etc.).

Here are several methods to check if a given number is a power of 2.

Method 1: Using Bitwise AND Operation

This method is efficient and leverages the properties of binary numbers. For a number that is a power of 2, (n) and (n-1) have no common set bits.

Explanation

• For a power of 2, binary representation is 1000...0.
• Subtracting 1 from it gives 0111...1.
• Performing a bitwise AND between (n) and (n-1) results in 0 if (n) is a power of 2.

Implementation in Python

def is_power_of_2(n):
    return n > 0 and (n & (n - 1)) == 0

# Example usage
print(is_power_of_2(16))  # Output: True
print(is_power_of_2(18))  # Output: False

Method 2: Using a Loop

This method repeatedly divides the number by 2. If the number can be divided by 2 down to 1 without leaving a remainder, it is a power of 2.

Explanation

• Keep dividing the number by 2.
• If the number becomes 1, it is a power of 2.
• If at any step the number is not divisible by 2, it is not a power of 2.

Implementation in Python

def is_power_of_2(n):
    if n <= 0:
        return False
    while n % 2 == 0:
        n /= 2
    return n == 1

# Example usage
print(is_power_of_2(16))  # Output: True
print(is_power_of_2(18))  # Output: False

Method 3: Using Bit Length

This method checks if the number has exactly one set bit in its binary representation.

Explanation

• Convert the number to its binary representation.
• Count the number of '1' bits.
• If there is exactly one '1' bit, the number is a power of 2.

Implementation in Python

def is_power_of_2(n):
    return n > 0 and bin(n).count('1') == 1

# Example usage
print(is_power_of_2(16))  # Output: True
print(is_power_of_2(18))  # Output: False

Method 4: Using Math Logarithm

This method uses logarithms to determine if the logarithm base 2 of the number is an integer.

Explanation

• Calculate the base-2 logarithm of the number.
• Check if the result is an integer.

Implementation in Python

import math

def is_power_of_2(n):
    return n > 0 and math.log2(n).is_integer()

# Example usage
print(is_power_of_2(16))  # Output: True
print(is_power_of_2(18))  # Output: False

Summary

• Bitwise AND Operation: Efficient and commonly used method to check if a number is a power of 2. (O(1) time complexity)
• Loop Division: Simple method using repeated division. (O(log n) time complexity)
• Bit Length Check: Uses binary string operations to check for a single '1' bit. (O(1) time complexity)
• Math Logarithm: Uses logarithmic properties to determine if the number is a power of 2. (O(1) time complexity, but potentially slower due to floating-point operations)

Each method has its own advantages, and the choice depends on the specific requirements and constraints of your application. For more in-depth knowledge and practical examples on programming concepts, consider exploring Grokking the Coding Interview on DesignGurus.io, which provides comprehensive courses on essential coding and interview techniques.