Why Check if Number is Power of Two in DSA C?

The Big Idea

Discover a tiny trick that makes checking powers of two lightning fast!

The Scenario

Imagine you have a big list of numbers, and you want to find out which ones are powers of two, like 1, 2, 4, 8, 16, and so on. Doing this by dividing each number repeatedly by 2 and checking if you end up with 1 can take a lot of time and effort, especially if the list is very long.

The Problem

Manually dividing numbers by 2 over and over is slow and can easily lead to mistakes, especially if you forget to check for edge cases like zero or negative numbers. It also wastes time when you have to do this for many numbers.

The Solution

Using a simple bit trick, you can quickly check if a number is a power of two by looking at its binary form. This method is very fast and reliable, and it works instantly even for very large numbers.

Before vs After

✗ Before

int isPowerOfTwo(int number) {
    if (number <= 0) return 0;
    while (number % 2 == 0) {
        number /= 2;
    }
    return number == 1;
}

✓ After

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

What It Enables

This lets you instantly identify powers of two, enabling faster algorithms and smarter decisions in programs that rely on binary operations.

Real Life Example

In computer graphics, checking if a texture size is a power of two helps optimize memory and performance, because many graphics systems work best with power-of-two dimensions.

Key Takeaways

Manual division is slow and error-prone.

Bitwise check is fast and simple.

Useful in many computing tasks involving binary data.

Practice

1. Which of the following statements correctly describes a number that is a power of two?

easy

A. It has exactly one bit set to 1 in its binary form.

B. It is always an odd number.

C. It is divisible by 3.

D. It has all bits set to 1 in its binary form.

Solution

1. Step 1: Understand binary representation of powers of two

   A power of two in binary has exactly one '1' bit and the rest are '0's. For example, 4 is 100 in binary.

2. Step 2: Analyze the options

   It has exactly one bit set to 1 in its binary form. matches the binary property of powers of two. Options B, C, and D do not describe powers of two correctly.

3. Final Answer:

   It has exactly one bit set to 1 in its binary form. -> Option A

4. Quick Check:

   Power of two = one '1' bit [OK]

Hint: Power of two has only one '1' bit in binary [OK]

Common Mistakes:

• Thinking powers of two are always odd
• Assuming powers of two have multiple '1' bits
• Confusing divisibility rules

2. Which of the following C code snippets correctly checks if an integer n is a power of two?

easy

A. if (n & (n - 1)) { /* not power of two */ } else { /* power of two */ }

B. if (n | (n - 1)) { /* power of two */ } else { /* not power of two */ }

C. if (n & (n + 1)) { /* power of two */ } else { /* not power of two */ }

D. if (n ^ (n - 1)) { /* power of two */ } else { /* not power of two */ }

Solution

1. Step 1: Understand bitwise check for power of two

   The expression n & (n - 1) is zero only if n is a power of two.

2. Step 2: Analyze each option

   if (n & (n - 1)) { /* not power of two */ } else { /* power of two */ } uses the correct expression. Options A, C, and D use incorrect bitwise operations that do not correctly check for power of two.

3. Final Answer:

   if (n & (n - 1)) { /* not power of two */ } else { /* power of two */ } -> Option A

4. Quick Check:

   n & (n-1) == 0 means power of two [OK]

Hint: Use n & (n-1) == 0 to check power of two [OK]

Common Mistakes:

• Using OR instead of AND in bitwise check
• Using n + 1 instead of n - 1
• Confusing XOR with AND

3. What is the output of the following C code snippet?

int n = 16;
if (n & (n - 1))
    printf("No\n");
else
    printf("Yes\n");

medium

A. Runtime error

B. No

C. Compilation error

D. Yes

Solution

1. Step 1: Calculate n & (n - 1) for n = 16

   16 in binary is 10000. 15 is 01111. Bitwise AND: 10000 & 01111 = 00000 (0).

2. Step 2: Check condition and output

   Since the result is 0, the else block executes, printing "Yes".

3. Final Answer:

   Yes -> Option D

4. Quick Check:

   16 & 15 = 0 means power of two [OK]

Hint: If n & (n-1) is zero, print Yes [OK]

Common Mistakes:

• Miscomputing bitwise AND
• Confusing output branches
• Assuming non-zero means power of two

4. Identify the error in the following C code that checks if n is a power of two:

int n = 10;
if (n & n - 1 == 0)
    printf("Power of two\n");
else
    printf("Not power of two\n");

medium

A. No error, code is correct

B. Missing parentheses around (n - 1) in bitwise operation

C. Incorrect variable initialization

D. Using bitwise OR instead of AND

Solution

1. Step 1: Analyze operator precedence in condition

   In C, == has higher precedence than &, so expression is evaluated as n & ((n - 1) == 0) which is incorrect.

2. Step 2: Correct the expression with parentheses

   Use (n & (n - 1)) == 0 to ensure correct evaluation.

3. Final Answer:

   Missing parentheses around (n - 1) in bitwise operation -> Option B

4. Quick Check:

   Use parentheses to fix precedence [OK]

Hint: Add parentheses: (n & (n - 1)) == 0 [OK]

Common Mistakes:

• Ignoring operator precedence
• Not using parentheses in bitwise expressions
• Assuming code compiles correctly without fix

5. You want to write a function in C that returns 1 if a number n is a power of two and 0 otherwise. Which of the following implementations correctly handles the case when n is zero or negative?

hard

A. int isPowerOfTwo(int n) { return n >= 0 && (n & (n + 1)) == 0; }

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

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

D. int isPowerOfTwo(int n) { return n != 0 || (n & (n - 1)) == 0; }

Solution

1. Step 1: Consider zero and negative inputs

   Zero and negative numbers are not powers of two, so the function must exclude them.

2. Step 2: Analyze each function

   int isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; } checks if n > 0 and then applies the bitwise check correctly. int isPowerOfTwo(int n) { return (n & (n - 1)) == 0; } misses the positive check. Options A, B, and D use incorrect logic or operators.

3. Final Answer:

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

4. Quick Check:

   Check n > 0 before bitwise test [OK]

Hint: Check n > 0 before bitwise test to avoid errors [OK]

Common Mistakes:

• Not handling zero or negative inputs
• Using wrong bitwise operators
• Using OR instead of AND in conditions