Check if Number is Power of Two in DSA Rust - Deep Dive

Overview - Check if Number is Power of Two

What is it?

Checking if a number is a power of two means finding out if it can be written as 2 raised to some whole number. For example, 1, 2, 4, 8, 16 are powers of two. This is useful in computing because powers of two often relate to memory sizes and binary operations. The check helps optimize programs and algorithms.

Why it matters

Without this check, programs might waste time or resources handling numbers inefficiently. Many systems rely on powers of two for fast calculations and memory alignment. If we can't quickly identify these numbers, software might run slower or use more memory than needed. This check helps keep programs fast and efficient.

Where it fits

Before this, learners should understand basic binary numbers and bitwise operations. After this, they can explore more complex bit manipulation techniques and optimization strategies in algorithms.

Mental Model

Core Idea

A number is a power of two if it has exactly one '1' bit in its binary form.

Think of it like...

Imagine a row of light switches where only one switch is turned on at a time. If exactly one switch is on, it means the number is a power of two.

Binary representation example:

  Number: 8
  Binary: 00001000

Only one '1' bit is set, so 8 is a power of two.

Number: 10
Binary: 00001010

Two '1' bits are set, so 10 is NOT a power of two.

Build-Up - 6 Steps

1

Foundation

Understanding Powers of Two

Concept: What powers of two are and how they look in decimal and binary.

Powers of two are numbers like 1, 2, 4, 8, 16, etc. Each is 2 multiplied by itself some number of times. In binary, these numbers have only one '1' bit and the rest are '0's. For example, 4 in binary is 100, and 8 is 1000.

Result

Learner can recognize powers of two by their binary pattern of a single '1'.

Understanding the binary pattern of powers of two is the key to checking them efficiently.

2

Foundation

Binary Representation Basics

Concept: How numbers are represented in binary and what bits mean.

Every number can be shown as a series of bits (0s and 1s). Each bit represents a power of two, starting from the right. For example, the number 5 is 101 in binary (1*4 + 0*2 + 1*1).

Result

Learner understands how to read and interpret binary numbers.

Knowing binary helps us see why powers of two have only one '1' bit.

3

Intermediate

Bitwise AND Operation

Concept: Using bitwise AND to compare bits of two numbers.

Bitwise AND compares two numbers bit by bit. It returns 1 only if both bits are 1. For example, 6 (110) & 4 (100) = 4 (100). This operation helps us test specific bits in a number.

Result

Learner can use bitwise AND to check bits in numbers.

Bitwise AND is a powerful tool to isolate and test bits efficiently.

4

Intermediate

Power of Two Check Using Bitwise Trick

🤔Before reading on: Do you think subtracting 1 from a power of two flips all bits after the single '1' bit? Commit to yes or no.

Concept: The trick that n & (n-1) equals zero only for powers of two.

For a power of two n, subtracting 1 flips all bits after the single '1' bit. For example, 8 (1000) - 1 = 7 (0111). Doing n & (n-1) results in 0 only if n is a power of two. This is because the single '1' bit and all bits after it do not overlap.

Result

Learner can check if a number is a power of two using n & (n-1) == 0.

This bitwise trick is a fast and elegant way to check powers of two without loops.

5

Advanced

Rust Implementation of Power of Two Check

🤔Before reading on: Do you think zero or negative numbers can be powers of two? Commit to yes or no.

Concept: Writing a complete Rust function to check if a number is a power of two.

```rust fn is_power_of_two(n: u32) -> bool { n != 0 && (n & (n - 1)) == 0 } fn main() { let numbers = [0, 1, 2, 3, 4, 5, 8, 16, 18]; for &num in &numbers { println!("{} -> {}", num, is_power_of_two(num)); } } ``` This function returns true only if n is not zero and n & (n-1) is zero.

Result

Output: 0 -> false 1 -> true 2 -> true 3 -> false 4 -> true 5 -> false 8 -> true 16 -> true 18 -> false

Implementing this in Rust shows how to use bitwise operations safely and efficiently.

6

Expert

Handling Edge Cases and Signed Numbers

🤔Before reading on: Can negative numbers be powers of two in binary? Commit to yes or no.

Concept: Understanding why zero and negative numbers are excluded and how signed integers affect the check.

