Reverse Bits of a Number in DSA Rust - Execution Trace

Concept Flow - Reverse Bits of a Number

Start with input number

↓

Initialize result = 0

↓

For each bit position 0 to 31

↓

Extract rightmost bit of input

↓

Shift result left by 1

↓

Add extracted bit to result

↓

Shift input right by 1

↓

Repeat until all bits processed

↓

Return result with bits reversed

Start with the input number, extract bits one by one from right to left, build the reversed number by shifting and adding bits, repeat for all 32 bits, then return the reversed result.

Execution Sample

DSA Rust

fn reverse_bits(mut n: u32) -> u32 {
    let mut result = 0;
    for _ in 0..32 {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }
    result
}

This code reverses the bits of a 32-bit unsigned integer by shifting and masking bits.

Execution Table

Step	Operation	Input (n)	Extracted Bit (n & 1)	Result Before	Result After	Visual State (bits)
1	Initialize result=0	00000000000000000000000000000011	-	00000000000000000000000000000000	00000000000000000000000000000000	result=0
2	Extract bit, shift result, add bit	00000000000000000000000000000011	1	00000000000000000000000000000000	00000000000000000000000000000001	result=000...001
3	Shift input right	00000000000000000000000000000001	-	00000000000000000000000000000001	00000000000000000000000000000001	n=000...001
4	Extract bit, shift result, add bit	00000000000000000000000000000001	1	00000000000000000000000000000001	00000000000000000000000000000011	result=000...011
5	Shift input right	00000000000000000000000000000000	-	00000000000000000000000000000011	00000000000000000000000000000011	n=000...000
6	Extract bit, shift result, add bit	00000000000000000000000000000000	0	00000000000000000000000000000011	00000000000000000000000000000110	result=000...110
7	Shift input right	00000000000000000000000000000000	-	00000000000000000000000000000110	00000000000000000000000000000110	n=000...000
8	Extract bit, shift result, add bit	00000000000000000000000000000000	0	00000000000000000000000000000110	00000000000000000000000000001100	result=000...1100
9	Shift input right	00000000000000000000000000000000	-	00000000000000000000000000001100	00000000000000000000000000001100	n=000...000
10	Repeat for remaining bits (all 0)	00000000000000000000000000000000	0	shifting and adding 0	result shifts left each time	result accumulates zeros on right
32	Final step	00000000000000000000000000000000	0	result before last shift	result final	result=11000000000000000000000000000000
33	Return result	-	-	-	11000000000000000000000000000000	Reversed bits of input 3

💡 All 32 bits processed, loop ends, reversed bits returned.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 32	Final
n	00000000000000000000000000000011	00000000000000000000000000000001	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000
result	00000000000000000000000000000000	00000000000000000000000000000001	00000000000000000000000000000011	00000000000000000000000000000110	00000000000000000000000000001100	11000000000000000000000000000000	11000000000000000000000000000000

Key Moments - 3 Insights

Why do we shift the result left before adding the extracted bit?

Because we build the reversed number from left to right, shifting left makes space for the new bit on the right side. See execution_table steps 2 and 4 where result shifts left before adding the bit.

Why do we extract the rightmost bit of n using (n & 1)?

Because (n & 1) isolates the least significant bit (rightmost bit) of n. This bit is then added to the result. Refer to execution_table column 'Extracted Bit (n & 1)' for each step.

What happens when n becomes zero before finishing 32 steps?

We continue shifting result and adding zeros because we must process all 32 bits. This ensures the reversed number has all bits correctly placed. See steps 10 to 32 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of result after adding the extracted bit?

A 00000000000000000000000000000010

B 00000000000000000000000000000011

C 00000000000000000000000000000001

D 00000000000000000000000000000110

💡 Hint

Check the 'Result After' column at step 4 in execution_table.

At which step does the input n become zero for the first time?

A Step 5

B Step 3

C Step 6

D Step 8

💡 Hint

Look at the 'Input (n)' column in execution_table and find when it changes to all zeros.

If the input number was 1 instead of 3, how would the result after step 2 change?

A Result would be 00000000000000000000000000000000

B Result would be 00000000000000000000000000000010

C Result would be 00000000000000000000000000000001

D Result would be 00000000000000000000000000000011

💡 Hint

Compare the extracted bit and result update at step 2 for input 3 and input 1.

Concept Snapshot

Reverse Bits of a Number:
- Initialize result=0
- For each of 32 bits:
  - Extract rightmost bit of input (n & 1)
  - Shift result left by 1
  - Add extracted bit to result
  - Shift input right by 1
- Return result with bits reversed

Full Transcript

This concept reverses the bits of a 32-bit unsigned integer. We start with the input number and a result initialized to zero. For each bit from 0 to 31, we extract the rightmost bit of the input using bitwise AND with 1. Then we shift the result left by one to make space for the new bit, and add the extracted bit to the result. After that, we shift the input right by one to process the next bit. We repeat this until all 32 bits are processed. The final result contains the bits of the original number in reverse order. The execution table shows each step with the input, extracted bit, result before and after, and the visual bit state. Key moments clarify why we shift result before adding bits and why we continue even if input becomes zero early. The visual quiz tests understanding of these steps.

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