Check if Number is Power of Two in DSA C#

Mental Model

A number is a power of two if it can be divided by two repeatedly until it becomes one without any remainder.

Analogy: Imagine folding a paper in half multiple times. If you can fold it exactly some number of times until it becomes a tiny square, the number of folds is like the power of two.

16 -> 8 -> 4 -> 2 -> 1
Each arrow means dividing by 2 exactly with no leftovers.

Dry Run Walkthrough

Input: number = 16

Goal: Determine if 16 is a power of two

Step 1: Check if number is zero or negative

number = 16

Why: Powers of two are positive numbers only

Step 2: Check if 16 & (16 - 1) equals zero

16 in binary: 10000
15 in binary: 01111
16 & 15 = 00000

Why: If number & (number-1) is zero, number is power of two

Step 3: Return true because condition is met

Result = true

Why: 16 is a power of two

Result:

16 is a power of two: true

Annotated Code

DSA C#

using System;

class PowerOfTwoChecker
{
    public static bool IsPowerOfTwo(int number)
    {
        // If number is less than or equal to zero, it cannot be power of two
        if (number <= 0) return false;

        // Check if number & (number - 1) equals zero
        return (number & (number - 1)) == 0;
    }

    static void Main()
    {
        int number = 16;
        bool result = IsPowerOfTwo(number);
        Console.WriteLine($"{number} is a power of two: {result}");
    }
}

if (number <= 0) return false;

Exclude zero and negative numbers as they cannot be powers of two

return (number & (number - 1)) == 0;

Use bitwise AND to check if only one bit is set, indicating power of two

Output

16 is a power of two: True

Complexity Analysis

Time: O(1) because the bitwise operation runs in constant time regardless of input size

Space: O(1) because no extra space is used beyond variables

vs Alternative: Compared to dividing repeatedly by two until one, this bitwise method is faster and simpler with constant time

Edge Cases

number = 0

Returns false because zero is not a power of two

DSA C#

if (number <= 0) return false;

number = 1

Returns true because 1 is 2^0, a power of two

DSA C#

return (number & (number - 1)) == 0;

number = -8

Returns false because negative numbers are not powers of two

DSA C#

if (number <= 0) return false;

When to Use This Pattern

When you need to quickly check if a number is a power of two, use the bitwise AND pattern number & (number - 1) == 0 because it efficiently tests if only one bit is set.

Common Mistakes

Mistake: Trying to check powers of two by dividing repeatedly without handling zero or negative inputs
Fix: Add a guard to return false immediately if number is less than or equal to zero

Mistake: Using loops instead of the bitwise trick, making the solution slower
Fix: Use the bitwise AND check for constant time performance

Summary

Checks if a number has exactly one bit set, meaning it is a power of two.

Use when you need a fast and simple way to verify powers of two.

The key insight is that powers of two have only one '1' bit in binary, 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 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