Reverse Bits of a Number in DSA Rust

Mental Model

Flip the order of bits in a number so the last bit becomes first and the first becomes last.

Analogy: Imagine a row of light switches turned on or off. Reversing bits is like walking to the end of the row and flipping the switches in reverse order, so the last switch's state becomes the first in the new row.

Original bits: 1 0 1 1 0 0 1 0
Reversed bits: 0 1 0 0 1 1 0 1

Dry Run Walkthrough

Input: number: 13 (binary 00001101), reverse all 8 bits

Goal: Reverse the bits of the number 13 so the least significant bit becomes the most significant bit and vice versa.

Step 1: Extract least significant bit (LSB) 1 and add to result

result = 00000001, number shifted right to 00000110

Why: We start from the rightmost bit and build the reversed number from left to right

Step 2: Shift result left and add LSB 0

result = 00000010, number shifted right to 00000011

Why: Shift result left to make room for next bit, then add next bit

Step 3: Shift result left and add LSB 1

result = 00000101, number shifted right to 00000001

Why: Continue extracting bits and building reversed number

Step 4: Shift result left and add LSB 1

result = 00001011, number shifted right to 00000000

Why: Last bit extracted, number becomes zero

Step 5: Shift result left 4 more times adding zeros (since number is zero)

result = 10110000

Why: Complete 8 bits by shifting result left for remaining bits

Result:

Reversed bits: 10110000 (decimal 176)

Annotated Code

DSA Rust

fn reverse_bits(mut n: u8) -> u8 {
    let mut result = 0u8;
    for _ in 0..8 {
        result <<= 1; // shift result left to make room for next bit
        result |= n & 1; // add least significant bit of n to result
        n >>= 1; // shift n right to process next bit
    }
    result
}

fn main() {
    let number = 13u8; // 00001101
    let reversed = reverse_bits(number);
    println!("Reversed bits: {:08b} (decimal {})", reversed, reversed);
}

result <<= 1; // shift result left to make room for next bit

Shift result left to prepare for adding next bit

result |= n & 1; // add least significant bit of n to result

Add current least significant bit of n to result

n >>= 1; // shift n right to process next bit

Move to next bit in n by shifting right

Output

Reversed bits: 10110000 (decimal 176)

Complexity Analysis

Time: O(1) because the number of bits (8) is fixed and small

Space: O(1) because only a few variables are used regardless of input

vs Alternative: This method is efficient and direct; alternative methods using string conversion or arrays are slower and use more memory

Edge Cases

number is 0 (all bits zero)

Reversed bits remain 0

DSA Rust

for _ in 0..8 { ... } loop handles zero bits naturally

number is 255 (all bits one)

Reversed bits remain 255

DSA Rust

for _ in 0..8 { ... } loop reverses all ones correctly

number with alternating bits (e.g., 170 = 10101010)

Bits reversed correctly to 85 (01010101)

DSA Rust

bitwise operations in loop handle any pattern

When to Use This Pattern

When you need to reverse the order of bits in a number, use bitwise shifting and masking to build the reversed number bit by bit.

Common Mistakes

Mistake: Not shifting the result before adding the new bit, causing bits to overwrite
Fix: Always shift the result left before OR-ing the new bit

Mistake: Shifting the input number left instead of right, losing bits
Fix: Shift the input number right to process bits from least significant to most

Summary

Reverses the bits of a number by shifting and masking each bit.

Use when you need to flip the bit order of a fixed-size integer.

Shift the result left before adding each extracted bit from the input.

Practice

1. What does the operation of reversing bits of a number mean in simple terms?

easy

A. Adding 1 to the binary number

B. Changing all 0s to 1s and 1s to 0s

C. Flipping the order of bits from left to right

D. Shifting bits to the left by one position

Solution

1. Step 1: Understand bit representation

   Bits are the 0s and 1s that represent a number in binary form.

2. Step 2: Define reversing bits

   Reversing bits means reading the bits from right to left instead of left to right, effectively flipping their order.

3. Final Answer:

   Flipping the order of bits from left to right -> Option C

4. Quick Check:

   Reverse bits = flip order [OK]

Hint: Reverse bits means flip their order, not invert values [OK]

Common Mistakes:

• Confusing reversing bits with bitwise NOT (inverting bits)
• Thinking reversing means shifting bits
• Assuming reversing adds or subtracts from the number

2. Which Rust code snippet correctly reverses the bits of a 4-bit unsigned integer n?

