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

The Big Idea

Discover a simple trick that turns a slow, tiring task into a lightning-fast check!

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 hand means dividing each number by 2 again and again until you reach 1 or a number that is not divisible by 2.

The Problem

This manual way is slow and tiring, especially if the numbers are very big. You might make mistakes counting divisions or miss some numbers. It's like trying to find a needle in a haystack by checking every straw one by one.

The Solution

Using a simple check with bits (the way computers store numbers) lets us quickly tell if a number is a power of two. This method is fast and never makes mistakes because it uses a clever trick with how numbers look in binary form.

Before vs After

✗ Before

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

✓ After

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

What It Enables

This lets you quickly and reliably check if numbers are powers of two, which is useful in many computer tasks like memory allocation and optimization.

Real Life Example

When a game needs to create textures or images, it often requires sizes that are powers of two for better performance. This check helps the game quickly decide if the size is right.

Key Takeaways

Manual division to check powers of two is slow and error-prone.

Bitwise check is a fast and reliable shortcut.

This method is widely used in programming and computer systems.

Practice

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

easy

A. It is divisible by 3.

B. It is always an odd number.

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

D. It has exactly one bit 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, e.g., 4 is 100.

2. Step 2: Check other options for correctness

   Odd numbers and divisibility by 3 do not define powers of two. Having all bits set to 1 means numbers like 7 (111), not powers of two.

3. Final Answer:

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

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
• Confusing all bits set to 1 with power of two
• Assuming divisibility by 3 means power of two

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

easy

A. return (n & (n + 1)) == 0;

B. return (n | (n - 1)) == 0;

C. return (n & (n - 1)) == 0 && n > 0;

D. return (n ^ (n - 1)) == 0;

Solution

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

   For a power of two, n & (n - 1) clears the only set bit, resulting in 0. Also, n must be positive.

2. Step 2: Analyze other expressions

   Other options use incorrect bitwise operations that do not correctly identify powers of two.

3. Final Answer:

   return (n & (n - 1)) == 0 && n > 0; -> Option C

4. Quick Check:

   Bitwise AND with n-1 equals zero means power of two [OK]

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

Common Mistakes:

• Using OR or XOR instead of AND
• Not checking if n is positive
• Using n + 1 instead of n - 1

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

int n = 16;
bool result = (n & (n - 1)) == 0 && n > 0;
Console.WriteLine(result);

medium

A. True

B. False

C. Compile-time error

D. Runtime exception

Solution

1. Step 1: Calculate bitwise AND of n and n-1

   For n=16 (binary 10000), n-1=15 (binary 01111). Bitwise AND is 0.

2. Step 2: Check if result is zero and n is positive

   Since (n & (n - 1)) == 0 and n > 0, the expression is true.

3. Final Answer:

   True -> Option A

4. Quick Check:

   16 is power of two, so output is True [OK]

Hint: If n & (n-1) == 0 and n>0, output is True [OK]

Common Mistakes:

• Miscomputing bitwise AND
• Ignoring n > 0 condition
• Confusing True and False outputs

4. The following code is intended to check if n is a power of two. What is the error?

bool IsPowerOfTwo(int n) {
    return (n & (n - 1)) == 0;
}

medium

A. The expression should be (n | (n - 1)) == 0 instead.

B. It does not check if n is positive, so zero or negative numbers return true incorrectly.

C. The function should return an integer, not a boolean.

D. The bitwise AND operator is used incorrectly; it should be OR.

Solution

1. Step 1: Analyze the bitwise condition

   The expression (n & (n - 1)) == 0 is true for powers of two but also for zero.

2. Step 2: Identify missing condition

   Zero and negative numbers are not powers of two, so the function must check n > 0.

3. Final Answer:

   It does not check if n is positive, so zero or negative numbers return true incorrectly. -> Option B

4. Quick Check:

   Check n > 0 to avoid false positives [OK]

Hint: Always check n > 0 when using bitwise power of two check [OK]

Common Mistakes:

• Omitting n > 0 check
• Using wrong bitwise operator
• Returning wrong data type

5. You want to write a function that returns the smallest power of two greater than or equal to a given positive integer n. Which approach correctly achieves this in C#?

hard

A. Use a loop doubling a variable starting at 1 until it is >= n.

B. Return n & (n - 1) to get the smallest power of two.

C. Return n | (n - 1) to get the smallest power of two.

D. Return n ^ (n - 1) to get the smallest power of two.

Solution

1. Step 1: Understand the problem requirement

   We need the smallest power of two >= n, so start from 1 and double until reaching or exceeding n.

2. Step 2: Analyze other options

   Bitwise operations like AND, OR, XOR with n-1 do not produce the smallest power of two >= n.

3. Final Answer:

   Use a loop doubling a variable starting at 1 until it is >= n. -> Option A

4. Quick Check:

   Doubling loop finds smallest power of two >= n [OK]

Hint: Double from 1 until >= n to find smallest power of two [OK]

Common Mistakes:

• Using bitwise AND/OR/XOR incorrectly for this task
• Not handling n less than 1
• Assuming bitwise ops give next power of two