Check if Number is Power of Two in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this code snippet?

Given the function to check if a number is a power of two, what will be printed for n = 16?

DSA C

int isPowerOfTwo(unsigned int n) {
    return n && !(n & (n - 1));
}

#include <stdio.h>

int main() {
    unsigned int n = 16;
    if (isPowerOfTwo(n)) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}

A No

B 1

C 0

D Yes

💡 Hint

A power of two has exactly one bit set in binary.

The function returns true if n is not zero and n & (n-1) is zero, which is true only for powers of two. 16 is 2^4, so output is 'Yes'.

❓ Predict Output

intermediate

What is the output when n = 0?

Using the same function, what will be printed for n = 0?

DSA C

int isPowerOfTwo(unsigned int n) {
    return n && !(n & (n - 1));
}

#include <stdio.h>

int main() {
    unsigned int n = 0;
    if (isPowerOfTwo(n)) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}

A Yes

B 1

C No

D 0

💡 Hint

Zero is not a power of two.

The function returns false for zero because the first condition 'n' fails. So output is 'No'.

🔧 Debug

advanced

What error does this code raise?

Identify the error in this code snippet that attempts to check if n is a power of two.

DSA C

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

#include <stdio.h>

int main() {
    unsigned int n = 8;
    if (isPowerOfTwo(n)) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}

A Logical error causing wrong output

B Always prints 'No'

C No error, prints 'Yes'

D Syntax error

💡 Hint

Operator precedence matters in bitwise and comparison operations.

The expression 'n & (n - 1) == 0' is evaluated as 'n & ((n - 1) == 0)', which is wrong. It should be '(n & (n - 1)) == 0'.

🧠 Conceptual

advanced

How many numbers between 1 and 16 (inclusive) are powers of two?

Count how many numbers in the range 1 to 16 are powers of two.

A 5

B 4

C 6

D 7

💡 Hint

Powers of two are 1, 2, 4, 8, 16 in this range.

The powers of two in 1 to 16 are 1, 2, 4, 8, and 16, total 5 numbers.

🚀 Application

expert

What is the value of variable 'count' after this code runs?

This code counts how many numbers in an array are powers of two. What is the final count?

DSA C

#include <stdio.h>

int isPowerOfTwo(unsigned int n) {
    return n && !(n & (n - 1));
}

int main() {
    unsigned int arr[] = {3, 4, 6, 8, 16, 18, 32};
    int count = 0;
    for (int i = 0; i < 7; i++) {
        if (isPowerOfTwo(arr[i])) {
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}

A 3

B 4

C 5

D 6

💡 Hint

Check each number if it has exactly one bit set.

Numbers 4, 8, 16, and 32 are powers of two, so count is 4.

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