Checking if a Number is a Power of Two Using Bit Manipulation

Introduction

The Power of Two Check is a bit manipulation technique to determine if an integer is a power of two. Powers of two are integers like 1, 2, 4, 8, etc., where only one bit is set in their binary representation. This property allows for a quick and efficient check using a single bitwise operation.

How it Works

The key to this technique is understanding that for any power of two (e.g., 1, 2, 4, 8), the binary representation has exactly one set bit, and subtracting 1 from a power of two flips all bits to the right of that set bit. Using the expression n & (n - 1), we can check for this unique property.

Steps in the Algorithm:

1. If n is zero, it is not a power of two.
2. If n & (n - 1) equals zero, n is a power of two.
3. Otherwise, n is not a power of two.

Example Walkthrough

Let's take an example where n = 8 (which is 1000 in binary).

• Binary representation of n:
  n = 1000
  • Subtract 1:
    n - 1 = 0111
  • Perform the AND operation:
    n & (n - 1) = 1000 & 0111 = 0000

Since the result is zero, 8 is confirmed to be a power of two.

Edge Case Example

Consider n = 10 (binary 1010):

• Binary representation of n:
  n = 1010
  • Subtract 1:
    n - 1 = 1001
  • Perform the AND operation:
    n & (n - 1) = 1010 & 1001 = 1000 (not zero)

Since the result is not zero, 10 is not a power of two.

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

// Function to check if a number is a power of two
bool isPowerOfTwo(int n) {
    // Step 1: Check if the number is positive
    if (n <= 0) {
        return false;  // Negative numbers and zero are not powers of two
    }

    // Step 2: Perform the bitwise AND operation
    // If n is a power of two, n & (n - 1) should be 0
    int bitwiseCheck = n & (n - 1);

    // Step 3: Return the result of the check
    if (bitwiseCheck == 0) {
        return true;  // n is a power of two
    } else {
        return false;  // n is not a power of two
    }
}

int main() {
    // Testing the function with a list of numbers
    vector<int> numbers = {0, 1, 2, 3, 4, 16, 18};

    // Loop through each number and print whether it is a power of two
    for (int num : numbers) {
        bool result = isPowerOfTwo(num);
        cout << num << " is a power of two: " << (result ? "True" : "False") << endl;
    }

    return 0;
}

Python Implementation

def is_power_of_two(n):
    # Step 1: Check if the number is positive
    if n <= 0:
        return False  # Negative numbers and zero are not powers of two

    # Step 2: Perform the bitwise AND operation
    # If n is a power of two, n & (n - 1) should be 0
    bitwise_check = n & (n - 1)

    # Step 3: Return the result of the check
    if bitwise_check == 0:
        return True  # n is a power of two
    else:
        return False  # n is not a power of two

# Testing the function
numbers = [0, 1, 2, 3, 4, 16, 18]
for num in numbers:
    result = is_power_of_two(num)
    print(f"{num} is a power of two: {result}")

Time Complexity

The time complexity of this check is O(1) since it uses a single bitwise operation.

Why It's Efficient

The Power of Two Check avoids looping or recursive calculations. Instead, it relies on a simple bitwise operation, making it extremely fast and suitable for performance-sensitive applications.

Conclusion

Using bitwise operations to check for powers of two is a powerful technique, allowing for an efficient solution to a common problem in computer science. This technique is essential in algorithms requiring binary analysis and is widely applicable in fields like computer graphics, memory management, and data structure design.