Check if Number is Power of Two in DSA C

Mental Model

A number is a power of two if it has exactly one '1' in its binary form.

Analogy: Imagine a row of light switches where only one switch is turned on at a time; that means the number is a power of two.

Number: 8
Binary: 1 0 0 0
          ↑
Only one '1' bit means power of two.

Dry Run Walkthrough

Input: number = 8

Goal: Check if 8 is a power of two

Step 1: Calculate number & (number - 1): 8 & 7

8 in binary: 1000
7 in binary:  0111
AND result:   0000

Why: If result is 0, number has only one '1' bit, so it is power of two

Step 2: Check if number is greater than 0

number = 8 > 0 is true

Why: Only positive numbers can be powers of two

Step 3: Since (number & (number - 1)) == 0 and number > 0, conclude power of two

Result: true

Why: Both conditions confirm number is power of two

Result:

8 is a power of two

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>

// Function to check if a number is power of two
bool isPowerOfTwo(int number) {
    // Check number is positive and only one bit is set
    return number > 0 && (number & (number - 1)) == 0;
}

int main() {
    int number = 8;
    if (isPowerOfTwo(number)) {
        printf("%d is a power of two\n", number);
    } else {
        printf("%d is NOT a power of two\n", number);
    }
    return 0;
}

return number > 0 && (number & (number - 1)) == 0;

Check if number is positive and has exactly one '1' bit in binary

Output

8 is a power of two

Complexity Analysis

Time: O(1) because bitwise operations take constant time

Space: O(1) because no extra memory is used

vs Alternative: Compared to looping and dividing by 2 repeatedly, this bitwise method is faster and simpler

Edge Cases

number = 0

Returns false because 0 is not a power of two

DSA C

return number > 0 && (number & (number - 1)) == 0;

number = 1

Returns true because 1 (2^0) is a power of two

DSA C

return number > 0 && (number & (number - 1)) == 0;

number = negative value

Returns false because negative numbers cannot be powers of two

DSA C

return number > 0 && (number & (number - 1)) == 0;

When to Use This Pattern

When you need to quickly check if a number is a power of two, use the bitwise AND trick because it efficiently tests the single '1' bit condition.

Common Mistakes

Mistake: Checking only if number & (number - 1) == 0 without verifying number > 0
Fix: Add number > 0 condition to exclude zero and negative numbers

Summary

Checks if a number has exactly one '1' bit in binary to determine if it is a power of two.

Use when you need a fast and simple way to verify powers of two without loops.

The key insight is that powers of two have only one bit set, so number & (number - 1) equals zero.