C Program to Check if Number is Power of 2

In C, you can check if a number is a power of 2 by using the condition n & (n - 1) == 0 and ensuring n > 0, for example: if (n > 0 && (n & (n - 1)) == 0) printf("Power of 2\n"); else printf("Not power of 2\n");.

Examples

Input16

OutputPower of 2

Input18

OutputNot power of 2

Input1

OutputPower of 2

How to Think About It

To check if a number is a power of 2, think about its binary form: powers of 2 have exactly one '1' bit and the rest are '0's. Using the bitwise AND operator, if you do n & (n - 1), it will be zero only for powers of 2. Also, the number must be greater than zero because zero or negative numbers are not powers of 2.

Algorithm

1

Get the input number n.

2

Check if n is greater than zero.

3

Perform bitwise AND of n and (n - 1).

4

If the result is zero, then n is a power of 2.

5

Otherwise, n is not a power of 2.

6

Print the result accordingly.

Code

c

#include <stdio.h>

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);

    if (n > 0 && (n & (n - 1)) == 0) {
        printf("Power of 2\n");
    } else {
        printf("Not power of 2\n");
    }
    return 0;
}

Output

Enter a number: 16
Power of 2

Dry Run

Let's trace the input 16 through the code to see how it checks if 16 is a power of 2.

1

Input number

n = 16

2

Check if n > 0

16 > 0 is true

3

Calculate n & (n - 1)

16 in binary is 10000, 15 is 01111, so 10000 & 01111 = 00000 (0)

4

Compare result to zero

Result is 0, so condition is true

5

Print result

Print 'Power of 2'

Step	n	n-1	n & (n-1)	Condition (==0)
3	16 (10000)	15 (01111)	0 (00000)	True

Why This Works

Step 1: Check positive number

The number must be greater than zero because zero and negative numbers cannot be powers of 2.

Step 2: Bitwise AND trick

For powers of 2, the binary form has only one '1'. Subtracting 1 flips all bits after that '1'. So, n & (n - 1) clears the only set bit, resulting in zero.

Step 3: Decision

If n & (n - 1) equals zero, the number is a power of 2; otherwise, it is not.

Alternative Approaches

Using loop to divide by 2

c

#include <stdio.h>

int main() {
    int n, temp;
    printf("Enter a number: ");
    scanf("%d", &n);
    if (n <= 0) {
        printf("Not power of 2\n");
        return 0;
    }
    temp = n;
    while (temp % 2 == 0) {
        temp /= 2;
    }
    if (temp == 1) {
        printf("Power of 2\n");
    } else {
        printf("Not power of 2\n");
    }
    return 0;
}

This method uses repeated division by 2 until the number is 1 or not divisible by 2; it is less efficient but easy to understand.

Using logarithm function

c

#include <stdio.h>
#include <math.h>

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    if (n > 0 && floor(log2(n)) == ceil(log2(n))) {
        printf("Power of 2\n");
    } else {
        printf("Not power of 2\n");
    }
    return 0;
}

This method uses math functions to check if log base 2 is an integer; it requires including math library and may have floating point precision issues.

Complexity: O(1) time, O(1) space

Time Complexity

The bitwise operation n & (n - 1) runs in constant time, so the overall time complexity is O(1).

Space Complexity

The program uses a fixed amount of memory for variables, so space complexity is O(1).

Which Approach is Fastest?

The bitwise method is fastest and simplest compared to looping or using logarithms, which are slower or require extra libraries.

Approach	Time	Space	Best For
Bitwise AND	O(1)	O(1)	Fastest and simplest check
Loop division	O(log n)	O(1)	Easy to understand, no bitwise knowledge needed
Logarithm	O(1)	O(1)	When math library is available, but may have precision issues