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

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Rust code checking power of two?

Consider the following Rust function that checks if a number is a power of two. What will be printed when calling is_power_of_two(16)?

DSA Rust

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

fn main() {
    println!("{}", is_power_of_two(16));
}

A true

B false

C Compilation error

D Runtime panic

💡 Hint

Recall that powers of two have only one bit set in binary.

The function returns true if the number is not zero and has exactly one bit set. 16 in binary is 10000, which is a power of two, so output is true.

❓ Predict Output

intermediate

What does this Rust code print for input 18?

Given the same function is_power_of_two, what will be printed when calling is_power_of_two(18)?

DSA Rust

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

fn main() {
    println!("{}", is_power_of_two(18));
}

A Compilation error

B true

C Runtime panic

D false

💡 Hint

Check the binary form of 18 and count set bits.

18 in binary is 10010, which has two bits set, so it is not a power of two. The function returns false.

🔧 Debug

advanced

What happens when compiling this Rust code?

This Rust function checks if a number is a power of two using a specific expression. What will occur when compiling and running it with input 8?

DSA Rust

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

fn main() {
    println!("{}", is_power_of_two(8));
}

A Runtime panic due to overflow

B No error, prints true

C Compilation error due to operator precedence

D Compilation error due to missing semicolon

💡 Hint

Rust operator precedence: subtraction (-) has higher precedence than bitwise AND (&).

No compilation error. The expression (n & n - 1) is parsed as n & (n - 1) because subtraction has higher precedence than bitwise AND. For n=8 (1000 in binary), 8 & 7 (0111) == 0, so it returns true.

🧠 Conceptual

advanced

Why does the expression n & (n - 1) check for power of two?

Explain why the bitwise operation n & (n - 1) equals zero only when n is a power of two.

A Because powers of two have only one bit set, subtracting 1 flips all lower bits, so AND results in zero.

B Because powers of two are always even numbers, and AND with n-1 clears the least significant bit.

C Because n-1 always has the same bits as n, so AND is zero only for powers of two.

D Because the operation counts the number of set bits in n.

💡 Hint

Think about binary representation of powers of two and what subtracting 1 does.

A power of two has exactly one bit set. Subtracting 1 flips that bit and sets all lower bits. ANDing with original clears that bit, resulting in zero.

🚀 Application

expert

What is the output of this Rust code printing powers of two up to 32?

This Rust code prints numbers from 1 to 32 that are powers of two. What is the printed output?

DSA Rust

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

fn main() {
    for i in 1..=32 {
        if is_power_of_two(i) {
            print!("{} ", i);
        }
    }
}

A "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 "

B "2 4 8 16 32 "

C "1 2 4 8 16 32 "

D "1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 "

💡 Hint

Recall which numbers have exactly one bit set in binary.

The code prints all powers of two between 1 and 32 inclusive: 1, 2, 4, 8, 16, 32.

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