Check if Number is Power of Two in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean for a number to be a power of two?

A number is a power of two if it can be written as 2 raised to some integer exponent, like 1, 2, 4, 8, 16, and so on.

intermediate

How can you check if a number is a power of two using bitwise operations?

If a number is a power of two, it has exactly one '1' bit in its binary form. So, n & (n - 1) equals 0 only for powers of two (and n > 0).

beginner

Rust code snippet: What does this function do? fn is_power_of_two(n: u32) -> bool { n != 0 && (n & (n - 1)) == 0 }

This function returns true if n is a power of two, false otherwise. It checks that n is not zero and that n & (n - 1) equals zero.

beginner

Why do we check n != 0 before the bitwise operation in the power of two check?

Because zero is not a power of two, and without this check, the bitwise condition would incorrectly return true for zero.

beginner

What is the binary representation of 8 and how does it confirm 8 is a power of two?

8 in binary is 1000. It has exactly one '1' bit, so it is a power of two.

Which of these numbers is NOT a power of two?

A 8

B 16

C 18

D 4

18 is not a power of two because it cannot be expressed as 2 raised to an integer.

What does the expression n & (n - 1) == 0 check for a positive integer n?

A If n is a power of two

B If n is odd

C If n is even

D If n is zero

This expression is true only when n is a power of two.

Why must we ensure n != 0 before checking n & (n - 1) == 0?

A Because zero & (zero - 1) equals zero, which is incorrect

B Because zero is a power of two

C Because zero is odd

D Because zero is negative

Without checking n != 0, zero would incorrectly pass the power of two test.

What is the output of is_power_of_two(1) in Rust?

A undefined

B true

C panic

D false

1 is 2^0, so it is a power of two and the function returns true.

Which binary pattern represents a power of two?

A 1111

B 1010

C 1100

D 1000

1000 has exactly one '1' bit, so it represents a power of two.

Explain how to check if a number is a power of two using bitwise operations.

Think about how binary numbers look for powers of two.

Write a simple Rust function to check if a number is a power of two and explain each step.

Use bitwise AND and subtraction.

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