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.

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