Reverse Bits of a Number in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean to reverse the bits of a number?

Reversing the bits means flipping the order of all bits in the binary form of the number, so the first bit becomes the last, the second becomes the second last, and so on.

beginner

In Rust, which operator is used to shift bits to the right?

The right shift operator is `>>`. It moves bits to the right, dropping the rightmost bits and filling from the left with zeros.

beginner

Why do we use bitwise AND (`&`) with 1 when reversing bits?

Using `& 1` extracts the least significant bit (rightmost bit) of a number, which helps us read bits one by one from right to left.

intermediate

What is the purpose of shifting the result to the left when reversing bits?

Shifting the result to the left makes space for the next bit to be added at the rightmost position, building the reversed bit sequence step by step.

beginner

How many times do we need to repeat the bit extraction and shifting to reverse a 32-bit number?

We repeat the process 32 times, once for each bit in the 32-bit number, to reverse all bits completely.

What does the expression `n & 1` do in bit manipulation?

A Extracts the most significant bit of n

B Shifts n to the left by 1

C Shifts n to the right by 1

D Extracts the least significant bit of n

The bitwise AND with 1 extracts the rightmost bit of the number.

In reversing bits, why do we shift the result left before adding the next bit?

A To make space for the new bit on the right

B To discard the previous bits

C To reverse the bits automatically

D To reset the result to zero

Shifting left moves bits to the left, creating space on the right for the next bit.

How many bits are processed when reversing bits of a 32-bit unsigned integer?

A 16

B 8

C 32

D 64

A 32-bit number has 32 bits to process.

Which Rust operator shifts bits to the right?

A <<

B >>

C &

D |

The `>>` operator shifts bits to the right.

What is the initial value of the result variable when reversing bits?

A 0

B The input number

C Depends on the input

D 1

We start with 0 and build the reversed bits step by step.

Explain step-by-step how to reverse the bits of a 32-bit number using bitwise operations.

Think about reading bits from right to left and building the reversed number from left to right.

Describe why shifting and bitwise AND are essential in reversing bits.

Focus on how bits are read and placed in reverse order.

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