Check if Number is Power of Two in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean for a number to be a power of two?

A number is a power of two if it can be written as 2 raised to some integer exponent, like 1, 2, 4, 8, 16, etc.

intermediate

Which bitwise operation can quickly check if a number is a power of two?

Using (n & (n - 1)) == 0 checks if n is a power of two, because powers of two have only one bit set.

intermediate

Why must we check if the number is greater than zero before using (n & (n - 1))?

Because zero and negative numbers are not powers of two, and (n & (n - 1)) == 0 is true for zero, so we exclude zero by checking n > 0.

beginner

What is the output of the function if the input number is 16?

The function returns true because 16 is 2^4, a power of two.

beginner

Write the C code snippet to check if an integer n is a power of two.

int isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }

Which of these numbers is NOT a power of two?

A 10

B 8

C 16

D 32

10 is not a power of two because it cannot be written as 2 raised to an integer.

What does the expression (n & (n - 1)) == 0 check for?

A If n is zero

B If n is a power of two

C If n is negative

D If n is odd

This expression is true only when n is a power of two (and n > 0).

Why do we check n > 0 before applying (n & (n - 1)) == 0?

A Because it improves performance

B Because negative numbers are powers of two

C Because zero also satisfies (n & (n - 1)) == 0 but is not a power of two

D Because it checks if n is odd

Zero satisfies the bitwise condition but is not a power of two, so we exclude it by checking n > 0.

What is the output of isPowerOfTwo(1)?

A True

B False

C Error

D Depends on compiler

1 is 2^0, so it is a power of two and the function returns true.

Which of these is a correct way to check if n is a power of two in C?

A return n % 2 == 0;

B return n & (n - 1);

C return n == 0 || n == 1;

D return n > 0 && (n & (n - 1)) == 0;

Option D correctly checks if n is positive and has only one bit set.

Explain how to check if a number is a power of two using bitwise operations.

Think about how powers of two look in binary.

Write a simple C function to check if a number is a power of two and explain why it works.

Use (n & (n - 1)) == 0 condition.