easy

A. let mut rev = 0; for _ in 0..4 { rev <<= 1; rev |= n & 1; n >>= 1; }

B. let mut rev = 0; for _ in 0..4 { rev |= n & 1; rev <<= 1; n >>= 1; }

C. let mut rev = 0; for _ in 0..4 { rev += n & 1; n <<= 1; }

D. let mut rev = 0; for _ in 0..4 { rev <<= 1; rev |= n << 1; n >>= 1; }

Solution

1. Step 1: Analyze bit reversal logic

   We shift rev left by 1, add the least significant bit of n, then shift n right by 1.

2. Step 2: Check each option

   let mut rev = 0; for _ in 0..4 { rev <<= 1; rev |= n & 1; n >>= 1; } correctly does rev <<= 1; rev |= n & 1; n >>= 1; in loop. Others have wrong order or operations.

3. Final Answer:

   let mut rev = 0; for _ in 0..4 { rev <<= 1; rev |= n & 1; n >>= 1; } -> Option A

4. Quick Check:

   Shift rev left, add bit, shift n right [OK]

Hint: Shift rev left before adding bit, shift n right after [OK]

Common Mistakes:

• Adding bit before shifting rev left
• Shifting n left instead of right
• Using addition instead of bitwise OR

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

fn reverse_bits(mut n: u8) -> u8 {
    let mut rev = 0;
    for _ in 0..8 {
        rev <<= 1;
        rev |= n & 1;
        n >>= 1;
    }
    rev
}

fn main() {
    let num = 13u8; // binary 00001101
    println!("{}", reverse_bits(num));
}

medium

A. 176

B. 11

C. 101

D. 208

Solution

1. Step 1: Convert 13 to binary and reverse bits

   13 in 8 bits is 00001101. Reversing bits gives 10110000.

2. Step 2: Convert reversed bits back to decimal

   10110000 binary equals 128+32+16=176 decimal.

3. Final Answer:

   176 -> Option A

4. Quick Check:

   00001101 reversed = 10110000 = 176 [OK]

Hint: Reverse bits visually, then convert binary to decimal [OK]

Common Mistakes:

• Not using 8 bits, missing leading zeros
• Confusing bit order or reversing incorrectly
• Calculating decimal value wrong

4. Identify the bug in this Rust function that attempts to reverse bits of a 4-bit number:

fn reverse_bits(mut n: u8) -> u8 {
    let mut rev = 0;
    for _ in 0..4 {
        rev |= n & 1;
        rev <<= 1;
        n >>= 1;
    }
    rev
}

medium

A. Using bitwise OR instead of addition

B. Shifting rev left after adding bit causes incorrect result

C. Not shifting n left instead of right

D. Loop should run 8 times for 4-bit number

Solution

1. Step 1: Analyze order of operations in loop

   rev |= n & 1 adds bit, then rev <<= 1 shifts left, causing last bit to be zeroed out.

2. Step 2: Correct order is shift rev left first, then add bit

   Shifting rev left after adding bit loses the last bit added, so order must be reversed.

3. Final Answer:

   Shifting rev left after adding bit causes incorrect result -> Option B

4. Quick Check:

   Shift rev left before OR bit [OK]

Hint: Shift rev left before OR bit to avoid losing bits [OK]

Common Mistakes:

• Adding bit before shifting rev left
• Loop count mismatch for bit size
• Shifting n left instead of right

5. Given a 16-bit unsigned integer, how would you efficiently reverse its bits using Rust's built-in methods combined with bitwise operations?

hard

A. Manually loop 16 times shifting bits and reconstruct reversed number

B. Use n.swap_bytes() to reverse bits

C. Convert number to string, reverse characters, then parse back

D. Use n.reverse_bits() method directly on the number

Solution

1. Step 1: Know Rust's built-in bit reversal

   Rust's primitive integer types have a reverse_bits() method that reverses bits efficiently.

2. Step 2: Compare options

   Use n.reverse_bits() method directly on the number uses the built-in method directly, which is efficient and simple. Others are manual or incorrect methods.

3. Final Answer:

   Use n.reverse_bits() method directly on the number -> Option D

4. Quick Check:

   Use built-in reverse_bits() for efficiency [OK]

Hint: Use built-in reverse_bits() method for fast bit reversal [OK]

Common Mistakes:

• Trying manual loops instead of built-in method
• Confusing byte swap with bit reversal
• Using string conversion which is inefficient