Check if Number is Power of Two in DSA Rust - Execution Trace

Concept Flow - Check if Number is Power of Two

Start with number n

↓

Check if n <= 0?

Yes→Return False

No↓

Compute n & (n-1)

↓

Is result 0?

Yes→Return True

No↓

Return False

Start with the number n, if n is positive, check if n & (n-1) equals zero. If yes, n is a power of two; otherwise, it is not.

Execution Sample

DSA Rust

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

This function returns true if n is a power of two, false otherwise.

Execution Table

Step	Operation	Input n	Compute n-1	Compute n & (n-1)	Result	Return Value
1	Check if n == 0	8	-	-	False	Continue
2	Calculate n-1	8	7	-	-	-
3	Calculate n & (n-1)	8	7	8 & 7 = 0	0	-
4	Check if result == 0	8	7	0	True	Return True

💡 Result of n & (n-1) is 0, so 8 is a power of two.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
n	8	8	8	8
n-1	-	7	7	7
n & (n-1)	-	-	0	0
Return Value	-	-	-	True

Key Moments - 3 Insights

Why do we check if n == 0 first?

Because zero is not a power of two and the bitwise operation n & (n-1) would also be zero, which would incorrectly indicate true. See execution_table step 1.

Why does n & (n-1) equal zero only for powers of two?

Because powers of two have only one bit set. Subtracting 1 flips that bit and all lower bits, so ANDing them results in zero. See execution_table steps 2 and 3.

What happens if n is not a power of two?

The result of n & (n-1) will not be zero, so the function returns false. This is shown by the check in step 4.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of n & (n-1) at step 3?

A 8

B 0

C 7

D 1

💡 Hint

Refer to the 'Compute n & (n-1)' column in execution_table row 3.

At which step does the function decide to return True?

A Step 1

B Step 2

C Step 4

D Step 3

💡 Hint

Look at the 'Return Value' column in execution_table.

If n was 0, what would the function return according to the execution flow?

A False

B True

C Depends on n-1

D Error

💡 Hint

Check execution_table step 1 where n == 0 returns false immediately.

Concept Snapshot

Check if n is zero first (return false).
Compute n & (n-1).
If result is zero, n is power of two.
Otherwise, it is not.
This works because powers of two have only one bit set.

Full Transcript

To check if a number n is a power of two, first verify if n is zero. If it is, return false because zero is not a power of two. Then compute the bitwise AND of n and n-1. If this result is zero, it means n has only one bit set, so it is a power of two. Otherwise, it is not. This method is efficient and uses simple bitwise operations.

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