Check if Number is Power of Two in DSA Rust - Build from Scratch

Check if Number is Power of Two

📖 Scenario: Imagine you are working with a system that needs to quickly check if certain numbers are powers of two. Powers of two are numbers like 1, 2, 4, 8, 16, and so on. This is useful in many areas like computer memory allocation and game development.

🎯 Goal: You will write a Rust program that checks if a given number is a power of two. You will start by setting up the number, then create a helper variable, write the logic to check the condition, and finally print the result.

📋 What You'll Learn

Create a variable called number with the value 16.

Create a boolean variable called is_power_of_two initialized to false.

Write an if statement that sets is_power_of_two to true if number is a power of two using bitwise operations.

Print "Power of two" if is_power_of_two is true, otherwise print "Not a power of two".

💡 Why This Matters

🌍 Real World

Checking if a number is a power of two is important in computer memory management, graphics programming, and optimizing algorithms.

💼 Career

Understanding bitwise operations and conditional logic is essential for software developers, especially those working with low-level programming or performance-critical applications.

1

Set the number to check

Create a variable called number and set it to 16.

DSA Rust

# Your code here

Hint

Use let number = 16; to create the variable.

2

Create a boolean variable for the result

Create a boolean variable called is_power_of_two and set it to false.

DSA Rust

fn main() {
    let number = 16;
    # Your code here
}

Hint

Use let mut is_power_of_two = false; to create a mutable boolean variable.

3

Check if the number is a power of two

Write an if statement that sets is_power_of_two to true if number is greater than zero and number & (number - 1) == 0.

DSA Rust

fn main() {
    let number = 16;
    let mut is_power_of_two = false;
    # Your code here
}

Hint

Use the bitwise AND operator & to check the power of two condition.

4

Print the result

Print "Power of two" if is_power_of_two is true, otherwise print "Not a power of two".

DSA Rust

fn main() {
    let number = 16;
    let mut is_power_of_two = false;
    if number > 0 && (number & (number - 1)) == 0 {
        is_power_of_two = true;
    }
    # Your code here
}

Hint

Use println!("Power of two") and println!("Not a power of two") inside an if statement.

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 exactly one bit set to 1 in its binary form.

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, e.g., 4 is 100.

2. Step 2: Analyze the options

   It has exactly one bit set to 1 in its binary form. matches this property. Options B, C, and D are incorrect because powers of two can be even, are not necessarily divisible by 3, and do not have all bits set to 1.

3. Final Answer:

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

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

2. Which Rust code snippet correctly checks if a number `n` is a power of two?

easy

A. n & (n - 1) == 0

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

C. n & (n + 1) == 0

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

Solution

1. Step 1: Recall the bitwise trick for power of two

   The expression `n & (n - 1) == 0` is true only if `n` is a power of two (and n > 0).

2. Step 2: Check each option

   n & (n - 1) == 0 matches the known correct bitwise check. Options A, C, and D use incorrect bitwise operators or operands.

3. Final Answer:

   n & (n - 1) == 0 -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Using OR or XOR instead of AND
• Using n + 1 instead of n - 1
• Not considering n must be positive

3. What is the output of the following Rust code?

fn main() {
    let n = 16;
    let result = n > 0 && (n & (n - 1)) == 0;
    println!("{}", result);
}

medium

A. true

B. Runtime panic

C. Compilation error

D. false

Solution

1. Step 1: Evaluate the condition for n = 16

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

2. Step 2: Check the full expression

   Since n > 0 is true and bitwise AND is 0, the expression evaluates to true.

3. Final Answer:

   true -> Option A

4. Quick Check:

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

Hint: Check bitwise AND with n-1 equals zero for power of two [OK]

Common Mistakes:

• Ignoring the n > 0 check
• Miscomputing bitwise AND
• Confusing true/false output

4. Identify the error in this Rust function that checks if a number is a power of two:

fn is_power_of_two(n: u32) -> bool {
    n & (n - 1) == 0
}

medium

A. Syntax error due to missing semicolon

B. Incorrect bitwise operator used

C. Function return type should be i32, not bool

D. Missing check for n > 0 to avoid zero being true

Solution

1. Step 1: Analyze the function logic

   The expression `n & (n - 1) == 0` returns true for zero, which is not a power of two.

2. Step 2: Identify missing condition

   We must add `n > 0` to exclude zero. Options B, C, and D are incorrect because the operator and syntax are correct, and return type bool is appropriate.

3. Final Answer:

   Missing check for n > 0 to avoid zero being true -> Option D

4. Quick Check:

   Check n > 0 to exclude zero [OK]

Hint: Always check n > 0 before bitwise test [OK]

Common Mistakes:

• Not excluding zero as power of two
• Changing correct bitwise operator
• Wrong return type assumption

5. Given a list of integers, which Rust code snippet correctly filters and collects only the numbers that are powers of two?

let numbers = vec![3, 4, 6, 8, 16, 18];
let powers: Vec<u32> = numbers.iter()
    .filter(|&&x| /* condition */)
    .cloned()
    .collect();

What should replace /* condition */?

hard

A. x & (x + 1) == 0

B. x > 0 && (x & (x - 1)) == 0

C. x > 0 || (x & (x - 1)) == 0

D. x == 0 || (x & (x - 1)) == 0

Solution

1. Step 1: Understand filtering condition for power of two

   The condition must check that x is positive and that x & (x - 1) == 0 to confirm power of two.

2. Step 2: Evaluate each option

   x > 0 && (x & (x - 1)) == 0 correctly combines both checks with AND. x > 0 || (x & (x - 1)) == 0 uses OR which is incorrect. Options A and D use wrong conditions allowing zero or incorrect bitwise operations.

3. Final Answer:

   x > 0 && (x & (x - 1)) == 0 -> Option B

4. Quick Check:

   Filter positive numbers with bitwise AND zero test [OK]

Hint: Filter with x > 0 and x & (x-1) == 0 [OK]

Common Mistakes:

• Using OR instead of AND in condition
• Allowing zero as power of two
• Using incorrect bitwise operations