Zero is not a power of two because it has no '1' bits. Negative numbers in two's complement form have the highest bit set, but they are not powers of two in the positive sense. The check n != 0 ensures zero is excluded. For signed integers, the check must consider only positive values to be meaningful.

Result

Learner knows to exclude zero and negatives when checking powers of two.

Recognizing these edge cases prevents bugs and incorrect results in real applications.

Under the Hood

The check n & (n-1) works because subtracting 1 from a power of two flips all bits after the single '1' bit, turning it into zeros and ones that do not overlap with the original number's single '1' bit. The bitwise AND then results in zero only if there was exactly one '1' bit in n.

Why designed this way?

This method was designed to provide a fast, constant-time check using simple bitwise operations instead of loops or division. It leverages binary number properties and hardware-supported operations for efficiency.

  n:     0 0 0 1 0 0 0 0  (example: 16)
  n-1:   0 0 0 0 1 1 1 1  (15)
  n&(n-1):0 0 0 0 0 0 0 0  (0 means power of two)

If n had more than one '1' bit, n&(n-1) would be non-zero.

Myth Busters - 3 Common Misconceptions

Quick: Is zero considered a power of two? Commit to yes or no.

Common Belief: Zero is a power of two because it is 2 raised to the power of zero.

Reality: Zero is not a power of two; 2^0 equals 1, not zero.

Why it matters: Treating zero as a power of two causes incorrect results and logic errors in programs.

Quick: Can negative numbers be powers of two? Commit to yes or no.

Common Belief: Negative numbers can be powers of two because they have a single '1' bit in two's complement form.

Reality: Negative numbers are not powers of two in the usual sense; the check applies only to positive integers.

Why it matters: Including negatives leads to wrong conclusions and bugs in algorithms expecting positive powers of two.

Quick: Does the bitwise trick work for all integer types? Commit to yes or no.

Common Belief: The n & (n-1) trick works the same for signed and unsigned integers.

Reality: It only works correctly for unsigned or positive integers; signed integers can produce unexpected results due to sign bits.

Why it matters: Misusing the trick on signed integers can cause subtle bugs and incorrect checks.

Expert Zone

1

The bitwise trick is constant time and does not depend on the number's size, making it extremely efficient for large numbers.

2

In some architectures, checking powers of two can be done with specialized CPU instructions, but the bitwise method is portable and fast.

3

When working with floating-point numbers, this check does not apply directly; understanding the data type is crucial.

When NOT to use

Avoid this method for floating-point numbers or when negative powers of two are meaningful. Instead, use logarithmic checks or floating-point specific methods.

Production Patterns

Used in memory allocation to check alignment, in graphics programming for texture sizes, and in algorithms that require input sizes to be powers of two for optimization.

Connections

Bit Manipulation

Builds-on

Understanding this check deepens knowledge of bitwise operations, which are fundamental in low-level programming and optimization.

Memory Alignment

Application

Powers of two are critical in aligning memory addresses for faster access, so this check helps ensure proper alignment.

Signal Processing

Related concept

In signal processing, buffer sizes are often powers of two for efficient FFT algorithms, linking this check to performance in a different field.

Common Pitfalls

#1 Checking zero as a power of two.

Wrong approach:

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

Correct approach:

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

Root cause:

Not excluding zero leads to true for zero because 0 & (0-1) == 0, which is incorrect.

#2 Applying the check to signed integers without validation.

Wrong approach:

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

Correct approach:

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

Root cause:

Signed integers can be negative; the check must ensure positivity to be valid.

#3 Using division or loops instead of bitwise operations.

Wrong approach:

fn is_power_of_two(mut n: u32) -> bool {
if n == 0 { return false; }
while n % 2 == 0 {
n /= 2;
}
n == 1
}

Correct approach:

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

Root cause:

Loops and division are slower and less efficient than bitwise operations.

Key Takeaways

A number is a power of two if it has exactly one '1' bit in its binary form.

The bitwise trick n & (n-1) == 0 efficiently checks for powers of two in constant time.

Zero and negative numbers are not powers of two and must be excluded in checks.

Bitwise operations provide fast, low-level tools essential for performance-critical code.

Understanding binary representation is key to mastering many algorithmic optimizations.

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